排序算法汇总III

发表于 分类于 本文字数： 8.2k 阅读时长 ≈ 7 分钟

排序算法汇总 III

计数排序

计数排序就是一种时间复杂度 O(n) 的排序算法，对一定范围内的整数排序时，它的复杂度为O(n+k) 【其中 k 是整数的范围大小】

例如：我们需要对一列数组排序，这个数组中每个元素都是【1，9】区间内的整数。那么我们可以构建一个长度为9 的数组用于计算。记数数组的下标分别对应区间内的 9 个整数。然后遍历待排序的数组，将区间的每个整数出现的次数统计到计数数组中对应下标的位置。然后遍历计数数组，将每个元素输出，输出的次数就是对应位置记录的次数

算法实现如下 （以【1，9】为例）

  • 伪计数排序
    代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public static void countingSort(int[] arr){
    	// 建立长度为 9 的数组，下标 0~8 对应数字 1~9
    	int[] counting = new int[9];
    	// 遍历 arr 中的每个元素
    	for(int element: arr){
    		// 将每个整数出现的次数统计到计数数组中对应下标的位置
    		counting[element-1] ++ ;
    	}
    	int index = 0;
    	// 遍历计数数组，将每个元素输出
    	for(int i=0;i<9;i++){
    		// 输出的次数就是对应位置记录的次数
    		while(counting[i] != 0){
    			arr[index++] = i+1 ;
    			counting[i]-- ;
    		}
    	}
    }

    在纯数字排序中，这个方式看起来无伤大雅，但在实际工作中，这样的排序算法几乎无法使用。因为被排序的对象往往都会携带其他的属性，但这份算法将被排序对象的其他属性都丢失了。
    就好比业务部门要求我们将 11 号商品，22 号商品，33 号商品，44 号商品按照价格排序，它们的价格分别为 88 元、66 元，66 元，99 元。 我们告诉业务部门：排序完成后价格为 66 元、 66 元、88 元，99 元，但不知道这些价格对应哪个商品。这显然是不可接受的。

  • 伪计数排序 2.0
    在统计元素出现的次数时，同时把真实的元素保存到列表中，输出时，从列表中取真实的元素。算法实现如下：

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 countingSort9(int[] arr) {
    // 建立长度为 9 的数组，下标 0~8 对应数字 1~9
    int[] counting = new int[9];
    // 记录每个下标中包含的真实元素，使用队列可以保证排序的稳定性
    HashMap<Integer , Queue<Integer>> records = new HashMap<>() ;
    //遍历 arr 中的元素
    for(int element :arr){
    	// 将每个整数出现的次数统计到计数数组中对应下标的位置
        counting[element - 1]++;
        if(!records.containsKey(element - 1)){
        	records.put(element - 1,new LinkedList<>());
        }
        records.get(element-1).add(element);
    }
    int idx = 0;
    // 遍历计数数组，将每个元素输出
    for(int i=0 ; i<9 ; i++){
    	//输出的次数就是对应位置记录的次数
    	while(counting[i] != 0){
    		// 输出记录的真实元素
    		arr[index++] = records.get(i).remove();
    		counting[i]-- ;
    	}
    }
}

通过队列来保存真实的元素,可以保证排序算法的稳定性。

真正的计数排序

举个例子，班上有 10 名同学：他们的考试成绩分别是：7, 8, 9, 7, 6, 7, 6, 8, 6,6，他们需要按照成绩从低到高坐到 0～9 共 10 个位置上。
一过程需要以下几步：

  1. 计数，统计出4 名同学考了 6 分，3 名同学考了 7 分，2 名同学考了 8 分，1 名同学考了 9 分；
  2. 从头遍历数组，第一名同学考了 7 分，共有 4 个人比他分数低，所以第一名同学排在了4号位置 （也就是第5 个）
  3. 第二名同学考了 8 分，共有 7 个人（4 + 3）比他分数低，所以第二名同学坐在 7 号位置；
  4. 第三名同学考了 9 分，共有 9 个人（4 + 3 + 2）比他分数低，所以第三名同学坐在 9 号位置；
    …依次完成整个排序
    【区别就在于计数排序并不是把计数数组的下标直接作为结果输出，而是通过计数的结果，计算出每个元素在排序完成后的位置，然后将元素赋值到对应位置。】

