1 本節思路

之前的算法的最基本的思想是比較元素大小，所以算法復雜度最好是$\Theta (nlogn)$，本節不再基于元素比較，而是基于計數的Counting sort，然后應用在Radix sort上。

2 Counting sort

2.1 算法思想

Counting sort算法的思想比較簡單，就是通過統計每個數字的的個數確定每個數字的位置，譬如【8，6，2】這三個數，通過計數統計知道#8=1，#6=1，#2=1，很自然就是2排正位置1上，6排在位置1+1=2上，8排在位置2+1=3上，因為每個數字都是不重復，所以看起來很low，考慮到有充分數字的情況，就會領會到這個算法的巧妙之處了。

2.2 算法演示

2.3 算法描述

2.4 算法實現

# -*- coding: utf-8 -*- import collectionsdef counting_sort(A, B, k):# let C[0..k] be a new arrayC = [0] * (k + 1)for i in range(k + 1):C[i] = 0for j in range(1, len(A)):C[A[j]] = C[A[j]] + 1# C[i] now contains the number of elements equal to i.for i in range(1, k + 1):C[i] = C[i] + C[i - 1]# C[i] now contains the number of elements less than or equal to i.for j in range(len(A) - 1, 0, -1):B[C[A[j]]] = A[j]C[A[j]] = C[A[j]] - 1if __name__ == '__main__':A = ['x', 2, 5, 3, 0, 2, 3, 0, 3]B = [0] * len(A)k = max(A[1:])print('before sort:', A[1:])counting_sort(A, B, k)print('after sort:', B[1:])

運行結果：

before sort: [2, 5, 3, 0, 2, 3, 0, 3] after sort: [0, 0, 2, 2, 3, 3, 3, 5]

2.5 算法分析

容易得到Counting sort的算法復雜度是$O(k+n)$，k為集合中元素個數，n為排序序列中元素個數，因為$k<n$，所以可以認為這個算法是線性時間復雜度，其原因就是空間換時間，所以 其用途在于小范圍內的數據，如果數據范圍過大（排序的元素個數不一定很多）會占用大量的內存，下面Radix sort正好可以應用到這一點。

3 Radix sort

3.1 Radix sort算法思想

Radix sort按位從后至前排序，因為要防止重復數字問題，所以順序是從后至前。下面的演示很簡單的表達了這種思想：

3.2 算法描述

這里stable sort 指的是counting sort。

3.3 算法分析

• 考慮一個極端的情況，在一個b=32位的計算機上，每一個數字都可以表示為b個bit的序列，此時$b=lo{g}_{2}n$，應用上面的lemma8.3容易得到，在這種情況下使用RADIX-SORT的算法復雜度是$\Theta (b(n+2))=\Theta (logn(n+2))$，之前的基于“元素比較”排序算法沒有什么提高。
• 考慮另一個方向的極端情況，假如計算機內存超級大隨便用（不考慮緩存消耗），那么上面問題的復雜度是$\Theta (n+32)$，理論上完美，實際上不可信。
• 兩個極端的情況之間存在著一種權衡，這種權衡關系如下面lemma8.4所示，這個lemma8.4中使用適當的顆粒度r作為一位進行counting sort。

• 有點問題。。。待續。。。

總結

以上是生活随笔為你收集整理的八、计数排序及其应用分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。