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