【经典算法】线性时间排序

　　在计算机科学中，排序是一门基础的算法技术，许多算法都要以此作为基础，不同的排序算法有着不同的时间开销和空间开销。排序算法有非常多种，如我们最常用的快速排序和堆排序等算法，这些算法需要对序列中的数据进行比较，因为被称为基于比较的排序。

基于比较的排序算法是不能突破O(NlogN)的。简单证明如下：

　　N个数有N!个可能的排列情况，也就是说基于比较的排序算法的判定树有N!个叶子结点，比较次数至少为log(N!)=O(NlogN)(斯特林公式)。

　　而非基于比较的排序，如计数排序，桶排序，和在此基础上的基数排序，则可以突破O(NlogN)时间下限。但要注意的是，非基于比较的排序算法的使用都是有条件限制的，例如元素的大小限制，相反，基于比较的排序则没有这种限制(在一定范围内)。但并非因为有条件限制就会使非基于比较的排序算法变得无用，对于特定场合有着特殊的性质数据，非基于比较的排序算法则能够非常巧妙地解决。

　　本文着重介绍三种线性的非基于比较的排序算法：计数排序、桶排序与基数排序。

1.计数排序　

　　假设我们有一个待排序的整数序列A，其中元素的最小值不小于0，最大值不超过K。建立一个长度为K的线性表C，用来记录不大于每个值的元素的个数。这个算法伪代码如下：

　　假设输入数组A[1..n]，A.length=n,我们还需要两个数组：B[1..n]存放排序的输出，C[0..k]提供临时存储空间。

COUNTING-SORT(A,B,k)
1 let C[0..k]be a new array
2 for i=0 to k
3     C[i] = 0
4 for j = 1 to A.length
5     C[A[j]] = C[A[j]] + 1;
6 //C[i] now contains the number of elements equal to i.
7 for i = 1 to k
8     C[i] = C[i] + C[i-1]
9 //C[i]now contains the number of elements less than or equal to i.
10 for j = A.length downto 1
11     B[C[A[j]]] = A[J]
12     C[A[J]] = C[A[j]] - 1;

　　上述代码在第2~3行for循环的初始化操作之后，数组C的值全为0；第4~5行的for循环遍历每一个输入元素。如果一个输入元素的值为i，就将C[i]值加1.于是，在第5行执行完成后，C[i]中保存的就是等于i的元素的个数，其中i=0,1,...,k。第7~8行通过加总计算确定对每一个i=0,1,...,k，就有多少输入元素是小于或等于i的。

　　最后，在第10~12行的for循环部分，把每个元素A[j]放到它在输出数组B中的正确位置上。如果所有n个元素都是互异的，那么当第一次执行第10行时，对每个A[j]值来说，C[A[j]]就是A[j]在输出数组中的最终正确的位置。这是因为共有C[A[j]]个元素小于等于A[j]。因为所有的元素可能并不都是互异的，所以，我们每将一个值A[j]放入数组B中一后，都要将C[A[j]]的值减1.这样，当遇到下一个值等于A[j]的输入元素（如果存在）时，该元素可以直接被放在输出数组A[j]的前一个位置上。

　　例如，输入数组A为{3, 4, 3, 2, 1}，最大是4，数组长度是5。

　　建立计数数组C{0, 0, 0, 0}。

　　遍历输入数组：

　　A{3, 4, 3, 2, 1} -> C{0, 0, 1, 0}
　　A{3, 4, 3, 2, 1} -> C{0, 0, 1, 1}
　　A{3, 4, 3, 2, 1} -> C{0, 0, 2, 1}
　　A{3, 4, 3, 2, 1} -> C{0, 1, 2, 1}
　　A{3, 4, 3, 2, 1} -> C{1, 1, 2, 1}

　　计数数组现在是{1, 1, 2, 1}，我们现在把它写回到输入数组里：

