<Java> 5 数组、排序和查找

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

即：数组就是一组数据。

5.1 一维数组

5.1.1 数组基础

数组可以是多个相同类型数据的组合，实现对这些数据的统一管理。

数组中的元素可以是任何数据类型。包括基本类型和引用类型，但是不能混用

数组的下标的从0开始的

数组创建后，如果没有赋值，有默认值：int（0），short（0），byte（0），long（0L），float（0.0F），double（0.0），char（000），boolean（false），String（null），Object（null）

使用数组的步骤：

1. 声明数组并开辟空间
2. 给数组各个元素赋值
3. 使用数组

数组属于引用类型，数组型数据是对象（object）

数组的构造方法：

• 构造方式1：动态初始化

  int[] a = new int[5];				// 创建了数组 name，存放5个int
  int a2[] = new int[1];				// 这种写法也行
  a[2] = 15;							// 访问数组第3个数

• 构造方式2：动态初始化

  double[] scores;							// 先声明数组 name，此时数组是 null
  double scores[];
  scores = new double[5];					// 分配内存空间，可以存放数据了

//从键盘输入一组数据
import java.util.Scanner;//导入
public class test {

    public static void main(String[] args) {
        double scores[];
        scores = new double[5];
        Scanner myScanner = new Scanner(System.in);
        for(int i = 0; i < scores.length; i++){
            System.out.println("请输入第" + (i+1) + "个元素的值");
            scores[i] = myScanner.nextDouble();
        }
        System.out.println("===数组的元素的清空如下：===");
        for(int i = 0; i < scores.length; i++){
            System.out.println("第" + (i+1) + "个元素的值= " + scores[i]);
        }
    }
}

• 构造方式3：静态初始化

  int a[] = {2,5,8,50,60,77}

  确切知道数组每个元素的场合可以用这个方法。

数组的使用方法：

• 访问数组元素：数组名[元素下标]

  其中，元素下标从 0 开始编号。如：访问 strs 数组的第一个元素 strs[0]

• 数组长度：数组名.length

  是一个 int 值。不能通过试图改变该值来改变数组容量

5.1.2 数组赋值机制

1. 基本数据类型赋值，赋值方式是值拷贝。这个值就是具体的数据，且互不影响

2. 数组在默认情况下是引用传递，赋的值是地址，赋值方式为引用传达。

   int[] array1 = {0, 0, 0};
   int[] array2 = array1;
   array2[0] = 100; //array2的变化会影响到array1

   上述情况下，array1[0] 也会变成 100。因为数组在 JVM 的 栈 里是一个地址，指向 堆 里的一个空间。这两个数组在上述情况下指向同一空间。

   

   image-20231125112653956

5.1.3 数组拷贝

int[] array1 = {10, 20, 30};
int[] array2 = new int[array1.length];
for (int i = 0;i < array1.length;i++) {
    array2[i] = array1[i];
}
//但是按照上述方式拷贝后，两数组相互独立。

5.1.4 数组反转

方式 1：通过找规律反转，（临时变量）

public class ArrayReverse {
    public static void main(String[] args) {
        int[] arr = {11, 22, 33, 44, 55, 66};

        //规律
        //1. 把 arr[0] 和 arr[5] 进行交换 {66,22,33,44,55,11}
        //2. 把 arr[1] 和 arr[4] 进行交换 {66,55,33,44,22,11}
        //3. 把 arr[2] 和 arr[3] 进行交换 {66,55,44,33,22,11}
        //4. 一共要交换 3 次 = arr.length / 2
        //5. 每次交换时，对应的下标 是 arr[i] 和 arr[arr.length - 1 -i]
        int temp = 0;
        int len = arr.length; //计算数组的长度
        for( int i = 0; i < len / 2; i++) {
            temp = arr[len - 1 - i];//保存
            arr[len - 1 - i] = arr[i];
            arr[i] = temp;
        }
        System.out.println("===翻转后数组===");
        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");//66,55,44,33,22,11
        }
    }
}

方式 2：使用逆序赋值方式，（创建一个新数组）

public class test {

