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