到了這篇文章就說明常見的排序我們就快要講完了，那這篇文章我們就講一下非比較排序--計數排序。
一、非比較排序
1.基本思想
計數排序又稱為鴿巢原理，是對哈希直接定址法的變形應用。 操作步驟：
- 統計相同元素出現次數
- 根據統計的結果將序列回收到原來的序列中
?
二、計數排序的特性總結
- 計數排序在數據范圍集中時，效率很高，但是適用范圍及場景有限。
- 時間復雜度：O(MAX(N,范圍))
- 空間復雜度：O(范圍)
- 穩定性：穩定
?
三、 計數排序
1. 實現思想
計數排序是一種非比較排序，它通過統計數組中每個數據出現的次數，然后根據數據出現的次數和數據的值來重構這個數組，從而將數組排成有序。所以計數排序適合數據范圍相對集中且數據為非負整數的情況。
?
2.?具體實現?
void CountSort(int* a, int n)
{int max = a[0], min = a[0];for (int i = 0; i < n; i++){if (min > a[i]){min = a[i];}if (max < a[i]){max = a[i];}}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail");return;}memset(count, 0, sizeof(int) * range);// 統計數據出現的次數for (int i = 0; i < n; i++){count[a[i] - min]++;}//排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}?
四、對于排序的總結
?
?
)
