排序算法(六): Counting Sort 计数排序

之前文章介绍的一些排序算法都是基于比较来进行排序的,故它们在平均情况下的时间复杂度最好也不过是线性对数级别。这里我们来介绍一种简单的基于非比较的排序算法——Counting Sort 计数排序,其时间复杂度可以达到线性级别

abstract.jpeg

基本思想

Counting Sort 计数排序,顾名思义,就是统计待排序数组元素的出现次数。其基本思想比较简单:

  1. 根据待排序元素的数值范围大小k(max-min+1),建立一个k大小的频数统计数组counts。对于counts数组而言,其索引范围 0 ~ k-1,正好可以对应到待排序元素的取值范围min~max上
  2. 统计待排序元素element的次数,并其存储到counts数组中,即counts[ elemet-min ] = countValue
  3. 待计数统计完成后遍历counts数组,根据次数值来输出原待排序元素值,此时即完成排序

    这里给出计数排序在Java下的实现:

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
* 计数排序
*/
public class CountingSort {

/**
* 升序排列 (非稳定)
*/
public static void sort1() {
// 获取测试用例
int[] array = getTestCase();
int size = array.length;

System.out.println("before sort: " + Arrays.toString(array) );

// 求取最值
int[] minMax = getMinMax(array);
int min = minMax[0];
int max = minMax[1];

// 根据数据范围创建统计数组
int k = max-min+1;
int[] counts = new int[ k ];

// 统计原数组中元素出现的次数
for(int i=0; i<size; i++) {
int dataInCountIndex = array[i] - min; // 计算原数组元素在统计数组中的索引
counts[dataInCountIndex] +=1; // 统计该值次数
}

int j = 0; // 有序的数据的插入位置
for(int i=0; i<k; i++) {
int originalData = i + min; // 还原 原排序数组的数据值
while( counts[i]>0 ) {
array[j] = originalData;
counts[i]--; // 该数值出现的次数减1
j++; // 更新有序数据的插入位置
}
}

System.out.println("after sort: " + Arrays.toString(array) );
}

/**
* 求指定数组的最值
* @param array
* @return [0]: 最小值; [1]: 最大值;
*/
private static int[] getMinMax(int[] array) {
int min = array[0];
int max = array[0];
for(int i=1; i<array.length; i++) {
if( array[i]>max ) {
max = array[i];
}
if( array[i]<min ) {
min = array[i];
}
}
int[] minMax = new int[]{min,max};
return minMax;
}

/**
* 获取测试用例
*/
private static int[] getTestCase() {
int[] caseArray = {-1,1,-1,1,2};
return caseArray;
}
}

测试结果如下:

figure 1.png

稳定的计数排序

基本原理

上面的计数排序算法是非稳定的,而一般我们所说的计数排序都是稳定的。那么如何保证计数排序的稳定性呢?其实很简单,只需在统计完待排序元素的频数后,对counts作累加计算(counts[i] = counts[i-1] + counts[i]),即计算统计数组中指定索引位置上的元素在排序后的位置;然后倒序遍历原数组,根据counts数组中的排序位置来将待排序元素放入合适的位置,同时将counts数组相应的值减1,以使下一个重复的排序元素可以放在前一位的位置上,以保证稳定性

算法图解

下图即是通过稳定的计数排序对 -1,1,-1,1,2 序列进行升序排列的图解过程

1. 建立counts数组

figure 2.png

2. 倒序遍历原待排序数组,按升序排列

figure 3.jpeg

Java实现

这里给出计数排序在Java下的实现:

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
/**
* 计数排序
*/
public class CountingSort {
...
/**
* 升序排列 (稳定)
*/
public static void sort2() {
// 获取测试用例
int[] array = getTestCase();
int size = array.length;

System.out.println("before sort: " + Arrays.toString(array) );

// 求取最值
int[] minMax = getMinMax(array);
int min = minMax[0];
int max = minMax[1];

// 根据数据范围创建统计数组
int k = max-min+1;
int[] counts = new int[ k ];

// 统计原数组中元素出现的次数
for(int i=0; i<size; i++) {
int dataInCountIndex = array[i] - min; // 计算原数组元素在统计数组中的索引
counts[dataInCountIndex] +=1; // 统计该值次数
}

// 计算统计数组的累计值,即计算 统计数组中指定索引位置上的元素在排序后的位置
// 如果该索引位置上有重复元素,则为重复元素所占的最大排序位置
for(int i=1; i<k; i++) {
counts[i] = counts[i-1] + counts[i];
}

int[] sortedArray = new int[size]; // 排序结果数组
// 倒序遍历原数组,保证稳定性
for(int i=size-1; i>=0; i--) {
int dataInCountIndex = array[i] - min; // 计算原数组元素在统计数组中的索引
// 计算其排序后的位置, 因为数组索引从0开始计算,故应对排序位置减1
// 例如,排在最前面的元素,排序位置为1,则其在数组中的位置索引应为0
int sortIndex = counts[dataInCountIndex] - 1;
sortedArray[sortIndex] = array[i]; // 将原数组元素放入排序后的位置上
counts[dataInCountIndex]--; // 下一个重复的元素,应排前一个位置,以保证稳定性
}

System.out.println("after sort: " + Arrays.toString(sortedArray) );
}
...
}

测试结果如下:

figure 4.png

特点

复杂度、稳定性

这里以稳定的计数排序进行说明:

时间复杂度 空间复杂度 稳定性
$O(N + k)$ $O(N + k)$ 稳定

缺陷

  1. 计数排序只能适用待排序元素为整数的场景
  2. 待排序元素的数值范围(极差)过大的情况下,计数排序会浪费大量空间,故一般不推荐使用计数排序

参考文献

  1. 算法导论 · 第3版
0%