Java 数组、排序和查找

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

即：数组就是一组数据。

一维数组

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

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

数组的下标从 0 开始。且必须在指定范围内使用，否则报错。

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

数组创建后，如果没有赋值，有默认值：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.使用数组

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

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

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

    1
    2
    3
    char[] chars;							// 先声明数组 name，此时数组是 null
    chars = new char[2];					// 分配内存空间，可以存放数据了
    chars[1] = '\t';

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

    1
    2
    boolean[] bools = {true, false, true, false};
    String[] strs = new String[]{"阿伟，你又在打电动噢", "烦啦"};

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

数组的使用方法：

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

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

  • 数组长度：数组名.length

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

数组赋值机制

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

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

    1
    2
    3
    int[] array1 = {0, 0, 0};
    int[] array2 = array1;
    array2[0] = 100;

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

    1
    2
    3
    4
    5
    6
    int[] array1 = {0, 0, 0};
    int[] array2 = new int[array1.length];
    for (int i = 0;i < array1.length;i++) {
        array2[i] = array1[i];
    }
    //同 int[] array2 = Arrays.copyOf(array1,array1.length);

    上述方式拷贝后，两数组相互独立。

数组的扩容

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

以下是一个扩容方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.Scanner;
public class Code5_1_3{

	public static void main(String[] args){

		Scanner inP = new Scanner(System.in);
		int[] arr1 = {1, 2, 3};		// 这是原数组
		int add = 0;				// 这个变量记录输入的新元素的值
		int count = arr1.length;	// 这个变量是新数组的长度
		char yN = 'a';				// 记录询问继续与否时用户的输入字符

		do{
       	/* 创建多一位的新数组，把新元素赋给新数组的最后一位 */
				System.out.println("请输入添加数字：");
				add = inP.nextInt();
				int[] tem = new int[arr1.length + 1];
				tem[count] = add;

       	/* 把旧数组的值全部赋给新数组 */
				for(int i = 0; i < arr1.length; i++){
					tem[i] = arr1[i];
				}

       	/* 把新数组保存下来，输出现在的数组 */
				arr1 = tem;
				count++;
				System.out.println("\n\n当前数组为：");

				for(int i = 0; i < arr1.length; i++){
					System.out.print(arr1[i] + " ");
				}

       	/* 询问是否继续添加，输入n跳出，否则循环 */
				System.out.println("\n\n是否继续添加？（Y/N）");
				yN = inP.next().charAt(0);

		}while(yN != 'N' && yN != 'n');

	}
}

二维（多维）数组

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

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

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

二维数组构造方法：

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

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

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

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

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

    1
    2
    3
    4
    char[][] many_chars = new char[3][];	// 创建一个三行列数不确定的二维数组
    for (int i = 0; i < 3; i++) {
        many_chars[i] = new char[i + 1];	// 此时，每个数组空间依次增大
    }

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

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

二维数组使用方法：

  • ints.length：该二维数组的长度，这里是 3
  • ints[0]：该二维数组的第一个子数组
  • ints[0].length：该二维数组的第一个子数组的长度，这里是 4
  • ints[1][0]：该二维数组第二个子数组的第一个元素的值，这里是 21

多维数组（不规则数组）：

  • Java实际上没有多维数组，只有一维数组。多维数组被解释为数组的数组。
  • 由于Java可以单独地访问数组的某一行，所以可以让两行交换

查找算法

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

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

线性查找

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

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

二分查找

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

每次取出那个中位数。目标值大于中位数的场合，则在较小一侧的范围内继续二分查找。否则在那个较大一侧查找。

递归方式二分查找：

1
2
3
4
5
6
7
8
9
10
11
12
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);
}

非递归方式二分查找：

1
2
3
4
5
6
7
8
9
10
11
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;
}

插值查找

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

那个自适应的取出位置 mid = low + (target - arr[low]) × (high - low) / (arr[high] - arr[low])

如若那个目标值更靠近某一端，这个自适应的取出位置也会更接近那一端

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

斐波那契查找

斐波那契查找原理与前两种类似，仅仅改变了中间节点的位置。

其中间节点不是中位或插值，而是位于黄金分割点附近。

排序算法

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

排序分为两类：

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

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

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

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

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

排序算法的时间复杂度：

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

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

