排序和查找

数组、排序和查找

第六章数组、排序和查找

数组

可以存放多个同一类型的数据。数组也是一种数据类型，是引用类型。

数组的使用

动态初始化一
- 数组的定义
  数据类型[] 数组名 = new 数据类型[大小] ;
  int[] Array = new int[10]; ——> 创建了一个数组，名字是 Array，可以存放 10 个 int 类型的数据
  （注意：未放初值则默认为 0 ）
- 数组的引用
  数组名[下标/索引]，比如 Array 数组的第 1 个数据元素为 Array[0]；
  （注意：数组下标从 0 开始）
动态初始化二
- 先声明数组，再创建数组。
  int[] Array; //声明 Array 数组，这时 Array 是 null
  Array = new int [10];
静态初始化
- 数据类型[] 数组名 = {元素值 , 元素值 , 元素值 , …… , 元素值} ;

★数组使用注意事项和细节

数组是多个相同类型数据的组合，实现对这些数据的统一管理；
数组中的元素可以是任何数据类型，包括基本类型和引用类型，但是不能混用；
★数组创建后，如果没有赋值，则有默认值：
- int、short、byte、long ——> 默认值为 0
- float、double ——> 默认值为 0.0
- char ——> 默认值为 \u0000（空字符）
- boolean ——> 默认值为 false
- String ——> 默认值为 null
使用数组的步骤：声明数组并开辟空间 ——> 给数组的各个元素赋值 ——> 利用下标使用数组；
数组的下标是从 0 开始的；
数组下标必须在指定范围内使用，否则报：下标越界异常；
数组属于引用类型，数组型数据是对象（object）。

数组赋值机制

基本数据类型赋值，这个值就是具体的数据，而且互相不影响； ——> 赋值方式为值拷贝
数组在默认情况下是引用传递，赋的值是地址。 ——> 赋值方式为引用赋值

public class Test{
    public static void main(String[] args){
        int[] Array1 = {1,2,3};
        int[] Array2 = Array1;
        Array2[1] = 4;
        for(int i = 0 ; i < Array1.length ; i ++){
            System.out.print( Array1[i] + " ");		//输出结果是 1 4 3 ，即 Array2 和 Array1 管理的是同一个数组
        }
    }
}

（注意：此时若 System.out.println(Array1); 和 System.out.println(Array2);会发现，他们地址是一样的）

数组拷贝

将 int[] arr1 = {10,20,30}; 的数据拷贝到 arr2 数组，要求数据空间是独立的（即非引用赋值）。

public class Test {
    public static void main(String[] args) {
        int[] arr1 = {10, 20, 30};
        int[] arr2 = new int[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            arr2[i] = arr1[i];
        }
        for (int i = 0; i < arr1.length; i++) {
            System.out.println(arr2[i]);
        }
    }
}

数组反转

把数组 int[] arr1 = {10,20,30,40,50,60}; 中的元素进行逆序反转，即反转为 int[] arr1 = {60,50,40,30,20,10};

public class Test {
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50, 60};
        int temp = 0;
        for (int i = 0; i < arr.length / 2; i++) {
            temp = arr[i];
            arr[i] = arr[arr.length - 1 - i];
            arr[arr.length - 1 - i] = temp;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

数组扩容

实现动态地给数组添加元素，实现对数组的扩容。

import java.util.Scanner;

public class Test {
    public static void main(String[] args) {
        Scanner myScanner = new Scanner(System.in);
        int[] arr = {1, 2, 3};
        do {
            System.out.println("当前数组元素有：");
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + "\t");
            }
            System.out.println("是否添加？y/n");
            char c = myScanner.next().charAt(0);
            if (c == 'y') {
                System.out.print("请输入要添加的数字：");
                int addNum = myScanner.nextInt();
                int[] arrNew = new int[arr.length + 1];
                for (int i = 0; i < arr.length; i++) {
                    arrNew[i] = arr[i];
                }
                arrNew[arr.length] = addNum;
                arr = arrNew;
            } else if (c == 'n') {
                System.out.println("输入为'n',不再添加");
                break;
            } else {
                System.out.println("输入的既不是'y'也不是'n',出现错误,终止添加");
                break;
            }
        } while (true);
        System.out.println("程序退出");
    }
}

已知有个升序的数组，要求插入一个元素后该数组顺序依然是升序，比如：[10, 12, 45, 90]，添加 23 后，数组为 [10, 12, 23, 45, 90]

import java.util.Scanner;

public class Test {
    public static void main(String[] args) {
        Scanner myScanner = new Scanner(System.in);
        int[] arr = {10, 12, 45, 90};
        System.out.println("请输入你要插入的整数：");
        int num = myScanner.nextInt();
        int index = -1;
        //找到输入的整数要插入的位置
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > num) {
                index = i;
                break;
            }
        }
        if (index == -1) {
            index = arr.length;
        }
        int[] arrNew = new int[arr.length + 1];
        //开始插入
        for (int i = 0, j = 0; i < arr.length; i++, j++) {
            //当 i == index 时，就留出这个位置给 num
            if (i == index) {
                j++;
                arrNew[j] = arr[i];
                continue;
            }
            arrNew[j] = arr[i];
        }
        arrNew[index] = num;
        arr = arrNew;
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}

数据缩减

实现动态地减少数组的最后一位元素，实现对数组的缩减。

import java.util.Scanner;