    public static void main(String[] args) {
        int[] arr = {11, 22, 33, 44, 55, 66};
        //使用逆序赋值方式
        //1. 先创建一个新的数组 arr2 ,大小 arr.length
        //2. 逆序遍历 arr ,将 每个元素拷贝到 arr2 的元素中(顺序拷贝)
        //3. 建议增加一个循环变量 j -> 0 -> 5
        int[] arr2 = new int[arr.length];
		//逆序遍历 arr
        for(int i = arr.length - 1, j = 0; i >= 0; i--, j++) {
            arr2[j] = arr[i];
        }
        //4. 当 for 循环结束，arr2 就是一个逆序的数组 {66, 55, 44,33, 22, 11}
        //5. 让 arr 指向 arr2 数据空间, 此时 arr 原来的数据空间就没有变量引用
        // 会被当做垃圾，销毁
        arr = arr2;
        System.out.println("====arr 的元素情况=====");
		//6. 输出 arr 看看
        for(int i = 0; i < arr.length; i++) {

            System.out.print(arr[i] + "\t");
        }
    }
}

5.1.5 数组的扩容

当数组达到上限时，创建一个容量更大的新数组。将旧数组的元素依次放入，之后替换旧数组。

以下是一个扩容方法：

import java.util.Scanner;//导入
public class test {

    public static void main(String[] args) {
        /*
        要求：实现动态的给数组添加元素效果，实现对数组扩容。ArrayAdd.java
        1.原始数组使用静态分配 int[] arr = {1,2,3}
        2.增加的元素 4，直接放在数组的最后 arr = {1,2,3,4}
        3.用户可以通过如下方法来决定是否继续添加，添加成功，是否继续？y/n
        思路分析
        1. 定义初始数组 int[] arr = {1,2,3}//下标 0-2
        2. 定义一个新的数组 int[] arrNew = new int[arr.length+1];
        3. 遍历 arr 数组，依次将 arr 的元素拷贝到 arrNew 数组
        4. 将 4 赋给 arrNew[arrNew.length - 1] = 4;把 4 赋给 arrNew 最后一个元素
        5. 让 arr 指向 arrNew ; arr = arrNew; 那么 原来 arr 数组就被销毁
        6. 创建一个 Scanner 可以接受用户输入
        7. 因为用户什么时候退出，不确定，老师使用 do-while + break 来控制
        */
        Scanner myScanner = new Scanner(System.in);
        //初始化数组
        int[] arr = {1,2,3};
        do {
            int[] arrNew = new int[arr.length + 1];

            //遍历 arr 数组，依次将 arr 的元素拷贝到 arrNew 数组
            for(int i = 0; i < arr.length; i++) {
                arrNew[i] = arr[i];
            }
            System.out.println("请输入你要添加的元素：");
            int addNum = myScanner.nextInt();
    
            arrNew[arrNew.length - 1] = addNum;
            //让 arr 指向 arrNew,
            arr = arrNew;
            System.out.println("====arr 扩容后元素情况====");
            for(int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + "\t");
            }
            //问用户是否继续
            System.out.println("是否继续添加 y/n");
            char key = myScanner.next().charAt(0);
            if( key == 'n') { //如果输入 n ,就结束
                break;
            }
        }while(true);

        System.out.println("你退出了添加...");
    }
}

5.2 排序算法

排序也叫排序算法。是将一组数据，依指定的顺序进行排列的过程

排序分为两类：

• 内部排序：将所有要处理的数据加载到内部存储器中进行排序

  内部排序主要有以下几种：

  • 插入排序：直接插入排序、希儿排序
  • 选择排序：简单选择排序、堆排序
  • 交换排序：冒泡排序、快速排序
  • 归并排序
  • 基数排序

• 外部排序：数据量庞大，无法全部加载到内存中，需要借助外部存储进行排序

  如：合并排序法、直接合并排序法

5.2.1 排序算法的时间复杂度

排序法	平均时间	最差情形	稳定性	额外空间	说明
冒泡排序	O(\(n^2\))	O(\(n^2\))	稳定	O(1)	n 小时较好
交换排序	O(n2)	O(\(n^2\))	不稳定	O(1)	n 小时较好
选择排序	O(\(n^2\))	O(\(n^2\))	不稳定	O(1)	n 小时较好
插入排序	O(\(n^2\))	O(\(n^2\))	稳定	O(1)	大部分已排序时较好
基数排序	O(n × k)	O(n × k)	稳定	O(n)	k 是 “桶” 的个数
Shell 排序	O(\(nlog_2n\))	O(\(nlog_2^2n\))	不稳定	O(1)	n 大时较好
快速排序	O(\(nlog_2n\))	O(\(n^2\))	不稳定	O(n㏒n)	n 大时较好
归并排序	O(\(nlog_2n\))	O(\(nlog_2n\))	稳定	O(1)	n 小时较好
堆排序	O(\(nlog_2n\))	O(\(nlog_2n\))	不稳定	O(1)	n 大时较好

