【概述】

計數排序是一種穩定的排序，屬于非比較類排序，其基本思想是：對于給定的輸入序列中的每一個元素 x，確定該序列中值小于 x 的元素的個數，一旦有了這個信息，就可以將 x 直接存放到最終的輸出序列的正確位置上。

例如，如果輸入序列中只有 17 個元素的值小于 x 的值，則 x 可以直接存放在輸出序列的第 18 個位置上。當然，如果有多個元素具有相同的值時，不能將這些元素放在輸出序列的同一個位置上，在代碼中作適當的修改即可。

【排序過程】

計數排序的排序過程為：

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

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

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

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

【源程序】

#define MAXNUM 20//待排序數的最大個數 #define MAX 100//待排序數的最大值 int res[MAXNUM]; int temp[MAX+1]; void countSort(int a[], int n){for(int i=0;i<n;i++)//統計i的次數 temp[a[i]]++; for(int i=1;i<=MAX;i++)//對所有的計數累加，統計數組a的前綴和與小于小于a數組值出現的個數temp[i]+=temp[i-1];for(int i=n-1;i>=0;i--){//逆向遍歷源數組，根據計數數組中對應的值填充到新數組中res[temp[a[i]]-1]=a[i];//temp[a[i]]表示數組a中包括a[i]和小于a[i]的總數temp[a[i]]--;//如果數組a中有相同的數，a[i]的下標-1} }

?

總結

以上是生活随笔為你收集整理的理论基础 —— 排序 —— 计数排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。