public class Test {
    public static void main(String[] args) {
        Scanner myScanner = new Scanner(System.in);
        int[] arr = {1, 2, 3, 4, 5};
        do {
            System.out.println("当前数组元素有：");
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + "\t");
            }
            System.out.println("是否缩减一位？y/n");
            char c = myScanner.next().charAt(0);
            if (c == 'y') {
                if (arr.length - 1 == 0) {
                    System.out.println("数组只剩下最后一个元素：" + arr[0] + "，无法再继续缩减。");
                    break;
                }
                int[] arrNew = new int[arr.length - 1];
                for (int i = 0; i < arr.length - 1; i++) {
                    arrNew[i] = arr[i];
                }
                arr = arrNew;
            } else if (c == 'n') {
                System.out.println("输入为'n',不再缩减");
                break;
            } else {
                System.out.println("输入的既不是'y'也不是'n',出现错误,终止缩减");
                break;
            }
        } while (true);
        System.out.println("程序退出");
    }
}

排序

排序是将多个数据，依照指定的顺序（升序或者降序）进行排列的过程。
排序的分类：
- 内部排序，指将需要处理的所有数据都加载到内部存储器中进行排序。包括（交换式排序法、选择式排序法和插入式排序法）；
- 外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。包括（合并排序法和直接合并排序法）。

冒泡排序

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前面移向后面，就像水底下的气泡一样逐渐向上冒。

public class Test {
    public static void main(String[] args) {
        int[] arr = {24, 69, 80, 57, 13, 45, 77};
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = false;
            for (int j = 1; j < arr.length - i; j++) {
                if (arr[j - 1] > arr[j]) {
                    int temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;		//若发现无交换，则说明已经排好序了，可以跳出循环
            }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}

冒泡排序特点：
若一共有 n 个数据，则一共要进行 n-1 轮排序（在没有提前结束，即 break 的前提下），每一轮排序都可以确定一个数的位置，且每一轮排序中的比较的次数都在减小（因为确定的数的位置在增加）。
如上述代码，第一轮排序确定了最大数的位置、第二轮排序确定了第二大的数的位置……以此类推。

顺序查找

import java.util.Scanner;

public class Test {
    public static void main(String[] args) {
        Scanner myScanner = new Scanner(System.in);
        String[] names = {"张三", "李四", "王五"};
        System.out.println("请输入你要查找的名称：");
        String name = myScanner.nextLine();
        boolean flag = false;
        for (int i = 0; i < names.length; i++) {
            if (name.equals(names[i])) {
                System.out.println("该名称的下标为：" + i);
                flag = true;
                break;
            }
        }
        if (!flag) {
            System.out.println("没有找到该名称");
        }
    }
}

二维数组

二维数组：原来的一维数组中的每个元素也是一个一维数组，就构成了二维数组。

public class Test{
    public static void main(String[] args) {
        int[][] arr = { {0,0},
                		{0,0,0},
               			{0,0,0,0}};
        System.out.println(arr.length);	    //输出为 3，代表二维数组 arr 中的一维数组个数
        System.out.println(arr[0].length);	//输出为 2，代表一维数组 arr[0] 中的元素个数
        System.out.println(arr[1].length);	//输出为 3，代表一维数组 arr[1] 中的元素个数
        System.out.println(arr[2].length);	//输出为 4，代表一维数组 arr[2] 中的元素个数
    }
}

public class Test {
    public static void main(String[] args) {
        int[][] arr = new int[3][];			//只定义了二维数组的长度为3，但是每个一维数组还没有内存空间
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new int[i + 1];		//动态地定义二维数组中的每个一维数组的长度
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println();
        }
    }
}

二维数组的使用

动态初始化一
- 数组的定义
  数据类型[][] 数组名 = new 数据类型[大小][大小] ;
  int[][] Array = new int[3][4]; ——> 创建了一个二维数组，名字是 Array，可以存放 3*4=12 个 int 类型的数据
  （注意：未放初值则默认为 0 ）
- 数组的引用
  数组名[下标/索引][下标/索引]，比如 Array 数组的第 1 个一维数组的第 2 个数据元素为 Array[0][1]；
  （注意：数组下标从 0 开始）
动态初始化二
- 先声明数组，再创建数组。
  int[][] Array; //声明 Array 数组，这时 Array 是 null
  Array = new int [3][4];
动态初始化三
- 先声明二维数组的长度，后续再动态声明二维数组中的每个一维数组的长度。
  int[][] arr = new int[3][];
  arr[0] = new int[4];
  arr[1] = new int[5];
  arr[2] = new int[6];
静态初始化
- 数据类型[][] 数组名 = { {元素值 , …… , 元素值},
  {元素值 , 元素值 , …… , 元素值},
  {元素值 , 元素值 , 元素值 , …… , 元素值},
  ……,
  {元素值 , 元素值 , 元素值 , …… , 元素值}} ;
  其中每个一维数组的长度可不相同。

注意：int[] x,y[]; x 是 int 类型的一维数组；y 是 int 类型的二维数组。

二维数组的遍历

int[][] arr = {{4, 6}, {1, 4, 5, 7}, {-2}}; ，遍历该二维数组，并得到和。

public class Test {
    public static void main(String[] args) {
        int[][] arr = {{4, 6}, {1, 4, 5, 7}, {-2}};
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                sum += arr[i][j];
            }
        }
        System.out.println("二维数组元素之和为：" + sum);
    }
}

杨辉三角

使用二维数组打印一个 10 行的杨辉三角。

public class Test {
    public static void main(String[] args) {
        int[][] arr = new int[10][];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new int[i + 1];
            for (int j = 0; j < arr[i].length; j++) {
                if (j == 0 || j == arr[i].length - 1) {
                    arr[i][j] = 1;
                } else {
                    arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - arr[i].length; j++) {
                System.out.print(" ");
            }
            for (int k = 0; k < arr[i].length; k++) {
                System.out.print(arr[i][k] + " ");
            }
            System.out.println();
        }
    }
}

第六章 数组、排序和查找

数组