稳定性：排序后，那些原本相等元素的相对顺序不改变

5.2.2 冒泡排序

冒泡排序：通过对待排序序列从左向右遍历，依次比较相邻元素的值。若发现前面的值比后面的值大则交换。

如此，各元素不断接近自己的位置。值较大的元素逐渐向后移动，就像水下的气泡一样逐渐上浮。

特别地：如果在某次排序中没有发生过任何交换，则此时是已完成排序，可提前结束排序过程。

public class test {

    public static void main(String[] args) {
        int arr[] = {52,16,32,88,64};
        int temp = 0;
        for( int i = 0; i < arr.length - 1; i++) {//外层循环是 4 次
            for( int j = 0; j < arr.length - 1 - i; j++) {//4 次比较-3 次-2 次-1 次
                //如果前面的数>后面的数，就交换
                if(arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            System.out.println("\n==第"+(i+1)+"轮==");
            for(int j = 0; j < arr.length; j++) {
                System.out.print(arr[j] + "\t");

            }
        }
    }
}

*5.2.3 选择排序……

5.3 查找算法

在 Java 中，常用的查找有 4 种：

• 顺序查找（遍历）
• 二分查找
• 插值查找
• 斐波那契查找

5.3.1 线性查找

逐一比对，直到发现目标值

public static int seqSearch(int[] array, int target) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == target) return i;
    }
    return -1;
}

import java.util.Scanner;
public class test {
    //编写一个 main 方法
    public static void main(String[] args) {
        /*
        有一个数列：白眉鹰王、金毛狮王、紫衫龙王、青翼蝠王猜数游戏：
        从键盘中任意输入一个名称，判断数列中是否包含此名称【顺序查找】
        要求: 如果找到了，就提示找到，并给出下标值
        思路分析
        1. 定义一个字符串数组
        2. 接收用户输入, 遍历数组，逐一比较，如果有，则提示信息，并退出
        */
        
        //定义一个字符串数组
        String[] names = {"白眉鹰王", "金毛狮王", "紫衫龙王", "青翼蝠王"};
        Scanner myScanner = new Scanner(System.in);
        System.out.println("请输入名字");
        String findName = myScanner.next();
        //遍历数组，逐一比较，如果有，则提示信息，并退出
        //这里老师给大家一个编程思想/技巧, 一个经典的方法
        int index = -1;
        for(int i = 0; i < names.length; i++) {
        //比较 字符串比较 equals, 如果要找到名字就是当前元素
            if(findName.equals(names[i])) {
                System.out.println("恭喜你找到 " + findName);
                System.out.println("下标为= " + i);
        //把 i 保存到 index
                index = i;
                break;//退出
            }
        }
        if(index == -1) { //没有找到
            System.out.println("sorry ,没有找到 " + findName);
        }

    }
}

*5.3.2 二分查找

二分查找要求数组必须是有序数组。

递归方式二分查找：

public static int binarySearch(int[] array, int target) {
    return binarySearch(array, target, 0, array.length);
}

public static int binarySearch(int[] array, int target, int l, int r) {
    if (l >= r) return -l - 1;
    int p = (l + r) / 2;
    if (target == array[p]) return p;
    else if (target > array[p]) {
        return binarySearch(array, target, p + 1, r);
    } else return binarySearch(array, target, l, p - 1);
}

非递归方式二分查找：

public static int binarySearch2(int[] array, int target) {
    int l = 0;
    int r = array.length;
    while (r > l) {
        int p = (r + l) / 2;
        if (target == array[p]) return p;
        else if (target > array[p]) l = p + 1;
        else r = p - 1;
    }
    return -l - 1;
}

*5.3.3 插值查找

插值查找类似于二分查找，但其不是取出中位数，而是从自适应的位置取出一个元素

public static int insertSearch(int[] array, int target) {
    if (target > array[array.length - 1]) return -array.length;
    else if (target < array[0]) return 0;
    int l = 0;
    int r = array.length;
    int p = 0;
    while (r >= l) {
        p = l + (target - array[l]) * (r - 1 - l) / (array[r - 1] - array[l]);
        if (target == array[p]) return p;
        else if (target > array[p]) l = p + 1;
        else r = p - 1;
    }
    return -p;
}