代码如下：

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
public static void countingSort9(int[] arr) {
    // 建立长度为 9 的数组，下标 0~8 对应数字 1~9
    int[] counting = new int[9];
    for (int element : arr) {
        // 将每个整数出现的次数统计到计数数组中对应下标的位置
        counting[element - 1]++;
    }
		// 记录前面比自己小的数字的总数
	int preCounts = 0;
	for(int i=0 ; i<counting.length; i++){
		int temp = countings[i];
		// 将 counting 计算成当前数字在结果中的起始下标位置。位置 = 前面比自己小的数字的总数。
		countings[i] = preCounts;
		// 当前的数字比下一个数字小，累计到 preCounts 中
		preCounts += temp;
	}
	int[] res = new int[arr.length];
	for (int element : arr) {
        // counting[element - 1] 表示此元素在结果数组中的下标
        int index = counting[element - 1];
        result[index] = element;
        // 更新 counting[element - 1]，指向此元素的下一个下标
        counting[element - 1]++;
    }
    // 将结果赋值回 arr
    for (int i = 0; i < arr.length; i++) {
        arr[i] = result[i];
    }

}

桶排序

思想：

  • 将区间划分为 n 个相同大小的区间，每个区间成为一个桶；
  • 遍历数组，将每个数字装入桶中。
  • 对每个桶内的数字单独排序，这里可以使用其他排序算法
  • 最后按照排序将所有桶内的数字合并起来

使用桶排序算法时，我们需要考虑两个因素：

  • 设置多少个桶合适
  • 桶采用哪种数据结构
  1. 以数组作为桶
    首先找到最大值和最小值
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public static void bucketSort(int[] arr){
    	// 防空和防止数组越界
    	if(arr == null || arr.length<=1) return ;
    	// 找到最大值，最小值
    	int max = arr[0];
    	int min = arr[0];
    	for(int i=1;i<arr.length;i++){
    		if(arr[i]>max) max = arr[i];
    		else if(arr[i]<min) min = arr[i];
    	}
    	// 确定取值范围
    	int range = max - min;
    	//...
    }

这里需要遍历一轮数组。
下一步，开始装桶：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 设置桶的数量，这里我们设为 100个，根据实际情况修改。
int bucketAmount = 100;
// 桶和桶之间的间距
double gap = range * 1.0/(bucketAmount-1) ;
// 用二维数组来装桶，第一个维度是桶的编号，第二个是桶中的数字。
int[][] buckets = new int[bucketAmount][arr.length];
// 单独采用一个数组来记录每个桶当前的长度，也就是桶内有多少个数字。
int[] bucketLength = new int[bucketAmount];

//装桶
for(int value : arr){
	// 找到value 属于哪个桶
	int index = (int)((value - min)/gap) ;
	// 装桶后，更新bucketLength[index]
}

说明：
我们将桶的数量设置为 100100 个，这个值可以根据输入数据的实际情况修改。所有的桶是一个二维数组，第一个维度代表桶的编号，第二个维度代表桶内的数字，每个桶中都有一组数字。

由于每个桶的长度都等于待排序数组的长度，所以我们还需要一个单独的数组来记录当前桶内的有效数字数量。

装桶时需要做一些简单的运算：先通过第一步找到的取值范围计算出每个桶之间的间距，再通过当前数字与最小值的距离除以间距计算出桶的编号，最后根据编号把当前数字放入对应的桶中。

下一步是对每个桶内的数字进行单独排序，这一步需要借助其他排序算法：