　　C{0, 1, 2, 1} -> A{1, 4, 3, 2, 1}
　　C{o, o, 2, 1} -> A{1, 2, 3, 2, 1}
　　C{o, o, 1, 1} -> A{1, 2, 3, 2, 1}
　　C{o, o, o, 1} -> A{1, 2, 3, 3, 1}
　　C{o, o, o, o} -> A{1, 2, 3, 3, 4}

　　这样就排好序了。

　　时间：O(n + k)，n是输入数组长度，k是最大的数的大小。

　　空间：O(n + k)，n是输入数组长度，k是最大的数的大小。

　　C++代码如下：

 1 void CountingSort(int A[], int len, int k) {
 2     if (A == NULL || len <= 0 || k <= 0)
 3         return;
 4     
 5     int *B = new int[len]();
 6     int *C = new int[k+1]();
 7     for (int i = 0; i < len; ++i)
 8         C[A[i]]++;
 9     for (int i = 1; i <= k; ++i)
10         C[i] += C[i - 1];
11 
12     for (int i = len - 1; i >= 0; --i) {
13         B[C[A[i]] - 1] = A[i];
14         C[A[i]]--;
15     }
16 
17     for (int i = 0; i < len; ++i)
18         A[i] = B[i];
19 
20     delete []C;
21     delete []B;
22 }

　2. 桶排序　　

　　这种特殊实现的方式时间复杂度为O(N+K)，空间复杂度也为O(N+K)，同样要求每个元素都要在K的范围内。更一般的，如果我们的K很大，无法直接开出O(K)的空间该如何呢？

　　首先定义桶，桶为一个数据容器，每个桶存储一个区间内的数。依然有一个待排序的整数序列A，元素的最小值不小于0，最大值不超过K。假设我们有M个桶，第i个桶Bucket[i]存储iK/M至(i+1)K/M之间的数，有如下桶排序的一般方法：

扫描序列A，根据每个元素的值所属的区间，放入指定的桶中(顺序放置)。
对每个桶中的元素进行排序，什么排序算法都可以，例如快速排序。
依次收集每个桶中的元素，顺序放置到输出序列中。

　　对该算法简单分析，如果数据是期望平均分布的，则每个桶中的元素平均个数为N/M。如果对每个桶中的元素排序使用的算法是快速排序，每次排序的时间复杂度为O(N/Mlog(N/M))。则总的时间复杂度为O(N)+O(M)O(N/Mlog(N/M)) = O(N+ Nlog(N/M)) =O(N + NlogN - NlogM)。当M接近于N是，桶排序的时间复杂度就可以近似认为是O(N)的。就是桶越多，时间效率就越高，而桶越多，空间却就越大，由此可见时间和空间是一个矛盾的两个方面。

　　桶中元素的顺序放入和顺序取出是有必要的，因为这样可以确定桶排序是一种稳定排序算法，配合基数排序是很好用的

　　代码如下，使用的例子是算法导论上的例子（区间为[0,1))：

 1 struct Node {
 2     float value;
 3     Node* next;
 4 
 5     Node(float v = 0) :value(v), next(NULL) {}
 6 };
 7 
 8 void Destruct(Node *p) {
 9     if (p == NULL) {
10         return;
11     }else {
12         Destruct(p->next);
13         delete p;
14     }
15 }
16 
17 void BucketSort(float A[],  int n) {
18     Node **B = new Node*[n];
19     memset(B, NULL, sizeof(Node*)*n);
20     
21     int i = 0, j;
22     for (i = 0; i < n; i++) {
23         int bi = n * A[i] ;
24         Node* q = new Node(A[i]);
25         Node *p = B[bi];
26         if (p == NULL) {
27             B[bi] = q;
28         } else if (p->next == NULL) {
29             if (A[i] < p->value) {
30                 B[bi] = q;
31                 q->next = p;
32             } else {
33                 p->next = q;
34             }
35         } else {
36             while ( p->next != NULL && A[i] > p->next->value)
37                 p = p->next;
38             q->next = p->next;
39             p->next = q;
40         }
41     }
42 
43     for (i = j = 0; i < n; i++) {
44         Node *p = B[i];
45         while (p != NULL) {
46             A[j++] = p->value;
47             p = p->next;
48         }
49     }
50 
51     for (i = 0; i < n; i++)
52         Destruct(B[i]);
53 
54     delete []B;
55 }

