计数排序、基数排序、桶排序

基于比较的排序算法的时间复杂度的下界一般是O(nlog(n))。而非基于比较的算法,如计数排序、基数排序和桶排序是可以突破这个下界的,但是限制也很多。

计数排序(Counting sort)

  • 思路:计数排序(Counting sort)是一种稳定的排序算法。计数排序是最简单的特例,由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存,适用性不高。其基本思想是对每一个输入元素x,确定小于x的元素个数,利用这一信息,就可以直接把x放到它在输出数组中的位置上。计数排序经常会被用作计数排序算法的一个子过程。当输入的元素是n个0到k之间的整数时,它的时间复杂度是O(n+k)。

  • 步骤:

    1. 找出待排序数组A[0..n)中的最大和最小的元素
    2. 申请大小为n(由最大值-最小值+1得到的范围)的数组B和大小为k(待排序数组A的元素个数)的数组C[0..k]
    3. 统计数组中每个值的出现次数,存入到数组B的[0,n)范围中
    4. 在[0,n)范围中对所有的计数累加(每一项值+=前一项值)
    5. 反向遍历待排序数组A,将A中元素在B中对应的计数减1(防止重复),然后A[i]存入此值作为下标的C数组中
  • 代码:
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
#include <iostream>

void countingSort(int a[], int k) {
if (k < 2) return;
int min = a[0], max = a[0];
for (int i = 0; i < k; ++i) {
if (a[i] < min) min = a[i];
if (a[i] > max) max = a[i];
}

// 原始数组值
std::cout << "原始数组值" << std::endl;
for (int i = 0; i < k; ++i) {
std::cout << a[i] << " ";
}
std::cout << std::endl;

int n = max - min + 1;
int *b = new int[n]; //辅助数组
int *c = new int[k]; //结果数组
memset(b, 0, sizeof(int)*n);

for (int i = 0; i < k; ++i) {
++b[a[i] - min];
}
for (int i = 1; i < n; ++i) {
b[i] += b[i - 1];
}

// 辅助数组累加后值
std::cout << "辅助数组累加后值" << std::endl;
for (int i = 0; i < n; ++i) {
std::cout << b[i] << " ";
}
std::cout << std::endl;

for (int i = k - 1; i >= 0; --i) {
--b[a[i] - min];
c[b[a[i] - min]] = a[i];
}

// 辅助数组最终值
std::cout << "辅助数组最终值" << std::endl;
for (int i = 0; i < n; ++i) {
std::cout << b[i] << " ";
}
std::cout << std::endl;

// 结果数组值
std::cout << "结果数组值" << std::endl;
for (int i = 0; i < k; ++i) {
std::cout << c[i] << " ";
}
std::cout << std::endl;

memcpy(a, c, sizeof(int) * k);
delete [] b;
delete [] c;
}

int main() {
int *a = new int[5] {5, 2, 3, 2, 1};
countingSort(a, 5);
delete [] a;
int arr[] = { 2, 5, -3, 0, 2, 3, 0, 3 };
countingSort(arr, sizeof(arr)/sizeof(int));
return 0;
}

特点

  • 计数排序仅适合于小范围的数据进行排序
  • 不能对浮点数进行排序
  • 时间复杂度为 O(n)
  • 计数排序是稳定的

基数排序(radix sorting)

基数排序(radix sorting)将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。 然后从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

假设我们有一些二元组(a,b),要对它们进行以a为首要关键字,b的次要关键字的排序。我们可以先把它们先按照首要关键字排序,分成首要关键字相同的若干堆。然后,在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起,使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。第二种方式是从最低有效关键字开始排序,称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序,然后对所有的数据按照首要关键字排序。要注意的是,使用的排序算法必须是稳定的,否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序,LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的。

基数排序的简单描述就是将数字拆分为个位十位百位,每个位依次排序。因为这对算法稳定要求高,所以我们对数位排序用到上一个排序方法计数排序。因为基数排序要经过d (数据长度)次排序, 每次使用计数排序, 计数排序的复杂度为 O(d*n),所以基数排序也是 O(n)。基数排序虽然是线性复杂度, 即对n个数字处理了n次,但是每一次代价都比较高, 而且使用计数排序的基数排序不能进行原地排序,需要更多的内存, 并且快速排序可能更好地利用硬件的缓存, 所以比较起来,像快速排序这些原地排序算法更可取。对于一个位数有限的十进制数,我们可以把它看作一个多元组,从高位到低位关键字重要程度依次递减。可以使用基数排序对一些位数有限的十进制数排序。