1
2
3
4
5
6
7
8
9
10
11
12
// 对桶内的数字单独排序
int index = 0;
for(int i = 0; i<bucketAmount ;i++){
	if(bucketLength[i] == 0) continue;
	// 取出桶内的数组
	int[] arrInBucket = Arrays.copyOf(buckets[i],bucketLength[i]);
	// 这里需要结合其他排序算法，例如：插入排序
	insertSort(arrInBucket);
	// 排序完成后将桶内的结果收集起来
	System.arraycopy(arrInBucket,0,arr,index,bucketLength[i]);
	index += bucketLength[i];
}

我们以插入排序为例，　insertSort　函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 插入排序
public static void insertSort(int[] arr){
	// 从第二个数开始，往前插入数字
	for(int i = 1;i< arr.length;i++)}{
		int cur = arr[i];
		int j = i-1;
		// 寻找插入位置的过程中，不断地将比 currentNumber 大的数字向后挪
		while(j >=0 && cur<arr[j]){
			arr[i+1] = arr[j];
			j-- ;
		}
		arr[j+1] = cur;

	}
}

这就是以数组作为桶实现的桶排序，它最大的缺点就是每个桶都和待排序数组一样长，非常消耗内存，容易导致「超出内存限制」错误。

完整代码如下：

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
public static void bucketSort(int[] arr){
	if(arr==null || arr.length<=1) return ;
	int max = arr[0];
	int min = arr[0];
	for(int i=1; i<arr.length;i++){
		if(arr[i]>max) max = arr[i];
		else if(arr[i]<min) min = arr[i];
	}
	int range = max-min;
	int bucketAmount = 100;
	double gap = range * 1.0/(bucketAmount-1);
	// 用二维数组来装桶，第一个维度是桶的编号，第二个维度是桶中的数字。初始化长度为 0
    int[][] buckets = new int[bucketAmount][];
    // 装桶
    for(int val:arr){
    	int idx = (int) ((value-min) / gap);
    	buckets[index] = add(buckets[idx] ,val);
    }
    int index = 0;
    // 对每个桶内的数字进行单独排序
    for(int i=0;i<bucketAmount;i++){
    	if(buckets[i]==null || buckets[i].length == 0) continue;
    	insertSort(buckets[i]);
    	// 排序完成后把桶内的结果收集起来
    	System.arraycopy(buckets[i],0,arr,idx,buckets[i].length);
    	idx+= buckets[i].length;
    }
}

// 数组扩容
public static int[] add(int[] arr, int num) {
    if (arr == null) return new int[]{num};
    int[] newArr = Arrays.copyOf(arr, arr.length + 1);
    newArr[arr.length] = num;
    return newArr;
}