3.基数排序

　　下面说到我们的重头戏，基数排序(Radix Sort)。上述的基数排序和桶排序都只是在研究一个关键字的排序，现在我们来讨论有多个关键字的排序问题。

　　假设我们有一些二元组(a,b)，要对它们进行以a为首要关键字，b的次要关键字的排序。我们可以先把它们先按照首要关键字排序，分成首要关键字相同的若干堆。然后，在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起，使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。

　　第二种方式是从最低有效关键字开始排序，称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序，然后对所有的数据按照首要关键字排序。要注意的是，使用的排序算法必须是稳定的，否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序，LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的。

　　代码如下：

 1 #include<iostream>
 2 #include<vector>
 3 #include<cmath>
 4 using namespace std;
 5 
 6 int getMax(int arr[], int n) {
 7     int mx = arr[0];
 8     for (int i = 1; i < n; i++)
 9         if (arr[i] > mx)
10         mx = arr[i];
11 
12     return mx;
13 }
14 
15 void CountSort(int arr[], int n, int exp) {
16     int *output = new int[n];
17     int i, count[10] = { 0 };
18 
19     //Store count of occurrences in count[]
20     for (i = 0; i < n; i++)
21         count[(arr[i] / exp) % 10]++;
22 
23     //Change count[i] so that count[i] now contains actual position of
24     //this digit in output[]
25     for (i = 1; i < 10; i++)
26         count[i] += count[i - 1];
27 
28     //Build the output array
29     for (i = n - 1; i >= 0; i--) {
30         output[count[(arr[i] / exp) % 10] - 1] = arr[i];
31         count[(arr[i] / exp) % 10]--;
32     }
33 
34     //Copy the output array to arr[], so that arr[] now 
35     //contains sorted numbers according to current digit
36     for (i = 0; i < n; i++)
37         arr[i] = output[i];
38 
39     delete []output;
40 }
41 
42 void RadixSort(int arr[], int n) {
43     //Find the maximum number fo know number of digits
44     int m = getMax(arr, n);
45 
46     //Do counting sort for every digit. Note that instead of passing digit
47     //number, exp is passed. exp is 10^i where i is current digit number
48     for (int exp = 1; m / exp > 0; exp *= 10)
49         CountSort(arr, n, exp);
50 }
51 
52 //A utility function to print an array
53 void Print(int arr[], int n) {
54     for (int i = 0; i < n; i++)
55         cout << arr[i] << " ";
56 }
57 
58 int main()
59 {
60     int arr[] = { 170, 45, 90, 802, 24, 2, 66 };
61     int n = sizeof(arr) / sizeof(arr[0]);
62     RadixSort(arr, n);
63     Print(arr, n);
64 
65     system("pause");
66     return 0;
67 
68 }

三种排序算法的比较：　　　

　　从整体上来说，计数排序，桶排序都是非基于比较的排序算法，而其时间复杂度依赖于数据的范围，桶排序还依赖于空间的开销和数据的分布。而基数排序是一种对多元组排序的有效方法，具体实现要用到计数排序或桶排序。

相对于快速排序、堆排序等基于比较的排序算法，计数排序、桶排序和基数排序限制较多，不如快速排序、堆排序等算法灵活性好。但反过来讲，这三种线性排序算法之所以能够达到线性时间，是因为充分利用了待排序数据的特性，如果生硬得使用快速排序、堆排序等算法，就相当于浪费了这些特性，因而达不到更高的效率。

　　在实际应用中，基数排序可以用于后缀数组的倍增算法，使时间复杂度从O(NlogNlogN)降到O(N*logN)。线性排序算法使用最重要的是，充分利用数据特殊的性质，以达到最佳效果。

参考文献：

　　1.http://www.geeksforgeeks.org/radix-sort/

　　2.http://www.geeksforgeeks.org/counting-sort/

　　3.https://www.byvoid.com/blog/sort-radix