云漫圈 | 计数排序，你真的了解么？
參加 2018 AI開發(fā)者大會，請點擊 ↑↑↑
—————? 第二天? —————
————————————
假定20個隨機整數(shù)的值如下：
9，3，5，4，9，1，2，7，8，1，3，6，5，3，4，0，10，9 ，7，9
如何給這些無序的隨機整數(shù)排序呢？
非常簡單，讓我們遍歷這個無序的隨機數(shù)列，每一個整數(shù)按照其值對號入座，對應(yīng)數(shù)組下標的元素進行加1操作。
比如第一個整數(shù)是9，那么數(shù)組下標為9的元素加1：
第二個整數(shù)是3，那么數(shù)組下標為3的元素加1：
繼續(xù)遍歷數(shù)列并修改數(shù)組......
最終，數(shù)列遍歷完畢時，數(shù)組的狀態(tài)如下：
數(shù)組每一個下標位置的值，代表了數(shù)列中對應(yīng)整數(shù)出現(xiàn)的次數(shù)。
有了這個“統(tǒng)計結(jié)果”，排序就很簡單了。直接遍歷數(shù)組，輸出數(shù)組元素的下標值，元素的值是幾，就輸出幾次：
0，1，1，2，3，3，3，4，4，5，5，6，7，7，8，9，9，9，9，10
顯然，這個輸出的數(shù)列已經(jīng)是有序的了。
public static int[] countSort(int[] array) {
? ?//1.得到數(shù)列的最大值
? ?int max = array[0];
? ?for(int i=1; i<array.length; i++){
? ? ? ?if(array[i] > max){
? ? ? ? ? ?max = array[i];
? ? ? ?}
? ?}
? ?//2.根據(jù)數(shù)列最大值確定統(tǒng)計數(shù)組的長度
? ?int[] countArray = new int[max+1];
? ?//3.遍歷數(shù)列，填充統(tǒng)計數(shù)組
? ?for(int i=0; i<array.length; i++){
? ? ? ?countArray[array[i]]++;
? ?}
? ?//4.遍歷統(tǒng)計數(shù)組，輸出結(jié)果
? ?int index = 0;
? ?int[] sortedArray = new int[array.length];
? ?for(int i=0; i<countArray.length; i++){
? ? ? ?for(int j=0; j<countArray[i]; j++){
? ? ? ? ? ?sortedArray[index++] = i;
? ? ? ?}
? ?}
? ?return sortedArray;
}
public static void main(String[] args) {
? ?int[] array = new int[] {4,4,6,5,3,2,8,1,7,5,6,0,10};
? ?int[] sortedArray = countSort(array);
? ?System.out.println(Arrays.toString(sortedArray));
}
這段代碼在一開頭補充了一個步驟，就是求得數(shù)列的最大整數(shù)值max。后面創(chuàng)建的統(tǒng)計數(shù)組countArray，長度就是max+1，以此保證數(shù)組的最后一個下標是max。
95，94，91，98，99，90，99，93，91，92
怎么解決這個問題呢？
很簡單，我們不再以（輸入數(shù)列的最大值+1）作為統(tǒng)計數(shù)組的長度，而是以（數(shù)列最大值和最小值的差+1）作為統(tǒng)計數(shù)組的長度。
同時，數(shù)列的最小值作為一個偏移量，用于統(tǒng)計數(shù)組的對號入座。
以剛才的數(shù)列為例，統(tǒng)計數(shù)組的長度為? 99-90+1 = 10 ，偏移量等于數(shù)列的最小值 90 。
對于第一個整數(shù)95，對應(yīng)的統(tǒng)計數(shù)組下標是 95-90 = 5，如圖所示：
什么意思呢？讓我們看看下面的例子：
給定一個學生的成績表，要求按成績從低到高排序，如果成績相同，則遵循原表固有順序。
那么，當我們填充統(tǒng)計數(shù)組以后，我們只知道有兩個成績并列95分的小伙伴，卻不知道哪一個是小紅，哪一個是小綠：
下面的講解會有一些燒腦，請大家扶穩(wěn)坐好。我們?nèi)匀灰詣偛诺膶W生成績表為例，把之前的統(tǒng)計數(shù)組變形成下面的樣子：
這是如何變形的呢？統(tǒng)計數(shù)組從第二個元素開始，每一個元素都加上前面所有元素之和。
為什么要相加呢？初次看到的小伙伴可能會覺得莫名其妙。
這樣相加的目的，是讓統(tǒng)計數(shù)組存儲的元素值，等于相應(yīng)整數(shù)的最終排序位置。比如下標是9的元素值為5，代表原始數(shù)列的整數(shù)9，最終的排序是在第5位。
接下來，我們創(chuàng)建輸出數(shù)組sortedArray，長度和輸入數(shù)列一致。然后從后向前遍歷輸入數(shù)列：
第一步，我們遍歷成績表最后一行的小綠：
小綠是95分，我們找到countArray下標是5的元素，值是4，代表小綠的成績排名位置在第4位。
同時，我們給countArray下標是5的元素值減1，從4變成3,，代表著下次再遇到95分的成績時，最終排名是第3。
第二步，我們遍歷成績表倒數(shù)第二行的小白：
小白是94分，我們找到countArray下標是4的元素，值是2，代表小白的成績排名位置在第2位。
同時，我們給countArray下標是4的元素值減1，從2變成1,，代表著下次再遇到94分的成績時（實際上已經(jīng)遇不到了），最終排名是第1。
第三步，我們遍歷成績表倒數(shù)第三行的小紅：
小紅是95分，我們找到countArray下標是5的元素，值是3（最初是4，減1變成了3），代表小紅的成績排名位置在第3位。
同時，我們給countArray下標是5的元素值減1，從3變成2,，代表著下次再遇到95分的成績時（實際上已經(jīng)遇不到了），最終排名是第2。
這樣一來，同樣是95分的小紅和小綠就能夠清楚地排出順序了，也正因此，優(yōu)化版本的計數(shù)排序?qū)儆?strong>穩(wěn)定排序。
后面的遍歷過程以此類推，這里就不再詳細描述了。
public static int[] countSort(int[] array) {
? ?//1.得到數(shù)列的最大值和最小值，并算出差值d
? ?int max = array[0];
? ?int min = array[0];
? ?for(int i=1; i<array.length; i++) {
? ? ? ?if(array[i] > max) {
? ? ? ? ? ?max = array[i];
? ? ? ?}
? ? ? ?if(array[i] < min) {
? ? ? ? ? ?min = array[i];
? ? ? ?}
? ?}
? ?int d = max - min;
? ?//2.創(chuàng)建統(tǒng)計數(shù)組并統(tǒng)計對應(yīng)元素個數(shù)
? ?int[] countArray = new int[d+1];
? ?for(int i=0; i<array.length; i++) {
? ? ? ?countArray[array[i]-min]++;
? ?}
? ?//3.統(tǒng)計數(shù)組做變形，后面的元素等于前面的元素之和
? ?int sum = 0;
? ?for(int i=0;i<countArray.length;i++) {
? ? ? ?sum += countArray[i];
? ? ? ?countArray[i] = sum;
? ?}
? ?//4.倒序遍歷原始數(shù)列，從統(tǒng)計數(shù)組找到正確位置，輸出到結(jié)果數(shù)組
? ?int[] sortedArray = new int[array.length];
? ?for(int i=array.length-1;i>=0;i--) {
? ? ? ?sortedArray[countArray[array[i]-min]-1]=array[i];
? ? ? ?countArray[array[i]-min]--;
? ?}
? ?return sortedArray;
}
public static void main(String[] args) {
? ?int[] array = new int[] {95,94,91,98,99,90,99,93,91,92};
? ?int[] sortedArray = countSort(array);
? ?System.out.println(Arrays.toString(sortedArray));
}
1.當數(shù)列最大最小值差距過大時，并不適用計數(shù)排序。
比如給定20個隨機整數(shù)，范圍在0到1億之間，這時候如果使用計數(shù)排序，需要創(chuàng)建長度1億的數(shù)組。不但嚴重浪費空間，而且時間復雜度也隨之升高。
2.當數(shù)列元素不是整數(shù)，并不適用計數(shù)排序。
如果數(shù)列中的元素都是小數(shù)，比如25.213，或是0.00000001這樣子，則無法創(chuàng)建對應(yīng)的統(tǒng)計數(shù)組。這樣顯然無法進行計數(shù)排序。
完
1.微信群：
添加小編微信：tangguoyemeng，備注“進群+姓名+公司職位”即可，加入【云計算學習交流群】，和志同道合的朋友們共同打卡學習！
2.征稿：
投稿郵箱：lijy@csdn.net；微信號：tangguoyemeng。請備注投稿+姓名+公司職位。
推薦閱讀
為什么阿里飛豬、滴滴、攜程都被質(zhì)疑濫用大數(shù)據(jù)殺熟？
程序員入錯行怎么辦？
我們研究了1.5萬場活動，換個大城市生活可能對你有用
大數(shù)據(jù)揭秘: 原來單身女生有這些特點...
放棄培訓班自學編程，9 個月后我成為年薪 6 位數(shù)的軟件工程師
82歲的北大教授證明了黎曼猜想？
繼承變量覆蓋及構(gòu)造函數(shù)失配，竟然會導致這些漏洞
35歲IT老兵，轉(zhuǎn)型AI，我做錯了嗎？
↓↓↓??點擊【閱讀原文】查看「CSDN云計算」往期精彩內(nèi)容
總結(jié)
以上是生活随笔為你收集整理的云漫圈 | 计数排序，你真的了解么？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 军警安保专用制式手枪
- 下一篇： windows pe 怎么分区 Wind