// 插入排序
public static void insertSort(int[] arr) {
    // 从第二个数开始，往前插入数字
    for (int i = 1; i < arr.length; i++) {
        int currentNumber = arr[i];
        int j = i - 1;
        // 寻找插入位置的过程中，不断地将比 currentNumber 大的数字向后挪
        while (j >= 0 && currentNumber < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 两种情况会跳出循环：1. 遇到一个小于或等于 currentNumber 的数字，跳出循环，currentNumber 就坐到它后面。
        // 2. 已经走到数列头部，仍然没有遇到小于或等于 currentNumber 的数字，也会跳出循环，此时 j 等于 -1，currentNumber 就坐到数列头部。
        arr[j + 1] = currentNumber;
    }
}

这里的扩容算法和 ArrayList 扩容很相似，先开辟一个更长的新数组，并将原数组拷贝过来，再加入新数字。但 ArrayList 扩容时，数组长度是先从 00 扩容到 1010，后续再不断乘以 1.51.5 倍，这会造成一定的内存浪费。

  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
    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 bucketSort(int[] arr) {
        // 判空及防止数组越界
        if (arr == null || arr.length <= 1) return;
        // 找到最大值，最小值
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) max = arr[i];
            else if (arr[i] < min) min = arr[i];
        }
        // 确定取值范围
        int range = max - min;
        // 设置桶的数量，这里我们设置为 100 个，可以任意修改。
        int bucketAmount = 100;
        // 桶和桶之间的间距
        double gap = range * 1.0 / (bucketAmount - 1);

        HashMap<Integer,LinkedList<Integer>> buckets = new HashMap<>();

        // 装桶
        for(int val: arr){
        	int index = (int)((val-min) / gap);
        	if(!buckets.containsKey(index)){
        		buckets.put(index,new LinkedList<>());
        	}
        	buckets.get(index).add(val);
        }

        int index = 0;
        //对每个桶内的数字进行单独排序
        for(int i =0 ;i<bucketAmount;i++){
        	LinkedList<Integer> bucket = buckets.get(i);
        	if(bucket == null) continue;
        	insertSort(bucket);
        	// 排序完成后将桶内的结果收集起来
        	for(int num : bucket){
        		arr[index++] = num;
        	}
        }
        // 对链表插入排序
    public static void insertSort(LinkedList<Integer> arr) {
        // 从第二个数开始，往前插入数字
        for (int i = 1; i < arr.size(); i++) {
            int currentNumber = arr.get(i);
            int j = i - 1;
            // 寻找插入位置的过程中，不断地将比 currentNumber 大的数字向后挪
            while (j >= 0 && currentNumber < arr.get(j)) {
                arr.set(j + 1, arr.get(j));
                j--;
            }
            // 两种情况会跳出循环：1. 遇到一个小于或等于 currentNumber 的数字，跳出循环，currentNumber 就坐到它后面。
            // 2. 已经走到数列头部，仍然没有遇到小于或等于 currentNumber 的数字，也会跳出循环，此时 j 等于 -1，currentNumber 就坐到数列头部。
            arr.set(j + 1, currentNumber);
        }
    }

    首先，我们仍然是找到数组中的最大值和最小值，确定出数据的取值范围，然后划分 100100 个桶，计算出间距。并且把所有的数字都放入 LinkedList 链表中。装桶后，再对链表进行插入排序即可。

采用 LinkedList，装桶时不会有额外的空间浪费，但装桶后排序会比较耗时，因为访问 LinkedList 链表时，get 和 set 方法都需要从链表头部开始，逐个向后寻找结点，效率较低。
使用链表排序还有一个问题：由于链表中不能存储基本类型，所以我们不得不将链表类型声明为 LinkedList，int 和 Integer 互相转换的过程被称为 「装箱」和「拆箱」，这也会造成额外的性能消耗。

  1. 折中的方案： 装桶时用链表，桶内排序用数组

装桶时使用 LinkedList，避免扩容问题，桶内排序时将链表转换为数组，再进行排序，避免 LinkedList 排序较慢的问题和大量 「装箱」和「拆箱」的性能消耗（整个链表中的 Integer 都只需要拆箱一次）。

  • 时间复杂度分析
    第一步：找到最大值和最小值的过程需要一轮遍历，时间复杂度O(n),空间复杂度O(1)。
    第二步：装桶的过程需要遍历一轮数组，时间复杂度O(n)，空间复杂度与桶的数量以及数据结构有关，设桶的数量为 k，如果使用 k 个长度为 n 的数组作为桶，则空间复杂度为 O(kn)，如果采用 ArrayList 或 LinkedList 来装桶，或者采用初始长度为 0 ，装桶时不断扩容的数组，则空间复杂度为 O(n) 。
    第三次：桶内排序的过程和具体的排序算法有关，由于桶排序假设数据从均匀分布，所以每个桶内的数字数量为 n/k ,采用O(=n^2)级的排序算法，则每个桶内的时间复杂度为O((n/k)^2)，所有桶完成排序的时间复杂度为 O(n^2/k);
    如果采用 O(nlog n)O(nlogn) 级排序算法，每个桶内排序的时间复杂度 O((n/k)log(n/k))，所有桶完成排序的时间复杂度为 O(k(n/k)log (n/k))，即 O(nlog(n/k))。

在桶的数量合适的情况下，时间复杂度 O(n^2/k)和O(nlog(n/k))都约等于O(n)O(n)。