計數(shù)排序（Counting sort）是一個非基于比較的排序算法，該算法于1954年由 Harold H. Seward 提出。它的優(yōu)勢在于在對一定范圍內(nèi)的整數(shù)排序時，它的復(fù)雜度為Ο(n+k)（其中k是整數(shù)的范圍），快于任何比較排序算法。

一、算法基本思想

（1）基本思想

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

例如，如果輸入序列中只有17個元素的值小于x的值，則x可以直接存放在輸出序列的第18個位置上。當(dāng)然，如果有多個元素具有相同的值時，我們不能將這些元素放在輸出序列的同一個位置上。解決方案就是要反向填充目標數(shù)組，以及將每個數(shù)字的統(tǒng)計減去1。

（2）運行過程

計數(shù)排序的運行過程如下：

1、找出待排序的數(shù)組中最大和最小的元素；

2、統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組 C 的第 i 項 ；

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

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

（3）示例

二、算法實現(xiàn)（核心代碼）

Java實現(xiàn)：

//針對c數(shù)組的大小，優(yōu)化過的計數(shù)排序 public class CountSort{public static void main(String []args){//排序的數(shù)組int a[] = {3, 6, 4, 1, 3, 4, 1, 4};int b[] = countSort(a);for(int i : b){System.out.print(i + " ");}System.out.println();}public static int[] countSort(int []a){int b[] = new int[a.length];int max = a[0], min = a[0];for(int i : a){if(i > max){max = i;}if(i < min){min = i;}}//這里k的大小是要排序的數(shù)組中，元素大小的極值差+1int k = max - min + 1;int c[] = new int[k];for(int i = 0; i < a.length; ++i){c[a[i]-min] += 1;//優(yōu)化過的地方，減小了數(shù)組c的大小}for(int i = 1; i < c.length; ++i){c[i] = c[i] + c[i-1];}for(int i = a.length-1; i >= 0; --i){b[--c[a[i]-min]] = a[i];//按存取的方式取出c的元素}return b;} }

三、性能（算法時間、空間復(fù)雜度、穩(wěn)定性）分析

計數(shù)排序時間復(fù)雜度為O(n+k)；空間復(fù)雜度為O(n+k)；是穩(wěn)定的排序算法。

需要注意的是：計數(shù)排序算法之所以能取得線性計算時間的上界是因為對元素的取值范圍作了一定限制，即k=O(n)。如果k=n^2，n^3,..，就得不到線性時間的上界。

總結(jié)

以上是生活随笔為你收集整理的经典排序算法（11）——计数排序算法详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。