9.桶排序
9.1 算法思想
桶排序假設(shè)待排序的一組數(shù)均勻獨(dú)立的分布在一個(gè)范圍中，并將這一范圍劃分成幾個(gè)子范圍（桶）。然后基于某種映射函數(shù)f （ 高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定 ），將待排序列的關(guān)鍵字 k 映射到第i個(gè)桶中 (即桶數(shù)組B 的下標(biāo)i) ，那么該關(guān)鍵字k 就作為 B[i]中的元素。接著將各個(gè)桶中的數(shù)據(jù)分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排） 。然后依次枚舉輸出 B[0]….B[M] 中的全部?jī)?nèi)容即完成了一個(gè)數(shù)組的桶排列。
ps：桶排序可以有很多方法，具體區(qū)別在于映射函數(shù)、桶、以及桶內(nèi)排序的方法不同。
由于要構(gòu)造桶，因此需要額外的空間，空間復(fù)雜度為o（n+k），時(shí)間復(fù)雜度為o（n+k），最好是o(N)，且桶排序是穩(wěn)定的。
9.2 算法過(guò)程
- 設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶；（當(dāng)數(shù)字少的時(shí)候，可以設(shè)置n個(gè)桶，只把相等的數(shù)放在同一個(gè)桶，不過(guò)這種方法空桶過(guò)多，數(shù)字多的時(shí)候回消耗極大的空間。數(shù)字多的時(shí)候可以少設(shè)置幾個(gè)桶，利用映射關(guān)系將多個(gè)數(shù)放在一個(gè)桶。） （類似于系統(tǒng)抽樣，是指盡可能均勻分布在各個(gè)桶里）
- 遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)映射完之后，一個(gè)一個(gè)放到對(duì)應(yīng)的桶里去；
- 對(duì)每個(gè)不是空的桶進(jìn)行排序；
-
從不是空的桶里把排好序的數(shù)據(jù)拼接起來(lái)。
桶的數(shù)量等于待排序元素?cái)?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ù)量找到每個(gè)桶的范圍
buckets
=
[
[
]
for
i
in
range
(
bucketNum
)
]
for
i
in
range
(
len
(
numList
)
)
:
# 將各個(gè)數(shù)分配到各個(gè)桶
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
)
)
:
# 分別將各個(gè)桶內(nèi)的數(shù)提出來(lái)，壓入結(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個(gè)桶
# 輸出結(jié)果為：[8, 11, 20, 23, 34, 45, 54, 56, 66, 78, 87]
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(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ì)您有幫助就好】元
