8.計數排序
8.1 算法思想
計數排序是一個非基于比較的排序算法。它的優(yōu)勢在于在對一定范圍內的整數排序時，它的復雜度為Ο(n+k)（其中k是整數的范圍），當o（k）< o（nlogn）時快于任何比較排序算法。這是一種 犧牲空間換取時間 的做法，而且當O(k)>O(n log(n))的時候其效率反而不如基于比較的排序（基于比較的排序的時間復雜度在理論上的下限是O(n log(n)), 如歸并排序，堆排序）。 作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。
計數排序的基本思想是對于給定的輸入序列中的每一個元素x，確定該序列中值小于x的元素的個數（此處并非比較各元素的大小，而是通過對元素值的計數和計數值的累加來確定）。一旦有了這個信息，就可以將x直接存放到最終的輸出序列的正確位置上。
計數排序只需遍歷一次數據，在計數數組中記錄，輸出計數數組中有記錄的下標，時間復雜度為O(n+k)。
這種算法同時也有額外空間開銷計數數組和結果數組，空間復雜度為o（n+k）
8.2 算法過程
- 找出待排序的數組中最大和最小的元素；
- 統(tǒng)計數組中每個值為i的元素出現的次數，存入數組C的第i項； （由于這個原因，要排序的數必須在大于等于0，且由于時間復雜度的問題，數組元素的上限也有一定的限制，否則，時間復雜度不如比較類排序。）
- 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；
- 反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1.
8.2.1 算法舉例
以下說明下計數排序的過程。以《算法導論》這本書的一個例子進行說明：
初始化數組： A[2,5,3,0,2,3,0,3]
假設我們已經事先知道A數組的最大值5，排序過程如下：
a）創(chuàng)建一個長度為6的臨時存儲數組空間C，并將C數組每一個元素初始化為0。
b）統(tǒng)計重復元素的個數。A數組的元素作為數組C的下標，掃描數組A，A數組元素每出現一次，數組C等于該元素的下標位置的元素加一。例如第一次掃描到的是2，則C[2]=0+1=1,…,第五次再次掃描到了2，C[2]=1+1=2，說明這個數組2的個數為2個。C[2,0,2,3,0,1]
c）計算有多少（y）個元素小于或等于數組C的下標。根據計數數組累加得到C[2,2,4,7,7,8] (小于等于0的有2個，小于等于1的有2個，小于等于2的4個，…小于等于5的有8個)
d）倒序掃描數組A的元素x，依次將元素放置于輸出序列res[y]位置,y為小于或者等于這個元素的個數,同時臨時數組C[x]=C[x]-1;重復這個過程直至掃描到數組A的首位元素。res[0,0,2,2,3,3,3,5]
因為倒敘遍歷原數組，不會改變原來相等元素的相對位置，所以這是穩(wěn)定的
簡而言之就是先統(tǒng)計出數組A元素x小于或等于自身的元素個數y，將x放置于res[y]處，y-1，接著重復這個過程。
簡而言之
以[5,3,6,6]數組為例，小于等于5的元素個數為2，小于等于3的元素個數為1，小于等于6的元素個數為4。res = [0,0,0,0]，從后往前遍歷原數組，6，小于等于6的元素個數為4，最后一個6，放在res[4-1]的位置，這是在剩下的元素中，小于等于6的個數為4-1=3；在繼續(xù)遍歷，6，小于等于6的元素個數為3，放在res[3-1]的位置。再繼續(xù)遍歷，3，這時候小于等于3的元素個數為1，不變，放在res[1-1]的位置；5，小于等于5的元素個數為2，放在res[2-1]的位置。
8.3 python代碼
def
countingSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
maxVal
=
max
(
numList
)
countArr
=
[
0
for
i
in
range
(
maxVal
+
1
)
]
for
i
in
numList
:
countArr
[
i
]
+=
1
for
i
in
range
(
1
,
len
(
countArr
)
)
:
countArr
[
i
]
+=
countArr
[
i
-
1
]
res
=
[
0
for
i
in
range
(
n
)
]
for
i
in
range
(
n
-
1
,
-
1
,
-
1
)
:
res
[
countArr
[
numList
[
i
]
]
-
1
]
=
numList
[
i
]
countArr
[
numList
[
i
]
]
-=
1
# 必須要減1，由于待排序元素在res中的位置是由計數數組的值來決定的。
# 當遍歷了元素x之后，小于x的元素不會受影響，大于x的元素不會受影響，
# 只有等于x的元素會受影響，在往res中壓的時候，要比x的位置往前移動一位，
# 因此需要將計數數組中的下標為x的值減1，使得下次在遍歷到x的時候，
# 壓入的位置在前一個x的位置之前
return
res
numlist
=
[
5
,
8
,
9
,
3
,
2
,
5
,
1
,
6
,
8
]
print
(
countingSort
(
numlist
)
)
# 輸出結果為：[1, 2, 3, 5, 5, 6, 8, 8, 9]
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
