計數(shù)排序算法

.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:0 0 5px 0;padding:5px;border:1px solid #d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc 100px);background-image:linear-gradient(#fff,#e5eecc 100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1px solid #d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1px solid #d4d4d4;width:98%}div.code{width:98%;border:1px solid #d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.code div{font-size:110%}div.code div,div.code p,div.example_code p{font-family:"courier new"}pre{margin:15px auto;font:12px/20px Menlo,Monaco,Consolas,"Andale Mono","lucida console","Courier New",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1px solid #ddd;border-left-width:4px;padding:10px 15px}

排序算法是《數(shù)據(jù)結(jié)構(gòu)與算法》中最基本的算法之一。排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。以下是計數(shù)排序算法：

計數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。作為一種線性時間復(fù)雜度的排序，計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

1. 計數(shù)排序的特征

當輸入的元素是 n 個 0 到 k 之間的整數(shù)時，它的運行時間是 Θ(n + k)。計數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。

由于用來計數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1），這使得計數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時間和內(nèi)存。例如：計數(shù)排序是用來排序0到100之間的數(shù)字的最好的算法，但是它不適合按字母順序排序人名。但是，計數(shù)排序可以用在基數(shù)排序中的算法來排序數(shù)據(jù)范圍很大的數(shù)組。

通俗地理解，例如有 10 個年齡不同的人，統(tǒng)計出有 8 個人的年齡比 A 小，那 A 的年齡就排在第 9 位,用這個方法可以得到其他每個人的位置,也就排好了序。當然，年齡有重復(fù)時需要特殊處理（保證穩(wěn)定性），這就是為什么最后要反向填充目標數(shù)組，以及將每個數(shù)字的統(tǒng)計減去 1 的原因。

?算法的步驟如下：

（1）找出待排序的數(shù)組中最大和最小的元素（2）統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項（3）對所有的計數(shù)累加（從C中的第一個元素開始，每一項和前一項相加）（4）反向填充目標數(shù)組：將每個元素i放在新數(shù)組的第C(i)項，每放一個元素就將C(i)減去12. 動圖演示

