10.基數排序
10.1 算法思想
基數排序是對桶排序的擴展。
第一類：最低位優先法，簡稱LSD法：先從最低位開始排序，再對次低位排序，直到對最高位排序后得到一個有序序列；
第二類：最高位優先法，簡稱MSD法：先從最高位開始排序，再逐個對各分組按次高位進行子排序，循環直到最低位。（位沒有數的話，補0）
這里以LSD為例，由于待排序元素每一位上的數字的取值范圍是0—9，因此每按照某一位，需要10個桶，這樣每一位上相同的數字會分配到一個桶里。
10.2 算法過程
假設有一未排序數組：
3,44,38,5,47,15,36,26,27,2,46,4,19,50,48
首先根據個位數的數值，在遍歷數值時將它們分配至編號0到9的桶中：
0：50
1：
2： 2
3： 3
4： 44,4
5： 5,15
6：36,26,46
7：47,27
8：38,48
9：19,
第二步
接下來將這些桶中的數值重新串接起來，成為以下的數列：
50,2,3,44,4,5,15,36,26,46,47,27,38,48,19
接著再進行一次分配，這次是根據十位數來分配：
0：2,3,4,5
1：15,19
2：26,27
3：36,38
4：44,46,47,48
5：50,
6：
7：
8：
9：
第三步
接下來將這些桶子中的數值重新串接起來，成為以下的數列：
2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
這時候整個數列已經排序完畢。
如果排序的對象有三位數以上，則持續進行以上的動作直至最高位數為止。
10.3 python代碼
def
getbit
(
num
,
i
)
:
# 獲取元素第i位的數
return
(
num
%
(
i
*
10
)
-
(
num
%
i
)
)
//
i
def
getMax
(
numList
)
:
# 獲取數組中的最大值
if
len
(
numList
)
==
1
:
return
numList
[
0
]
maxNum
=
numList
[
0
]
for
i
in
range
(
len
(
numList
)
)
:
if
numList
[
i
]
>
maxNum
:
maxNum
=
numList
[
i
]
return
maxNum
def
radixSort
(
numList
)
:
if
len
(
numList
)
==
0
or
len
(
numList
)
==
1
:
return
numList
maxNum
=
getMax
(
numList
)
bitCount
=
0
index
=
1
while
maxNum
//
index
:
bitCount
+=
1
index
*=
10
currentBit
=
1
# 統計一下最大值的bitCount（有多少位），因為比較多少次，是有最大值的位數決定的
while
currentBit
<=
10
**
(
bitCount
-
1
)
:
# 開始循環的進行每一個位的比較
res
=
[
]
buckets
=
[
[
]
for
i
in
range
(
10
)
]
# 桶排序
for
i
in
numList
:
currentBitNum
=
getbit
(
i
,
currentBit
)
buckets
[
currentBitNum
]
.
append
(
i
)
for
i
in
range
(
10
)
:
for
j
in
range
(
len
(
buckets
[
i
]
)
)
:
res
.
append
(
buckets
[
i
]
[
j
]
)
numList
=
res
currentBit
*=
10
return
numList
numlist
=
[
12
,
3
,
45
,
3543
,
214
,
1
,
4553
]
print
(
radixSort
(
numlist
)
)
# 輸出結果為：[1, 3, 12, 45, 214, 3543, 4553]
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
