之前文章介紹的一些排序算法都是基于比較來(lái)進(jìn)行排序的，故它們?cè)谄骄闆r下的時(shí)間復(fù)雜度最好也不過(guò)是線性對(duì)數(shù)級(jí)別。這里我們來(lái)介紹一種簡(jiǎn)單的基于非比較的排序算法——Counting Sort 計(jì)數(shù)排序，其時(shí)間復(fù)雜度可以達(dá)到線性級(jí)別

基本思想

Counting Sort 計(jì)數(shù)排序，顧名思義，就是統(tǒng)計(jì)待排序數(shù)組元素的出現(xiàn)次數(shù)。其基本思想比較簡(jiǎn)單： 1. 根據(jù)待排序元素的數(shù)值范圍大小k(max-min+1)，建立一個(gè)k大小的頻數(shù)統(tǒng)計(jì)數(shù)組counts。對(duì)于counts數(shù)組而言，其索引范圍 0 ~ k-1，正好可以對(duì)應(yīng)到待排序元素的取值范圍min~max上 2. 統(tǒng)計(jì)待排序元素element的次數(shù)，并其存儲(chǔ)到counts數(shù)組中，即counts[ elemet-min ] = countValue 3. 待計(jì)數(shù)統(tǒng)計(jì)完成后遍歷counts數(shù)組，根據(jù)次數(shù)值來(lái)輸出原待排序元素值，此時(shí)即完成排序

這里給出計(jì)數(shù)排序在Java下的實(shí)現(xiàn)：

