十大排序算法之计数排序

本文首发于个人博客

前言

本系列排序包括十大经典排序算法。

  • 使用的语言为:Java
  • 结构为:
    定义抽象类Sort里面实现了,交换,大小比较等方法。例如交换两个值,直接传入下标就可以了。其他的具体排序的类都继承抽象类Sort。这样我们就能专注于算法本身。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
* 返回值等于0,代表 array[i1] == array[i2]
* 返回值小于0,代表 array[i1] < array[i2]
* 返回值大于0,代表 array[i1] > array[i2]
*/
protected int cmp(int i1, int i2) {
return array[i1].compareTo(array[i2]);
}

protected int cmp(T v1, T v2) {
return v1.compareTo(v2);
}

protected void swap(int i1, int i2) {
T tmp = array[i1];
array[i1] = array[i2];
array[i2] = tmp;
}
  • 冒泡、选择、插入、归并、希尔、堆排序都是基于比较的排序

    • 平均时间复杂度最低O(nlogn)
  • 计数排序、桶排序、基数排序不是基于比较的排序

    • 使用空间换时间,某些时候,平均时间复杂度可以低于O(nlogn)

什么是计数排序

  • 计数排序(Counting sort)是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组 C ,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C 来将A中的元素排到正确的位置

算法思想

当输入的元素是n个0 到 k 之间的整数时,它的运行时间是O(n+k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。

核心思想:统计每个整数在序列中出现的次数,进而推导出每个整数在有序序列中的索引

  • 由于用来计数的数组C 的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。例如:计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名。但是,计数排序可以用在基数排序算法中,能够更有效的排序数据范围很大的数组。

  • 通俗地理解,例如有10个年龄不同的人,统计出有8个人的年龄比A小,那A的年龄就排在第9位,用这个方法可以得到其他每个人的位置,也就排好了序。当然,年龄有重复时需要特殊处理(保证稳定性),这就是为什么最后要反向填充目标数组,以及将每个数字的统计减去
    1。算法的步骤如下:

    • 找出待排序的数组中最大和最小的元素
    • 统计数组中每个值为i的元素出现的次数,存入数组C 的第i项
    • 对所有的计数累加 (从C 中的第一个元素开始,每一项和前一项相加)
    • 反向填充目标数组:将每个元素i放在新数组的第C[i]项,每放一个元素就将C[i]减去1

算法稳定性

  • 计数排序是一种稳定排序算法。

是否是原地算法

  • 何为原地算法?
    • 不依赖额外的资源或者依赖少数的额外资源,仅依靠输出来覆盖输入
    • 空间复杂度为 𝑂(1) 的都可以认为是原地算法
  • 非原地算法,称为 Not-in-place 或者 Out-of-place
  • 计数排序不属于 In-place

时空复杂度

  • 最好、最坏、平均时间复杂度:O(n+k)

  • 空间复杂度:O(n+k)

代码

先使用最简单的实现方案,先求最大值,用于创建数组,然后遍历出来,统计元素出现的次数,最后再按照顺序赋值

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
public class CountingSort extends Sort<Integer>{

protected void sort() {
//找出最大值
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i]>max) {
max= array[i];
}
}// O(n)

// 开辟内存空间,存储每个整数出现的次数
int[] counts = new int[max+1];
// 统计每个整数出现的次数
for (int i = 0; i < array.length; i++) {
counts[array[i]]++;
}// O(n)

// 根据整数的出现次数,对整数进行排序
int index = 0;
for (int i = 0; i < counts.length; i++) {
while (counts[i]-->0) {
array[index++] = i;

}
}// O(n)


}

}

优化

上述代码有些问题

  • 无法对负整数进行排序
  • 浪费内存空间
  • 不是稳定排序

优化思路:

  • 假设array中的最小值是min,最大值为max,就以min为索引0开始
    • 例如数组为 -2 4 5,那么 -2索引为0,4索引为6,5的索引为7
  • 定义个counts数组,里面存放着每个次数累加上前面的所有次数,得到的就是元素在有序序列中的位置信息

优化过的代码为

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
protected void sort2() {
//找出最大值和最小值
int max = array[0];
int min = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i]>max) {
max= array[i];
}
if (array[i]<min) {
min= array[i];
}
}// O(n)

// 开辟内存空间,存储次数
int[] counts = new int[max-min+1];
// 统计每个整数出现的次数
for (int i = 0; i < array.length; i++) {
counts[array[i]-min]++;
}// O(n)

// 累加次数
for (int i = 1; i < counts.length; i++) {
counts[i]+= counts[i-1];
}

//从后向前遍历元素,将她放在有序数组中的合适位置
int[] newArray = new int[array.length];
for (int i = array.length-1; i >=0 ; i--) {
//获取元素在counts中的索引
int index = array[i]-min;
//获取元素在counts中的值
//counts[index];
//放在合适位置
newArray[--counts[index]] = array[i];
}

// 将有序数组赋值到array
for (int i = 0; i < newArray.length; i++) {
array[i] = newArray[i];
}
}

结果

数据源:

从1到80000之间随机生成20000个数据来测试

Integer[] array = Integers.random(20000, 1, 80000);

结果如下

【CountingSort】
稳定性:true 耗时:0.005s(5ms) 比较次数:0 交换次数:0

【QuickSort】
稳定性:false 耗时:0.009s(9ms) 比较次数:33.27万 交换次数:1.32万

【MergeSort】
稳定性:true 耗时:0.01s(10ms) 比较次数:26.10万 交换次数:0

【ShellSort】
稳定性:false 耗时:0.016s(16ms) 比较次数:43.34万 交换次数:0

【HeapSort】
稳定性:false 耗时:0.023s(23ms) 比较次数:51.09万 交换次数:2.00万

【SelectionSort】
稳定性:true 耗时:0.514s(514ms) 比较次数:2.00亿 交换次数:2.00万

【InsertionSort1】
稳定性:true 耗时:1.362s(1362ms) 比较次数:9935.15万 交换次数:9933.15万

【BubbleSort】
稳定性:true 耗时:2.529s(2529ms) 比较次数:2.00亿 交换次数:9933.15万

可以看到这种情况下计数排序的甚至比快速排序,归并排序还要快。

代码地址: