排序算法是《數(shù)據(jù)結(jié)構(gòu)與算法》中最基本的算法之一。排序算法可以分為內(nèi)部排序和外部排序,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序,而外部排序是因排序的數(shù)據(jù)很大,一次不能容納全部的排序記錄,在排序過程中需要訪問外存。常見的內(nèi)部排序算法有:插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。以下是計數(shù)排序算法:
計數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲在額外開辟的數(shù)組空間中。作為一種線性時間復(fù)雜度的排序,計數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
1. 計數(shù)排序的特征當(dāng)輸入的元素是 n 個 0 到 k 之間的整數(shù)時,它的運行時間是 Θ(n + k)。計數(shù)排序不是比較排序,排序的速度快于任何比較排序算法。
由于用來計數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍(等于待排序數(shù)組的最大值與最小值的差加上1),這使得計數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組,需要大量時間和內(nèi)存。例如:計數(shù)排序是用來排序0到100之間的數(shù)字的最好的算法,但是它不適合按字母順序排序人名。但是,計數(shù)排序可以用在基數(shù)排序中的算法來排序數(shù)據(jù)范圍很大的數(shù)組。
通俗地理解,例如有 10 個年齡不同的人,統(tǒng)計出有 8 個人的年齡比 A 小,那 A 的年齡就排在第 9 位,用這個方法可以得到其他每個人的位置,也就排好了序。當(dāng)然,年齡有重復(fù)時需要特殊處理(保證穩(wěn)定性),這就是為什么最后要反向填充目標數(shù)組,以及將每個數(shù)字的統(tǒng)計減去 1 的原因。
?算法的步驟如下:
(1)找出待排序的數(shù)組中最大和最小的元素(2)統(tǒng)計數(shù)組中每個值為i的元素出現(xiàn)的次數(shù),存入數(shù)組C的第i項(3)對所有的計數(shù)累加(從C中的第一個元素開始,每一項和前一項相加)(4)反向填充目標數(shù)組:將每個元素i放在新數(shù)組的第C(i)項,每放一個元素就將C(i)減去12. 動圖演示代碼實現(xiàn)JavaScript 實例 function countingSort(arr, maxValue) {? ? var bucket = new Array(maxValue+1),? ? ? ? sortedIndex = 0;? ? ? ? arrLen = arr.length,? ? ? ? bucketLen = maxValue + 1;? ? for (var i = 0; i < arrLen; i++) {? ? ? ? if (!bucket[arr[i]]) {? ? ? ? ? ? bucket[arr[i]] = 0;? ? ? ? }? ? ? ? bucket[arr[i]]++;? ? }? ? for (var j = 0; j < bucketLen; j++) {? ? ? ? while(bucket[j] > 0) {? ? ? ? ? ? arr[sortedIndex++] = j;? ? ? ? ? ? bucket[j]--;? ? ? ? }? ? }? ? return arr;}Python實例 def countingSort(arr, maxValue):? ? bucketLen = maxValue+1? ? bucket = [0]*bucketLen? ? sortedIndex =0? ? arrLen = len(arr)? ? for i in range(arrLen):? ? ? ? if not bucket[arr[i]]:? ? ? ? ? ? bucket[arr[i]]=0? ? ? ? bucket[arr[i]]+=1? ? for j in range(bucketLen):? ? ? ? while bucket[j]>0:? ? ? ? ? ? arr[sortedIndex] = j? ? ? ? ? ? sortedIndex+=1? ? ? ? ? ? bucket[j]-=1? ? return arrGo實例 func countingSort(arr []int, maxValue int) []int {? ? ? ? bucketLen := maxValue + 1? ? ? ? bucket := make([]int, bucketLen) // 初始為0的數(shù)組? ? ? ? sortedIndex := 0? ? ? ? length := len(arr)? ? ? ? for i := 0; i < length; i++ {? ? ? ? ? ? ? ? bucket[arr[i]] += 1? ? ? ? }? ? ? ? for j := 0; j < bucketLen; j++ {? ? ? ? ? ? ? ? for bucket[j] > 0 {? ? ? ? ? ? ? ? ? ? ? ? arr[sortedIndex] = j? ? ? ? ? ? ? ? ? ? ? ? sortedIndex += 1? ? ? ? ? ? ? ? ? ? ? ? bucket[j] -= 1? ? ? ? ? ? ? ? }? ? ? ? }? ? ? ? return arr}Java實例 public class CountingSort implements IArraySort {? ? @Override? ? public int[] sort(int[] sourceArray) throws Exception {? ? ? ? // 對 arr 進行拷貝,不改變參數(shù)內(nèi)容? ? ? ? int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);? ? ? ? int maxValue = getMaxValue(arr);? ? ? ? return countingSort(arr, maxValue);? ? }? ? private int[] countingSort(int[] arr, int maxValue) {? ? ? ? int bucketLen = maxValue + 1;? ? ? ? int[] bucket = new int[bucketLen];? ? ? ? for (int value : arr) {? ? ? ? ? ? bucket[value]++;? ? ? ? }? ? ? ? int sortedIndex = 0;? ? ? ? for (int j = 0; j < bucketLen; j++) {? ? ? ? ? ? while (bucket[j] > 0) {? ? ? ? ? ? ? ? arr[sortedIndex++] = j;? ? ? ? ? ? ? ? bucket[j]--;? ? ? ? ? ? }? ? ? ? }? ? ? ? return arr;? ? }? ? private int getMaxValue(int[] arr) {? ? ? ? int maxValue = arr[0];? ? ? ? for (int value : arr) {? ? ? ? ? ? if (maxValue < value) {? ? ? ? ? ? ? ? maxValue = value;? ? ? ? ? ? }? ? ? ? }? ? ? ? return maxValue;? ? }}PHP實例 function countingSort($arr, $maxValue = null){? ? if ($maxValue === null) {? ? ? ? $maxValue = max($arr);? ? }? ? for ($m = 0; $m < $maxValue + 1; $m++) {? ? ? ? $bucket[] = null;? ? }? ? $arrLen = count($arr);? ? for ($i = 0; $i < $arrLen; $i++) {? ? ? ? if (!array_key_exists($arr[$i], $bucket)) {? ? ? ? ? ? $bucket[$arr[$i]] = 0;? ? ? ? }? ? ? ? $bucket[$arr[$i]]++;? ? }? ? $sortedIndex = 0;? ? foreach ($bucket as $key => $len) {? ? ? ? ? ? ? ? if($len !== null){? ? ? ? ? ? for($j = 0; $j < $len; $j++){? ? ? ? ? ? ? ? $arr[$sortedIndex++] = $key;? ? ? ? ? ? }? ? ? ? }? ? }? ? return $arr;}C實例 #include參考地址:
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/8.countingSort.md
https://zh.wikipedia.org/wiki/%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F
以上為計數(shù)排序算法詳細介紹,插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等排序算法各有優(yōu)缺點,用一張圖概括:關(guān)于時間復(fù)雜度
平方階 (O(n2)) 排序 各類簡單排序:直接插入、直接選擇和冒泡排序。
線性對數(shù)階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序;
O(n1+§)) 排序,§ 是介于 0 和 1 之間的常數(shù)。 希爾排序
線性階 (O(n)) 排序 基數(shù)排序,此外還有桶、箱排序。
關(guān)于穩(wěn)定性
穩(wěn)定的排序算法:冒泡排序、插入排序、歸并排序和基數(shù)排序。
不是穩(wěn)定的排序算法:選擇排序、快速排序、希爾排序、堆排序。
名詞解釋:
n:數(shù)據(jù)規(guī)模
k:"桶"的個數(shù)
In-place:占用常數(shù)內(nèi)存,不占用額外內(nèi)存
Out-place:占用額外內(nèi)存
穩(wěn)定性:排序后 2 個相等鍵值的順序和排序之前它們的順序相同