突然想自己寫個桶排序，然后做課后題又發(fā)現(xiàn)了計數(shù)排序，覺得挺有趣的。不過書上都沒有給代碼，所以就自己寫了一下代碼，超級爛0 0下面先簡單介紹下這兩種排序

桶排序

桶排序，就是根據(jù)散列的思想進行數(shù)據(jù)的排序。假設(shè)有M個桶，采用最簡單的hash(key)=key，這樣無需比較，就可以把數(shù)存入相應(yīng)的桶中。針對沖突排解問題，此時查找鏈的方式顯然不再適用，采用獨立鏈法，把每個桶以鏈表的形式存儲雷同元素，定義相同元素的偏序，這樣能實現(xiàn)排序的穩(wěn)定性。桶排序完全采用了簡單的哈希策略，是比較容易理解的。同時，完全摒棄了CBA式的方式，從而可以突破復(fù)雜度O(nlogn)的界限。通過空間換時間的策略，可以達到O(n)的時間復(fù)雜度，代價是O(M+N)的額外空間。下面是對于整型數(shù)組的桶排序，代碼很爛我也沒有改，已經(jīng)測試過：

 1 struct node 
 2 {
 3     node(int v = 0, node* s = NULL) :value(v), succ(s) {}
 4     int value;
 5     node* succ;
 6 };
 7 void insert(node &a, int b)//b插入到a后面
 8 {
 9     node* t = new node(b);
10     if (a.succ) t->succ = a.succ;
11     a.succ = t;
12 }
13 node* bucketSort(int* A, int n, int k)//數(shù)的范圍為[0,k)
14 {
15     node* bucket = new node[k]();
16     for (int i = 0; i < n; i++)
17         insert(bucket[A[i]],A[i]);
18     return bucket;
19 }
20 void show(node a)
21 {
22     while (a.succ)
23     {
24         a = *(a.succ);//第一個節(jié)點作為哨兵不輸出
25         cout << a.value << " ";
26     }
27 }
28 int main()
29 {
30     int A[15] = { 2,0,1,3,3,0,1,9,7,7,15,11,13,12,10};
31     node* p = bucketSort(A, 15, 16);
32     for (int i = 0; i < 16; i++)
33         show(p[i]);
34     system("pause");
35     return 0;
36 }

下面有測試例子，已經(jīng)經(jīng)過了測試，不過這里僅把排序的結(jié)果存入了一個申請空間的列表然后輸出，沒有進行釋放的操作，也沒有存入原數(shù)組或者另外一個數(shù)組0 0看具體的要求可以改動

計數(shù)排序

計數(shù)排序的基本策略，基于這樣的事實：一個有序序列，元素m的秩，應(yīng)當?shù)扔谛蛄兄腥吭刂?#xff0c;小于等于m的元素數(shù)量。所以計數(shù)排序算法可以歸納如下：遍歷序列，對于每個元素，再遍歷整個序列，用一個額外的數(shù)組進行計數(shù)。不難看出，時間復(fù)雜度為O(n^2)。顯然，無法接受這樣的復(fù)雜度。

可以考慮用散列的方法來降低復(fù)雜度。同樣，對于[0,k)的元素，選取M個桶，假設(shè)元素數(shù)量為n，先遍歷序列，用桶數(shù)組進行計數(shù)。隨后，每一個后面的桶的計數(shù)=前面桶的數(shù)量+它自身的計數(shù)。這樣，每個桶的數(shù)字-1就等于桶對應(yīng)元素的秩。同時，也可以處理相同元素的問題，因為當元素存在其他因素的偏序時，數(shù)字也加在了桶數(shù)組的計數(shù)中，桶數(shù)組只需要從后向前輸出，就可以維持這種偏序。實現(xiàn)代碼如下：

 1 /*計數(shù)排序*/
 2 int* countSort(int* A,int k,int n)//[0,k)范圍內(nèi)n個數(shù)
 3 {
 4     int* tmp = new int[k];
 5     int* s = new int[n];
 6     memset(tmp, 0, sizeof(int) * k);
 7     for (int i = 0; i < n; i++)//原始數(shù)組中的計數(shù)
 8         tmp[A[i]]++;
 9     for (int i = 0; i < k - 1; i++)//記錄不大于該數(shù)的數(shù)字個數(shù)
10         tmp[i + 1] += tmp[i];
11     for (int i = n - 1; i >= 0; i--)//逆序輸出
12         s[--tmp[A[i]]] = A[i];//計數(shù)哈希數(shù)組-1即為應(yīng)當對應(yīng)的秩，用原數(shù)組的數(shù)賦值
13     delete[] tmp;
14     return s;
15 }

代碼已經(jīng)經(jīng)過了測試。可以看到，只需要兩趟原數(shù)組遍歷，一趟桶數(shù)組遍歷即可完成，時間復(fù)雜度為O(M+n)。同樣，輔助空間為桶數(shù)組，空間復(fù)雜度為O(M)。不難看出，計數(shù)排序適用的最合適情況，是M遠小于n的時候，即數(shù)據(jù)較多而范圍不大。此時，時間復(fù)雜度僅為O(n)。

轉(zhuǎn)載于:https://www.cnblogs.com/lustar/p/7308089.html

總結(jié)

以上是生活随笔為你收集整理的桶排序和计数排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。