排序算法是《數(shù)據(jù)結(jié)構(gòu)與算法》中最基本的算法之一。排序算法可以分為內(nèi)部排序和外部排序,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序,而外部排序是因排序的數(shù)據(jù)很大,一次不能容納全部的排序記錄,在排序過(guò)程中需要訪問(wèn)外存。常見的內(nèi)部排序算法有:插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。以下是計(jì)數(shù)排序算法:
計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中。作為一種線性時(shí)間復(fù)雜度的排序,計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
1. 計(jì)數(shù)排序的特征當(dāng)輸入的元素是 n 個(gè) 0 到 k 之間的整數(shù)時(shí),它的運(yùn)行時(shí)間是 Θ(n + k)。計(jì)數(shù)排序不是比較排序,排序的速度快于任何比較排序算法。
由于用來(lái)計(jì)數(shù)的數(shù)組C的長(zhǎng)度取決于待排序數(shù)組中數(shù)據(jù)的范圍(等于待排序數(shù)組的最大值與最小值的差加上1),這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組,需要大量時(shí)間和內(nèi)存。例如:計(jì)數(shù)排序是用來(lái)排序0到100之間的數(shù)字的最好的算法,但是它不適合按字母順序排序人名。但是,計(jì)數(shù)排序可以用在基數(shù)排序中的算法來(lái)排序數(shù)據(jù)范圍很大的數(shù)組。
通俗地理解,例如有 10 個(gè)年齡不同的人,統(tǒng)計(jì)出有 8 個(gè)人的年齡比 A 小,那 A 的年齡就排在第 9 位,用這個(gè)方法可以得到其他每個(gè)人的位置,也就排好了序。當(dāng)然,年齡有重復(fù)時(shí)需要特殊處理(保證穩(wěn)定性),這就是為什么最后要反向填充目標(biāo)數(shù)組,以及將每個(gè)數(shù)字的統(tǒng)計(jì)減去 1 的原因。
?算法的步驟如下:
(1)找出待排序的數(shù)組中最大和最小的元素(2)統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù),存入數(shù)組C的第i項(xiàng)(3)對(duì)所有的計(jì)數(shù)累加(從C中的第一個(gè)元素開始,每一項(xiàng)和前一項(xiàng)相加)(4)反向填充目標(biāo)數(shù)組:將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng),每放一個(gè)元素就將C(i)減去12. 動(dòng)圖演示代碼實(shí)現(xiàn)JavaScript 實(shí)例 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實(shí)例 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實(shí)例 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實(shí)例 public class CountingSort implements IArraySort {? ? @Override? ? public int[] sort(int[] sourceArray) throws Exception {? ? ? ? // 對(duì) arr 進(jìn)行拷貝,不改變參數(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實(shí)例 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實(shí)例 #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
以上為計(jì)數(shù)排序算法詳細(xì)介紹,插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等排序算法各有優(yōu)缺點(diǎn),用一張圖概括:關(guān)于時(shí)間復(fù)雜度
平方階 (O(n2)) 排序 各類簡(jiǎn)單排序:直接插入、直接選擇和冒泡排序。
線性對(duì)數(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:"桶"的個(gè)數(shù)
In-place:占用常數(shù)內(nèi)存,不占用額外內(nèi)存
Out-place:占用額外內(nèi)存
穩(wěn)定性:排序后 2 個(gè)相等鍵值的順序和排序之前它們的順序相同