*5.3.4 斐波那契查找

斐波那契查找原理与前两种类似，仅仅改变了中间节点的位置。其中间节点不是中位或插值，而是位于黄金分割点附近。

5.4 二维数组

public class test {
    
    public static void main(String[] args) {
        /*
        请用二维数组输出如下图形
        0 0 0 0 0 0
        0 0 1 0 0 0
        0 2 0 3 0 0
        0 0 0 0 0 0
        */
        //什么是二维数组：
        //1. 从定义形式上看 int[][]
        //2. 可以这样理解，原来的一维数组的每个元素是一维数组, 就构成二维数组
        int[][] arr = {{0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 2, 0, 3, 0, 0}, {0, 0, 0, 0, 0, 0} };
        //关于二维数组的关键概念
        //(1)
        System.out.println("二维数组的元素个数=" + arr.length);
        //(2) 二维数组的每个元素是一维数组, 所以如果需要得到每个一维数组的值还需要再次遍历
        //(3) 如果我们要访问第 (i+1)个一维数组的第 j+1 个值 arr[i][j];
        // 举例 访问 3, =》 他是第 3 个一维数组的第 4 个值 arr[2][3]
        System.out.println("第 3 个一维数组的第 4 个值=" + arr[2][3]); 
		//3. 输出二维图形
        for(int i = 0; i < arr.length; i++) {//遍历二维数组的每个元素
        //1. arr[i] 表示 二维数组的第 i+1 个元素 比如 arr[0]：二维数组的第一个元素
        //2. arr[i].length 得到 对应的 每个一维数组的长度
            for(int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " "); //输出了一维数组
            }
            System.out.println();//换行
        }
    }
}

int[][] ints;					// 声明一个二维数组
int[] ints2[];					// 也能这样声明
int ints3[][];					// 这样也行
int[] x,y[];					// 声明了两个数组，一个是 int[] x 一个是 int[][] y
								// 把 int[] 视作一个类型，就能很好地理解这个写法

二维数组实际是由多个一维数组组成的，它的各个元素的长度可以相同，也可以不同。

数组是一个对象，所以二维数组的元素存放的是一维数组的地址。

二维数组构造方法

• 构造方法1：动态初始化

  int[][] a = new int[3][4]	// 创建 有3个 包含4个元素的一维数组 的二维数组
  int a[][] = new int[3][4]

• 构造方法2：动态初始化

  double[][] many_doubles;			// 先声明变量
  many_doubles = new double[3][4];	// 再开辟空间

• 构造方法3：动态初始化-列数不确定

  int[][] arr = new int[3][];//创建 二维数组，一个有 3 个一维数组，但是每个一维数组还没有开数据空间
  
  for(int i = 0; i < arr.length; i++) {//遍历 arr 每个一维数组
      //给每个一维数组开空间 new
      //如果没有给一维数组 new ,那么 arr[i]就是 null
  	arr[i] = new int[i + 1];
  	//遍历一维数组，并给一维数组的每个元素赋值
  	for(int j = 0; j < arr[i].length; j++) {
  		arr[i][j] = i + 1;//赋值
  	}
  }

• 构造方法4：静态初始化

  int[][] m = {{1, 3}, {4, 10, 2}, {95}};

二维数组使用方法

• arr.length：该二维数组的长度
• arr[0]：该二维数组的第一个子数组
• arr[0].length：该二维数组的第一个子数组的长度
• arr[1][0]：该二维数组第二个子数组的第一个元素的值

5.5 一些题目

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

public class test {

    public static void main(String[] args) {
        int[] arr = {10, 12, 45, 90};
        int insertNum = 23;
        int index = -1;
		
        //先定位到应该插入的位置
        for(int i = 0; i < arr.length; i++){
            if(insertNum < arr[i]){
                index = i;
                break;
            }
        }
        if(index == -1){
            index = arr.length;
        }

        System.out.println("应该插入的位置,arr[i]中的i为：" + index);

		//然后扩容数组
        int[] arrNew = new int[arr.length + 1];
        for(int i = 0,j = 0; i < arrNew.length; i++){   //这里的j很巧妙
            if(index != i){
                arrNew[i] = arr[j];
                j++;
            }
            else{
                arrNew[index] = insertNum;
            }
        }

        System.out.println("下面即为定位+扩容后的数组：");
        for(int i = 0; i < arrNew.length; i++){
            System.out.print(arrNew[i] + "\t" );
        }

    }
}