/*** 計(jì)數(shù)排序*/ public class CountingSort {/*** 升序排列 (非穩(wěn)定)*/public static void sort1() {// 獲取測(cè)試用例int[] array = getTestCase();int size = array.length;System.out.println("before sort: " + Arrays.toString(array) );// 求取最值int[] minMax = getMinMax(array);int min = minMax[0];int max = minMax[1];// 根據(jù)數(shù)據(jù)范圍創(chuàng)建統(tǒng)計(jì)數(shù)組int k = max-min+1;int[] counts = new int[ k ];// 統(tǒng)計(jì)原數(shù)組中元素出現(xiàn)的次數(shù)for(int i=0; i<size; i++) {int dataInCountIndex = array[i] - min; // 計(jì)算原數(shù)組元素在統(tǒng)計(jì)數(shù)組中的索引counts[dataInCountIndex] +=1; // 統(tǒng)計(jì)該值次數(shù)}int j = 0; // 有序的數(shù)據(jù)的插入位置for(int i=0; i<k; i++) {int originalData = i + min; // 還原 原排序數(shù)組的數(shù)據(jù)值while( counts[i]>0 ) {array[j] = originalData;counts[i]--; // 該數(shù)值出現(xiàn)的次數(shù)減1j++; // 更新有序數(shù)據(jù)的插入位置}}System.out.println("after sort: " + Arrays.toString(array) );} /*** 求指定數(shù)組的最值* @param array* @return [0]: 最小值; [1]: 最大值;*/private static int[] getMinMax(int[] array) {int min = array[0];int max = 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[] minMax = new int[]{min,max};return minMax;}/*** 獲取測(cè)試用例*/private static int[] getTestCase() {int[] caseArray = {-1,1,-1,1,2};return caseArray;} }

測(cè)試結(jié)果如下：

穩(wěn)定的計(jì)數(shù)排序

基本原理

上面的計(jì)數(shù)排序算法是非穩(wěn)定的，而一般我們所說(shuō)的計(jì)數(shù)排序都是穩(wěn)定的。那么如何保證計(jì)數(shù)排序的穩(wěn)定性呢？其實(shí)很簡(jiǎn)單，只需在統(tǒng)計(jì)完待排序元素的頻數(shù)后，對(duì)counts作累加計(jì)算（counts[i] = counts[i-1] + counts[i]），即計(jì)算統(tǒng)計(jì)數(shù)組中指定索引位置上的元素在排序后的位置；然后倒序遍歷原數(shù)組，根據(jù)counts數(shù)組中的排序位置來(lái)將待排序元素放入合適的位置，同時(shí)將counts數(shù)組相應(yīng)的值減1，以使下一個(gè)重復(fù)的排序元素可以放在前一位的位置上，以保證穩(wěn)定性

算法圖解

下圖即是通過(guò)穩(wěn)定的計(jì)數(shù)排序?qū)?-1,1,-1,1,2 序列進(jìn)行升序排列的圖解過(guò)程

1. 建立counts數(shù)組

2. 倒序遍歷原待排序數(shù)組，按升序排列

Java實(shí)現(xiàn)

這里給出計(jì)數(shù)排序在Java下的實(shí)現(xiàn)：

/*** 計(jì)數(shù)排序*/ public class CountingSort {.../*** 升序排列 (穩(wěn)定)*/public static void sort2() {// 獲取測(cè)試用例int[] array = getTestCase();int size = array.length;System.out.println("before sort: " + Arrays.toString(array) );// 求取最值int[] minMax = getMinMax(array);int min = minMax[0];int max = minMax[1];// 根據(jù)數(shù)據(jù)范圍創(chuàng)建統(tǒng)計(jì)數(shù)組int k = max-min+1;int[] counts = new int[ k ];// 統(tǒng)計(jì)原數(shù)組中元素出現(xiàn)的次數(shù)for(int i=0; i<size; i++) {int dataInCountIndex = array[i] - min; // 計(jì)算原數(shù)組元素在統(tǒng)計(jì)數(shù)組中的索引counts[dataInCountIndex] +=1; // 統(tǒng)計(jì)該值次數(shù)}// 計(jì)算統(tǒng)計(jì)數(shù)組的累計(jì)值，即計(jì)算 統(tǒng)計(jì)數(shù)組中指定索引位置上的元素在排序后的位置// 如果該索引位置上有重復(fù)元素，則為重復(fù)元素所占的最大排序位置for(int i=1; i<k; i++) {counts[i] = counts[i-1] + counts[i];}int[] sortedArray = new int[size]; // 排序結(jié)果數(shù)組// 倒序遍歷原數(shù)組，保證穩(wěn)定性for(int i=size-1; i>=0; i--) {int dataInCountIndex = array[i] - min; // 計(jì)算原數(shù)組元素在統(tǒng)計(jì)數(shù)組中的索引// 計(jì)算其排序后的位置, 因?yàn)閿?shù)組索引從0開始計(jì)算，故應(yīng)對(duì)排序位置減1// 例如，排在最前面的元素，排序位置為1，則其在數(shù)組中的位置索引應(yīng)為0int sortIndex = counts[dataInCountIndex] - 1;sortedArray[sortIndex] = array[i]; // 將原數(shù)組元素放入排序后的位置上counts[dataInCountIndex]--; // 下一個(gè)重復(fù)的元素，應(yīng)排前一個(gè)位置，以保證穩(wěn)定性}System.out.println("after sort: " + Arrays.toString(sortedArray) );}... }

測(cè)試結(jié)果如下：

特點(diǎn)

復(fù)雜度、穩(wěn)定性

這里以穩(wěn)定的計(jì)數(shù)排序進(jìn)行說(shuō)明：

缺陷

計(jì)數(shù)排序只能適用待排序元素為整數(shù)的場(chǎng)景

待排序元素的數(shù)值范圍(極差)過(guò)大的情況下，計(jì)數(shù)排序會(huì)浪費(fèi)大量空間，故一般不推薦使用計(jì)數(shù)排序

參考文獻(xiàn)

算法導(dǎo)論 · 第3版

總結(jié)

以上是生活随笔為你收集整理的倒序排序_排序算法(六)：Counting Sort 计数排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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