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