冒泡排序

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void bubble_sort(int[] array) {
    /* 共执行 n - 1 轮排序 */
    for(int count = 1; count < array.length; count++){
        boolean non_exchange = true;	// 该轮排序进行了交换时变为 false
        /* 每轮遍历 n - count 次 */
        for(int n = 0; n < array.length - count; n++){
            /* 当比较时，如果逆序，则交换 */
            if(array[n] > array[n + 1]){
                non_exchange = false;
                int temp = array[n + 1];
                array[n + 1] = array[n];
                array[n] = temp;
            }
        }

        /* 如果没有交换过，则提前结束排序过程 */
        if (non_exchange) break;
    }
}

如果有 n 个元素，就进行 n - 1 轮排序，第 k 轮排序比较 n - k 个元素，并进行最多 n - k 次交换。时间复杂度为 O(n2)

对随机数组 int[] array（array.length = 80000；array[i] ∊ [0, 107)）进行冒泡排序。

选择排序

选择排序：从待排序序列中，按指定规则选出某一元素，再依照规定交换位置后达到排序目的。

从待排序序列中找出最小值，与下标 0 位置元素交换。之后在剩余元素中找出最小值，与下标 1 元素交换。以此类推，直到完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void choice_sort(int[] array) {
    for (int p = 0; p < array.length - 1; p++) {
        int min_index = p;		// loc 指向那个当前找到的最小值的下标
        /* 找出当前剩余元素中的最小值 */
        for (int n = p + 1; n < array.length; n++) {
            if (array[n] < array[min_index]) min_index = n;
        }
        /* 将找到的最小值与对应位置元素交换 */
        if (min_index != p) {
            int temp = array[min_index];
            array[min_index] = array[p];
            array[p] = temp;
        }
    }
}

如果有 n 个元素，就进行 n - 1 轮排序，第 k 轮排序比较 n - k 个元素，并进行 1 次交换。时间复杂度为 O(n2)

对随机数组 int[] array（array.length = 80000；array[i] ∊ [0, 107)）进行选择排序。

插入排序

插入排序：在待排序序列中的元素，以插入的方式找寻该元素的适当位置，以达到排序目的。

将待排序序列的元素视为一个有序表和一个无序表。起初，有序表中只有一个元素，无序表中有 n - 1 个元素。

排序过程中每次从 无序表中取出第一个元素，把它依次与有序表元素进行比较，确定其在有序表的位置，将其插入有序表 ，成为新的有序表 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void insert_sort(int[] array) {
    /* 数组的前一部分视为有序表，后一部分视为无序表 */
    for (int p = 1; p < array.length; p++) {
        int temp = array[p];	// 那个 无序表首元素 的值
        int insertPos = p;		// 那个 无序表首元素 在有序表的位置
        
        /* 逆向遍历那个有序表，以确定该无序表首元素在有序表的位置。
        	到达位置前，将有序表的插入位置后的元素后移 */
        for (int n = p - 1; n >= 0; n--) {
            if (array[n] < temp) break;
            array[n + 1] = array[n];
            insertPos--;
        }
        /* 将该元素插入指定位置 */
        array[insertPos] = temp;
    }
}

如果有 n 个元素，就进行 n - 1 轮排序，第 k 轮排序需要进行 k 次比较、移动或插入。时间复杂度为 O(n2)

对随机数组 int[] array（array.length = 80000；array[i] ∊ [0, 107)）进行插入排序。

希儿排序

希儿排序：是希儿通过在量子之海中领悟事物的演变模式，于 1959 年提出的一种排序算法。

希儿排序也是一种插入排序，是简单插入排序的高效改进版。也称为：缩小增量排序。

希儿排序是把待排序序列按下标的一定步长进行分组，对每组使用插入排序法。随着步长逐渐减少，每组包含的元素个数也越来越多。

