計數排序不是基于比較的排序算法，其核心在于将輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。 作為一種線性時間複雜度的排序O（n），計數排序要求輸入的數據必須是有确定範圍的整數。（直方圖統計，再按照順序扔出來）

7.1 算法描述

找出待排序的數組中最大和最小的元素；

統計數組中每個值為i的元素出現的次數，存入數組C的第i項；

對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；

反向填充目标數組：将每個元素i放在新數組的第C(i)項，每放一個元素就将C(i)減去1。

7.2 動圖演示

代碼實現：

void countingSort(int a[], int len) { if (!a || len <= 0) return; //通過max和min計算出臨時數組所需要開辟的空間大小 int max = a[0], min = a[0]; for (int i = 0; i < len; i ) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } //分配臨時數組，使用calloc将數組都初始化為0 int range = max - min 1; int *b = (int *)calloc(range, sizeof(int)); //使用臨時數組記錄原始數組中每個數的個數 for (int i = 0; i < len; i ) b[a[i] - min] = 1; //注意：這裡在存儲上要在原始數組數值上減去min才不會出現越界問題 int j = 0; //根據統計結果，重新對元素進行回收 for (int i = 0; i < range; i ) { while (b[i]--) a[j ] = i min; //注意：要将i的值加上min才能還原到原始數據 } //釋放臨時數組 free(b); b = NULL; }

計數排序是一個穩定的排序算法。當輸入的元素是 n 個 0到 k 之間的整數時，時間複雜度是O(n k)，空間複雜度也是O(n k)，其排序速度快于任何比較排序算法。當k不是很大并且序列比較集中時，計數排序是一個很有效的排序算法。

桶排序是計數排序的升級版。它利用了函數的映射關系，高效與否的關鍵就在于這個映射函數的确定。桶排序 (Bucket sort)的工作的原理：假設輸入數據服從均勻分布，将數據分到有限數量的桶裡，每個桶再分别排序（有可能再使用别的排序算法或是以遞歸方式繼續使用桶排序進行排）。

8.1 算法描述

設置一個定量的數組當作空桶；

遍曆輸入數據，并且把數據一個一個放到對應的桶裡去；

對每個不是空的桶進行排序；

從不是空的桶裡把排好序的數據拼接起來。

8.2 動圖演示

8.3 代碼實現

//快速排序，用于每個桶中的排序，具體講解見之前的文章 void quickSort(int arr[], int left, int right) { if (left >= right) return; int l = left; int r = right; int key = arr[l]; while (l < r) { while (r > l && arr[r] > key) r--; arr[l] = arr[r]; while (l < r && arr[l] < key) l ; arr[r] = arr[l]; } arr[l] = key; quickSort(arr, left, l - 1); quickSort(arr, l 1, right); } //定義一個桶的結構體，也可以使用鍊表等其他實現方法 struct bucket { int node[10]; int count; //數據個數 }; void bucketSort(int a[], int len) { if (!a || len <= 0) return; int max = a[0], min = a[0]; for (int i = 1; i < len; i ) { if (a[i] > max) max = a[i]; if (a[i] < min) min = a[i]; } int num = (max - min 1) / 10 1; struct bucket *pBucket = (struct bucket*)calloc(num, sizeof(struct bucket)); //将a[i]放進對應的桶中 for (int i = 0; i < len; i ) { int k = (a[i] - min 1) / 10; //計算a[i]所屬桶的序号 (pBucket k)->node[(pBucket k)->count] = a[i]; (pBucket k)->count ; } int pos = 0; for (int i = 0; i < num; i ) { quickSort((pBucket i)->node, 0, (pBucket i)->count - 1);//使用快速排序對每個桶中的數進行排序，當然你可以使用任意一種排序 for (int j = 0; j < (pBucket i)->count; j ) { a[pos ] = (pBucket i)->node[j]; } } free(pBucket); }

桶排序最好情況下使用線性時間O(n)，桶排序的時間複雜度，取決于對各個桶之間數據進行排序的時間複雜度，因為其它部分的時間複雜度都為O(n)。很顯然，桶劃分的越小，各個桶之間的數據越少，排序所用的時間也會越少。但相應的空間消耗就會增大。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!