代码:

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>

void print(int *arr, int k, int index, int maxIndex) {
if (index != maxIndex) {
std::cout << "按第" << index << "位排序后,结果为:" << std::endl;
}
else {
std::cout << "最终排序结果为:" << std::endl;
}
for (int i = 0; i < k; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}

int getBitNum(int num, int index) {
while (num != 0 && index > 0) {
num /= 10;
--index;
}
return num % 10;
}

void countingSort(int *a, int k, int index) {
if (k < 2) return;
int min = 0, max = 9;

// 原始数组值
std::cout << "原始数组值" << std::endl;
for (int i = 0; i < k; ++i) {
std::cout << a[i] << " ";
}
std::cout << std::endl;

int n = max - min + 1;
int *b = new int[n]; //辅助数组
int *c = new int[k]; //结果数组
memset(b, 0, sizeof(int)*n);

for (int i = 0; i < k; ++i) {
++b[getBitNum(a[i] - min, index)];
}
for (int i = 1; i < n; ++i) {
b[i] += b[i - 1];
}

// 辅助数组累加后值
std::cout << "辅助数组累加后值" << std::endl;
for (int i = 0; i < n; ++i) {
std::cout << b[i] << " ";
}
std::cout << std::endl;

for (int i = k - 1; i >= 0; --i) {
--b[getBitNum(a[i] - min, index)];
c[b[getBitNum(a[i] - min, index)]] = a[i];
}

// 辅助数组最终值
std::cout << "辅助数组最终值" << std::endl;
for (int i = 0; i < n; ++i) {
std::cout << b[i] << " ";
}
std::cout << std::endl;

// 结果数组值
std::cout << "结果数组值" << std::endl;
for (int i = 0; i < k; ++i) {
std::cout << c[i] << " ";
}
std::cout << std::endl;
memcpy(a, c, sizeof(int) * k);
delete[] b;
delete[] c;
}

void radixSorting(int *arr, int k, int d) {
for (int i = 0; i < d; ++i) {
countingSort(arr, k, i);
print(arr, k, i, d);
}
}

int main() {
int arr[] = { 326,453,608,835,751,435,704,690,88,79,79 };
radixSorting(arr, sizeof(arr)/sizeof(int), 3);
for (int i = 0; i < sizeof(arr) / sizeof(int); ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;

return 0;
}

特点

  • 基数排序仅可排序非负整数
  • 与计数排序不同的是,基数排序可以排序大整数
  • 对每一位进行排序时,需要使用稳定的排序算法,保证在排序高位时低位的顺序不会变
  • 时间复杂度为 O(n)

桶排序(bucket sort)

对于一组长度为k的待排序数组A,将这些数据划分为M个区间(即放入M个桶中)。根据某种映射函数,将这k个数据放入m个桶中。然后对每个桶中的数据进行排序,最后依次输出,得到已排序数据。桶排序要求待排序的元素都属于一个固定的且有限的区间范围内。桶排序步骤如下:

  • 扫描序列A,根据每个元素的值所属的区间,放入指定的桶中(顺序放置)。
  • 对每个桶中的元素进行排序,例如插入排序。
  • 依次收集每个桶中的元素,顺序放置到输出序列中。

特点

  • 桶排序要求待排序数组的所有数据在某个指定的范围内
  • 可以用来排序浮点数,而计数排序和基数排序则不能排序浮点数
  • 桶排序是稳定的(桶内需使用插入排序等稳定排序算法)
  • 速度快,耗空间

小结

三种排序算法一般来说都是线性时间下的稳定排序(基数排序和桶排内部必须也使用稳定排序),但这个三种排序对数据的要求都比较严格,计数排序仅能对集中在较小范围中的整数进行排序,且排序的规模不宜过大;基数排序可以对长整数进行排序,但是不适用于浮点数;桶排序则可以对浮点数进行排序。

参考

线性排序算法(计数排序,基数排序,桶排序)分析及实现
计数排序,基数排序和桶排序