当步长减至 1 时，整个待排序序列恰被分为 1 组，算法便中止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static void seele_sort(int[] array) {
    int step = array.length / 2;		// 步长。该值等于分组数量
    
    /* 初始将数组为 2 数一组，那么每组的步长就是 array.length / 2
    	步长是那个分组中，相邻两个数的下标间隔。步长的值也等于组数
    	直到那个分组大小等于原序列，也就是步长 == 1 时，进行最后一次排序 */
    while (step >= 1) {
        
        /* 一共有 step 组，对每一组都进行一次完整的插入排序 */
        for (int group = 0; group < step; group++) {
            
            /* 每一组中，下一个元素的下标是：当前下标 + step
            	每组的起始下标是 group，根据插入排序法，将每组视为有序表和无序表
            	那个无序表从每组第二个元素开始计数，也就是下标 group + step */
            for (int toSort = group + step; toSort < array.length; toSort += step) {
                int insertPos = toSort;
                int temp;
                /* 已经有序时直接 continue */
                if ((temp = array[toSort]) >= array[toSort - step]) continue;
                /* 寻找插入位置。在找到位置前，移动那些有序表元素 */
                for (int exPos = toSort - step; exPos >= group; exPos -= step) {
                        if (array[exPos] < temp) break;
                        array[exPos + step] = array[exPos];
                        insertPos -= step;
                    }
                /* 执行插入 */
                array[insertPos] = temp;
            }
        }
        /* 每轮循环后，分组容量变为 2 倍，那么步长就会变为一半 */
        step /= 2;
    }
}

如果有 n 个元素，就进行 ㏒2n 次排序。每轮排序最多进行 k*n 次比较、移动或插入。因此，时间复杂度为 O(n㏒2n)

对随机数组 int[] array（array.length = 80000；array[i] ∊ [0, 107)）进行希儿排序。

快速排序

快速排序：是对冒泡排序的一种改进。通过一趟排序，将待排序序列分割成独立的两部分，其中一部分的所有数据都比另一部分小，再按此方法对这两部分数据分别进行快速排序。

整个排序过程可以递归进行，最终使整个数据变成有序序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static void quick_sort(int[] array) {
    quick_sort(array, 0, array.length);
}

private static void quick_sort(int[] array, int start, int end) {
    if (start == end) return;
    int key = array[end - 1];			// 将最后一个值取出作为比较值
    int l = start;						// 左指针
    int r = end;						// 右指针
    /* 遍历指定区间，将那些较小值放到左侧，较大值放到右侧 */
    for (int i = start; i < r; ) {
        if (array[i] < key) {
            array[l++] = array[i];
        } else if (array[i] > key) {
            int temp = array[--r];
            array[r] = array[i];
            array[i] = temp;
            continue;
        }
        i++;
    }
    /* key 值可能重复，那些左右指针间的空位置都是 key 值 */
    for (int i = l; i < r; i++) {
        array[i] = key;
    }
    quick_sort(array, start, l);		// 对那个较小侧区间再进行快速排序
    quick_sort(array, r, end);			// 对那个较大测区间再进行快速排序
}

如果有 n 个元素，就进行 ㏒2n ~ n 次排序。第 k 轮排序最多进行 2n - 2k - 1 次比较、交换或插入。因此，时间复杂度为 O(n㏒2n)，最差情况为 O(n2)

对随机数组 int[] array（array.length = 80000；array[i] ∊ [0, 107)）进行快速排序。

归并排序

归并排序：利用归并的思想实现的排序方法。该算法采用经典的分治策略（将问题分解成几个小问题，然后分而治之）。

对 2 个元素进行比较、排序，是很容易的。对 2 个有序序列，将其合并为新的有序序列，也是容易的。

因此，我们把待排序序列分成许多组，每组包含 2 个元素，并对每组进行排序。再逐渐合并那些组，最终就能得到一个完整的有序序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public static void merger_sort(int[] array) {
    int tl = (int) Math.ceil(array.length / 2.0);
    int[][] temp = new int[tl][];
    for (int i = 0; ; i += 2) {
        if (i == array.length) {
            if (i == array.length + 1) temp[i / 2] = new int[]{array[i - 1]};
            break;
        } else {
            if (array[i] > array[i + 1]) {
                temp[i / 2] = new int[]{array[i + 1], array[i]};
            } else {
                temp[i / 2] = new int[]{array[i], array[i + 1]};
            }
        }
    }
    while (temp.length != 1) {
        temp = combine(temp);
    }
    System.arraycopy(temp[0], 0, array, 0, array.length);
}

private static int[][] combine(int[][] temp) {
    int tl = (int) Math.ceil(temp.length / 2.0);
    int[][] tt = new int[tl][];
    for (int i = 0; i < tt.length; i++) {
        int tp = 2 * i;
        if (tp + 1 >= temp.length) tt[i] = temp[tp];
        else tt[i] = combine(temp[tp], temp[tp + 1]);
    }
    return tt;
}

