8.計數排序
8.1 算法思想
計數排序是一個非基于比較的排序算法。它的優勢在于在對一定范圍內的整數排序時,它的復雜度為Ο(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 算法過程
- 找出待排序的數組中最大和最小的元素;
- 統計數組中每個值為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)創建一個長度為6的臨時存儲數組空間C,并將C數組每一個元素初始化為0。
b)統計重復元素的個數。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]
因為倒敘遍歷原數組,不會改變原來相等元素的相對位置,所以這是穩定的
簡而言之就是先統計出數組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;在繼續遍歷,6,小于等于6的元素個數為3,放在res[3-1]的位置。再繼續遍歷,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元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
