9.桶排序
9.1 算法思想
桶排序假設(shè)待排序的一組數(shù)均勻獨立的分布在一個范圍中，并將這一范圍劃分成幾個子范圍（桶）。然后基于某種映射函數(shù)f （ 高效與否的關(guān)鍵就在于這個映射函數(shù)的確定 ），將待排序列的關(guān)鍵字 k 映射到第i個桶中 (即桶數(shù)組B 的下標(biāo)i) ，那么該關(guān)鍵字k 就作為 B[i]中的元素。接著將各個桶中的數(shù)據(jù)分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排） 。然后依次枚舉輸出 B[0]….B[M] 中的全部內(nèi)容即完成了一個數(shù)組的桶排列。
ps：桶排序可以有很多方法，具體區(qū)別在于映射函數(shù)、桶、以及桶內(nèi)排序的方法不同。
由于要構(gòu)造桶，因此需要額外的空間，空間復(fù)雜度為o（n+k），時間復(fù)雜度為o（n+k），最好是o(N)，且桶排序是穩(wěn)定的。
9.2 算法過程
- 設(shè)置一個定量的數(shù)組當(dāng)作空桶；（當(dāng)數(shù)字少的時候，可以設(shè)置n個桶，只把相等的數(shù)放在同一個桶，不過這種方法空桶過多，數(shù)字多的時候回消耗極大的空間。數(shù)字多的時候可以少設(shè)置幾個桶，利用映射關(guān)系將多個數(shù)放在一個桶。） （類似于系統(tǒng)抽樣，是指盡可能均勻分布在各個桶里）
- 遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)映射完之后，一個一個放到對應(yīng)的桶里去；
- 對每個不是空的桶進行排序；
-
從不是空的桶里把排好序的數(shù)據(jù)拼接起來。
桶的數(shù)量等于待排序元素數(shù)量展示，其中范圍分別是[0,9),[10,19),……，[90,99)
9.3 python代碼
def
bucktetSort
(
numList
,
bucketNum
)
:
if
len
(
numList
)
==
0
or
len
(
numList
)
==
1
:
return
numList
maxNum
=
numList
[
0
]
minNum
=
numList
[
0
]
for
i
in
range
(
1
,
len
(
numList
)
)
:
# 找到最大最小值
if
numList
[
i
]
<
minNum
:
minNum
=
numList
[
i
]
elif
numList
[
i
]
>
maxNum
:
maxNum
=
numList
[
i
]
else
:
continue
bucketSize
=
(
maxNum
-
minNum
+
1
)
//
bucketNum
# 根據(jù)桶的數(shù)量找到每個桶的范圍
buckets
=
[
[
]
for
i
in
range
(
bucketNum
)
]
for
i
in
range
(
len
(
numList
)
)
:
# 將各個數(shù)分配到各個桶
buckets
[
(
numList
[
i
]
-
minNum
)
//
bucketSize
]
.
append
(
numList
[
i
]
)
for
i
in
range
(
bucketNum
)
:
# 桶內(nèi)排序，可以使用各種排序方法
buckets
[
i
]
.
sort
(
)
res
=
[
]
for
i
in
range
(
len
(
buckets
)
)
:
# 分別將各個桶內(nèi)的數(shù)提出來，壓入結(jié)果
for
j
in
range
(
len
(
buckets
[
i
]
)
)
:
res
.
append
(
buckets
[
i
]
[
j
]
)
return
res
numlist
=
[
11
,
34
,
23
,
56
,
8
,
20
,
66
,
45
,
54
,
87
,
78
]
print
(
bucktetSort
(
numlist
,
5
)
)
# 利用5個桶
# 輸出結(jié)果為：[8, 11, 20, 23, 34, 45, 54, 56, 66, 78, 87]
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
