計數排序算法c++實現

.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}

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

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

1. 計數排序的特征

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

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

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

?算法的步驟如下：

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

代碼實現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的數組? ? ? ? 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 進行拷貝，不改變參數內容? ? ? ? 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

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

關于時間復雜度

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

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

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

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

關于穩定性

穩定的排序算法：冒泡排序、插入排序、歸并排序和基數排序。

不是穩定的排序算法：選擇排序、快速排序、希爾排序、堆排序。

名詞解釋：

n：數據規模

k："桶"的個數

In-place：占用常數內存，不占用額外內存

Out-place：占用額外內存

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