代碼實現(xiàn)JavaScript 實例 function countingSort(arr, maxValue) {? ? var bucket = new Array(maxValue+1),? ? ? ? sortedIndex = 0;? ? ? ? arrLen = arr.length,? ? ? ? bucketLen = maxValue + 1;? ? for (var i = 0; i < arrLen; i++) {? ? ? ? if (!bucket[arr[i]]) {? ? ? ? ? ? bucket[arr[i]] = 0;? ? ? ? }? ? ? ? bucket[arr[i]]++;? ? }? ? for (var j = 0; j < bucketLen; j++) {? ? ? ? while(bucket[j] > 0) {? ? ? ? ? ? arr[sortedIndex++] = j;? ? ? ? ? ? bucket[j]--;? ? ? ? }? ? }? ? return arr;}Python實例 def countingSort(arr, maxValue):? ? bucketLen = maxValue+1? ? bucket = [0]*bucketLen? ? sortedIndex =0? ? arrLen = len(arr)? ? for i in range(arrLen):? ? ? ? if not bucket[arr[i]]:? ? ? ? ? ? bucket[arr[i]]=0? ? ? ? bucket[arr[i]]+=1? ? for j in range(bucketLen):? ? ? ? while bucket[j]>0:? ? ? ? ? ? arr[sortedIndex] = j? ? ? ? ? ? sortedIndex+=1? ? ? ? ? ? bucket[j]-=1? ? return arrGo實例 func countingSort(arr []int, maxValue int) []int {? ? ? ? bucketLen := maxValue + 1? ? ? ? bucket := make([]int, bucketLen) // 初始為0的數(shù)組? ? ? ? sortedIndex := 0? ? ? ? length := len(arr)? ? ? ? for i := 0; i < length; i++ {? ? ? ? ? ? ? ? bucket[arr[i]] += 1? ? ? ? }? ? ? ? for j := 0; j < bucketLen; j++ {? ? ? ? ? ? ? ? for bucket[j] > 0 {? ? ? ? ? ? ? ? ? ? ? ? arr[sortedIndex] = j? ? ? ? ? ? ? ? ? ? ? ? sortedIndex += 1? ? ? ? ? ? ? ? ? ? ? ? bucket[j] -= 1? ? ? ? ? ? ? ? }? ? ? ? }? ? ? ? return arr}Java實例 public class CountingSort implements IArraySort {? ? @Override? ? public int[] sort(int[] sourceArray) throws Exception {? ? ? ? // 對 arr 進行拷貝，不改變參數(shù)內(nèi)容? ? ? ? int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);? ? ? ? int maxValue = getMaxValue(arr);? ? ? ? return countingSort(arr, maxValue);? ? }? ? private int[] countingSort(int[] arr, int maxValue) {? ? ? ? int bucketLen = maxValue + 1;? ? ? ? int[] bucket = new int[bucketLen];? ? ? ? for (int value : arr) {? ? ? ? ? ? bucket[value]++;? ? ? ? }? ? ? ? int sortedIndex = 0;? ? ? ? for (int j = 0; j < bucketLen; j++) {? ? ? ? ? ? while (bucket[j] > 0) {? ? ? ? ? ? ? ? arr[sortedIndex++] = j;? ? ? ? ? ? ? ? bucket[j]--;? ? ? ? ? ? }? ? ? ? }? ? ? ? return arr;? ? }? ? private int getMaxValue(int[] arr) {? ? ? ? int maxValue = arr[0];? ? ? ? for (int value : arr) {? ? ? ? ? ? if (maxValue < value) {? ? ? ? ? ? ? ? maxValue = value;? ? ? ? ? ? }? ? ? ? }? ? ? ? return maxValue;? ? }}PHP實例 function countingSort($arr, $maxValue = null){? ? if ($maxValue === null) {? ? ? ? $maxValue = max($arr);? ? }? ? for ($m = 0; $m < $maxValue + 1; $m++) {? ? ? ? $bucket[] = null;? ? }? ? $arrLen = count($arr);? ? for ($i = 0; $i < $arrLen; $i++) {? ? ? ? if (!array_key_exists($arr[$i], $bucket)) {? ? ? ? ? ? $bucket[$arr[$i]] = 0;? ? ? ? }? ? ? ? $bucket[$arr[$i]]++;? ? }? ? $sortedIndex = 0;? ? foreach ($bucket as $key => $len) {? ? ? ? ? ? ? ? if($len !== null){? ? ? ? ? ? for($j = 0; $j < $len; $j++){? ? ? ? ? ? ? ? $arr[$sortedIndex++] = $key;? ? ? ? ? ? }? ? ? ? }? ? }? ? return $arr;}C實例 #include #include #include void print_arr(int *arr, int n) {? ? ? ? int i;? ? ? ? printf("%d", arr[0]);? ? ? ? for (i = 1; i < n; i++)? ? ? ? ? ? ? ? printf(" %d", arr[i]);? ? ? ? printf(" ");}void counting_sort(int *ini_arr, int *sorted_arr, int n) {? ? ? ? int *count_arr = (int *) malloc(sizeof(int) * 100);? ? ? ? int i, j, k;? ? ? ? for (k = 0; k < 100; k++)? ? ? ? ? ? ? ? count_arr[k] = 0;? ? ? ? for (i = 0; i < n; i++)? ? ? ? ? ? ? ? count_arr[ini_arr[i]]++;? ? ? ? for (k = 1; k < 100; k++)? ? ? ? ? ? ? ? count_arr[k] += count_arr[k - 1];? ? ? ? for (j = n; j > 0; j--)? ? ? ? ? ? ? ? sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];? ? ? ? free(count_arr);}int main(int argc, char **argv) {? ? ? ? int n = 10;? ? ? ? int i;? ? ? ? int *arr = (int *) malloc(sizeof(int) * n);? ? ? ? int *sorted_arr = (int *) malloc(sizeof(int) * n);? ? ? ? srand(time(0));? ? ? ? for (i = 0; i < n; i++)? ? ? ? ? ? ? ? arr[i] = rand() % 100;? ? ? ? printf("ini_array: ");? ? ? ? print_arr(arr, n);? ? ? ? counting_sort(arr, sorted_arr, n);? ? ? ? printf("sorted_array: ");? ? ? ? print_arr(sorted_arr, n);? ? ? ? free(arr);? ? ? ? free(sorted_arr);? ? ? ? return 0;}

參考地址：

https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/8.countingSort.md

https://zh.wikipedia.org/wiki/%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F

以上為計數(shù)排序算法詳細介紹，插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等排序算法各有優(yōu)缺點，用一張圖概括：

關(guān)于時間復(fù)雜度

平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。

線性對數(shù)階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數(shù)。 希爾排序

線性階 (O(n)) 排序 基數(shù)排序，此外還有桶、箱排序。

關(guān)于穩(wěn)定性

穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序。

不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：數(shù)據(jù)規(guī)模

k："桶"的個數(shù)

In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存

Out-place：占用額外內(nèi)存

穩(wěn)定性：排序后 2 個相等鍵值的順序和排序之前它們的順序相同