private static int[] combine(int[] a, int[] b) {
    int[] ret = new int[a.length + b.length];
    int ap = 0;
    int bp = 0;
    int rp = 0;
    while (true) {
        if (ap >= a.length) {
            while (bp < b.length) {
                ret[rp++] = b[bp++];
            }
            break;
        } else if (bp >= b.length) {
            while (ap < a.length) {
                ret[rp++] = a[ap++];
            }
            break;
        } else if (a[ap] > b[bp]) {
            ret[rp++] = b[bp++];
        } else {
            ret[rp++] = a[ap++];
        }
    }
    return ret;
}

如果有 n 个元素，就进行 ㏒2n ~ n 次排序。每轮排序最多进行 2n 次比较或插入。因此，时间复杂度为 O(n㏒2n)

对随机数组 int[] array（array.length = 80000；array[i] ∊ [0, 107)）进行归并排序。

基数排序

基数排序：属于分配式排序（又称 “桶排序”。顾名思义，通过键值各个位的值，将待排序序列的元素分配至某些桶中，达到排序的作用）。基数排序是经典的空间换时间的算法。

基数排序法是桶排序的扩展。将整数按照位数切割成不同数字，然后按照每个位数分别比较。

该方法只能用于比较正数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void radix_sort(int[] array) {
    int[][] bucket = new int[10][array.length];
    int sub = 1;
    int border = 9;
    int[] p = new int[10];
    while (true) {
        boolean noMore = true;
        for (int i :array) {
            int pos = (i / sub) % 10;
            bucket[pos][p[pos]++] = i;
            if (i > border) noMore = false;
        }
        int n = 0;
        for (int i = 0; i < 10; i++) {
            int j = 0;
            while (p[i] > 0) {
                array[n++] = bucket[i][j++];
                --p[i];
            }
        }
        sub *= 10;
        border = 10 * sub - 1;
        if (noMore) break;
    }
}

根据那个最大数值的不同，需要进行 r 轮排序。每轮排序进行 3n 次计算、插入。因此，时间复杂度是 O(n㏒RB)

对随机数组 int[] array（array.length = 80000；array[i] ∊ [0, 107)）进行基数排序。

堆排序

堆排序：利用 堆 数据结构而设计的一种排序算法。堆排序是一种选择排序，也是一种不稳定排序。

堆 是具有以下性质的二叉树：

  • 大顶堆：每个节点的值都大于等于其子节点的值

    即，对于任意节点 arr[i] 都有 arr[i] >= arr[2 * i + 1] 并且 arr[i] >= arr[2 * i + 2]

  • 小顶堆：每个节点的值都小于等于其子节点的值

    即，对于任意节点 arr[i] 都有 arr[i] <= arr[2 * i + 1] 并且 arr[i] <= arr[2 * i + 2]

  1. 将 待排序序列 构成一个 大顶堆（数组形式）

    从最后一个非叶节点开始，从左至右，从下至上进行调整。

    调整时如果乱序，则将子节点中较大方的值与该节点交换即可。交换后，那些子节点乱序的场合也要依次调整。

    调整完成后，就得到了一个 大顶堆。

  2. 此时，堆顶元素即整个序列的最大值。将其 与队列末尾元素交换。

  3. 对剩余元素进行调整，使其恢复成 大顶堆。

  4. 重复上述步骤，就得到了有序序列。

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static void heap_sort(int[] array) {
    int len = array.length;
    for (int j = array.length / 2 + 1; j >= 0; j--) {
        heap_help(array, j, len);
    }
    heap_swap(array, --len);
    while (len > 1) {
        int tar = len;
        while (tar > 0) {
            tar = (tar - 1) / 2;
            heap_help(array, tar, len);
        }
        heap_swap(array, --len);
    }
}

private static void heap_help(int[] array, int tar, int length) {
    int temp = array[tar];
    for (int i = tar * 2 + 1; i < length; i = i * 2 + 1) {
        if (i < length - 1 && array[i] < array[i + 1]) i++;
        if (array[i] > temp) {
            array[tar] = array[i];
            tar = i;
        } else {
            break;
        }
    }
    array[tar] = temp;
}

private static void heap_swap(int[] array, int index) {
    int temp = array[0];
    array[0] = array[index];
    array[index] = temp;
}

对随机数组 int[] array（array.length = 80000；array[i] ∊ [0, 107)）进行堆排序。