0.概述
01.算法分類
在排序算法中，根據時間復雜度的不同可以將排序算法分為兩類：
比較類排序
：通過比較來決定元素間的相對次序，由于其時間復雜度不能突破O(nlogn)（下限），因此稱為非線性時間比較類排序。
非比較類排序
：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運行，因此稱為線性時間非比較類排序。
02.算法復雜度
03.穩定和不穩定
穩定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不穩定：如果a原本在b的前面，而a=b，排序之后 a 可能會出現在 b 的后面。
一：比較類排序
交換排序
1. 冒泡排序
2. 快速排序
插入排序
3. 簡單插入排序
4. 希爾排序
選擇排序
5. 簡單選擇排序
6. 堆排序
歸并排序
7. 歸并排序
二：比較類排序
8. 計數排序
9.桶排序
10.基數排序
詳細介紹
1.冒泡排序
1.1算法思想
冒泡排序是一種簡單的排序算法。通過重復地遍歷要排序的數列，一次比較兩個元素，從最開始的一對到最后的一對（相當于一個長度為2的滑動窗口），如果它們的順序錯誤（看從小到達排列還是從大到小排列）就把它們交換過來。如果是升序排列的話，每次遍歷都會把最大值交換到最右邊。然后重復這個過程，直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頭部，就像冒泡一樣。
這個算法不需要額外的空間，空間復雜度為o（1），同時對n個數據要進行n-1次比較，才能將最大的數固定在數列尾部，所以要固定好n個數，需要進行（n-1）+（n-2）+……+1+0次操作，時間復雜度為o（n^2）
1.2算法過程
- 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
- 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對，這樣在最后的元素應該會是最大的數；
- 針對所有的元素重復以上的步驟，除了最后一個；
- 重復步驟1~3，直到排序完成。
1.3 python實現
def
bubbleSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
for
i
in
range
(
n
)
:
# i在這里起到一個類似于計數的作用，看目前有多少個數排好序了
for
j
in
range
(
n
-
i
-
1
)
:
# 由于目前數組中，有i+1個數已經固定到數組尾部，因此只要對前n-i-1對數進行比較即可
if
numList
[
j
]
>
numList
[
j
+
1
]
:
temp
=
numList
[
j
]
numList
[
j
]
=
numList
[
j
+
1
]
numList
[
j
+
1
]
=
temp
return
numList
numList
=
[
3
,
10
,
7
,
1
,
3
,
5
,
6
,
2
,
6
]
print
(
bubbleSort
(
numList
)
)
# 輸出結果為 ：[1, 2, 3, 3, 5, 6, 6, 7, 10]
2.快速排序
2.1 算法思想
快速排序是對冒泡排序的一種改進。通過一次排序（
設要排序的數組是A[0]……A[N-1]，首先任意選取一個數據（通常選用數組的第一個數）作為關鍵數據，然后將所有比它小的數都放到它左邊，所有比它大的數都放到它右邊，這個過程稱為一次快速排序
）將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
快速排序的時間復雜度為o（nlogn），空間復雜度為o（nlogn）
2.2 算法過程
- 從數列中挑出一個元素，稱為 “基準”（pivot），通常選取數組的第一個數；
- 遍歷數組，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊，因此這不是穩定的排序算法）。分區完成之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作；
- 遞歸把小于基準值元素的子數列和大于基準值元素的子數列排序，具體過程合步驟1、2一樣。
2.3 python實現
def
quickSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
pivot
=
numList
[
0
]
left
=
[
]
right
=
[
]
for
i
in
range
(
1
,
n
)
:
# 分區
if
numList
[
i
]
<
pivot
:
left
.
append
(
numList
[
i
]
)
else
:
right
.
append
(
numList
[
i
]
)
return
quickSort
(
left
)
+
[
pivot
]
+
quickSort
(
right
)
# 對左右兩個子數組粉筆進行快排，并連同基準值一塊返回
numlist
=
[
3
,
2
,
5
,
6
,
7
,
4
,
1
,
8
]
print
(
quickSort
(
numlist
)
)
# 輸出結果為：[1,2,3,4,5,6,7,8]
3. 插入排序（簡單插入排序）
3.1算法思想
如果有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入后此數據序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、長度增加1的有序數據。
插入排序的基本思想是：每步將一個待排序的記錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。
同樣，這個算法不需要額外的存儲空間，空間復雜度為o（1），時間復雜度為o（n^2）
3.2算法過程
- 從第一個元素開始，該元素可以認為已經被排序；
- 取出下一個元素，在已經排序的元素序列中從后向前掃描；
- 如果該元素（已排序）大于新元素，將該元素移到下一位置；
- 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；
- 將新元素插入到該位置后；
- 重復步驟2~5。直到排完序為止。
3.3 python實現
def
insertionSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
for
i
in
range
(
n
)
:
preIndex
=
i
-
1
current
=
numList
[
i
]
while
preIndex
>=
0
and
current
<
numList
[
preIndex
]
:
numList
[
preIndex
+
1
]
=
numList
[
preIndex
]
preIndex
-=
1
numList
[
preIndex
+
1
]
=
current
return
numList
numlist
=
[
5
,
3
,
2
,
1
,
6
,
8
,
4
,
2
,
6
]
print
(
insertionSort
(
numlist
)
)
# 輸出結果為：[1, 2, 2, 3, 4, 5, 6, 6, 8]
4.希爾排序（縮小增量排序）
4.1 算法思想
希爾排序是插入排序的一種優化，又稱“縮小增量排序”，是直接插入排序算法的一種更高效的改進版本。
希爾排序是把記錄
按下標的一定增量分組
，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。
先取一個正整數d1
4.2 算法分析
希爾排序的時間復雜度與增量序列的選取有關，例如希爾增量時間復雜度為O(n2)，而Hibbard增量的希爾排序的時間復雜度為O( n^(3/2) )，希爾排序時間復雜度的下界是n*log2n。希爾排序沒有快速排序算法快 O(n(logn))，因此中等大小規模表現良好，對規模非常大的數據排序不是最優選擇。
Shell排序的執行時間依賴于增量序列。
好的增量序列的共同特征：
① 最后一個增量必須為1；
② 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。
這種算法不需要額外的空間，時間復雜度為o(1)
4.3 算法過程
先將整個待排序的元素序列按照增量分割成為若干子序列分別進行直接插入排序，具體算法描述：
- 選擇一個增量序列t1，t2，…，tk，其中t1>t2>……>tk，tk=1；
- 按增量序列個數k，對序列進行k 次排序；
- 每次排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量為1 時，即把所有的元素進行一個插入排序處理，表長度即為整個序列的長度。
4.4 python代碼
def
shellSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
gap
=
n
//
2
while
gap
>=
1
:
for
i
in
range
(
gap
,
n
)
:
# 把前gap個空出來，以便進行各組之間的插入排序(插入排序也是把第一個元素空出來，當成已經排好序的序列)
tempindex
=
i
while
tempindex
>=
gap
and
numList
[
tempindex
-
gap
]
>
numList
[
tempindex
]
:
numList
[
i
-
gap
]
,
numList
[
tempindex
]
=
numList
[
tempindex
]
,
numList
[
tempindex
-
gap
]
tempindex
-=
gap
# 先把一個子序列中的元素排好序，某個子序列中的元素下標之間的間隔為gap
gap
=
gap
//
2
return
numList
numlist
=
[
4
,
5
,
7
,
8
,
6
,
1
,
2
,
3
,
4
]
print
(
shellSort
(
numlist
)
)
# 輸出結果為：[1, 2, 3, 4, 4, 5, 6, 7, 8]
5.選擇排序
5.1算法思想
選擇排序(Selection-sort)的工作原理：首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
這種算法不需要額外的空間，空間復雜度為o（1）。由于每找一個最小（大）元素，都要遍歷一遍這個數組，因此時間復雜度為o（n^2）
5.2算法過程
無序數組為num
- 初始狀態：num[0,1,……,n-1]，有序區為空；
- 第i次排序(i=1,2,3…n-1)開始時，當前有序區和無序區分別為num[0,1,……,i-1]以及num[i,……,n-1]。該趟排序從當前無序區中選出最小的元素 num[k]，將它與無序區的第1個元素交換，使num[1,……,i]和num[i+1……n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區；
- 當進行完n-1次排序之后，數組變成有序數組。
5.3舉例
例如:給定n=8，數組R中的8個元素的排序碼為(8,3,2,1,7,4,6,5),則直接選擇排序的過程如下
所示：
初始狀態 [ 8 3 2 1 7 4 6 5 ] 8<—>1
第一次 [ 1 3 2 8 7 4 6 5 ] 3 <—> 2
第二次 [ 1 2 3 8 7 4 6 5 ] 3 <—> 3
第三次 [ 1 2 3 8 7 4 6 5 ] 8<—> 4
第四次 [ 1 2 3 4 7 8 6 5 ] 7 <—> 5
第五次 [ 1 2 3 4 5 8 6 7 ] 8 <—>6
第六次 [ 1 2 3 4 5 6 8 7 ] 8 <—> 7
第七次 [ 1 2 3 4 5 6 7 8 ] 排序完成
5.4 python實現
def
selectionSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
minIndex
=
-
1
# 記錄當前最小值所在的下標
for
i
in
range
(
n
)
:
minIndex
=
i
for
j
in
range
(
i
+
1
,
n
)
:
if
numList
[
j
]
<
numList
[
minIndex
]
:
minIndex
=
j
temp
=
numList
[
i
]
numList
[
i
]
=
numList
[
minIndex
]
numList
[
minIndex
]
=
temp
return
numList
numlist
=
[
5
,
3
,
2
,
1
,
6
,
8
,
4
,
2
,
6
]
print
(
selectionSort
(
numlist
)
)
# 輸出結果為：[1, 2, 2, 3, 4, 5, 6, 6, 8]
6.堆排序
6.1算法思想
堆排序是指利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，并同時滿足堆的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點（同層節點不進行比較）。并且一般來說，升序排列通過構造大頂堆來實現，降序排列通過構造小頂堆來實現。
這種算法不用額外的空間，空間復雜度為o（1），時間復雜度為o（nlogn）
6.1.1堆
堆是一種完全二叉樹（完全二叉樹 是 一種除了最后一層之外的其他每一層都被完全填充，并且所有結點都保持向左對齊的樹）
堆有兩種類型: 大頂堆和小頂堆：
大頂堆：每個結點的值都大于或等于左右孩子結點
小頂堆：每個結點的值都小于或等于左右孩子結點
大頂堆和小頂堆可以通過下面的圖進行直觀的感受：
6.2 算法過程
- 首先將待排序的數組構造出一個大頂堆（這里以升序排列為例）
- 取出這個大頂堆的堆頂節點(最大值)，與堆的最下最右的元素進行交換，然后把剩下的元素再構造出一個大根堆。
- 重復第二步，直到這個大根堆的長度為1，此時完成排序
ps：將數組中的元素構造成大頂堆的時候，堆頂元素就是所有元素的最大值，而堆的最下最右是數組的最后一個元素，這就相當于把最大值放在了數組的最后，然后在對剩下的元素進行相同操作。
對于這個算法的具體過程的圖示，大家可以看一下堆排序圖解這篇博客。
過程動圖如下
6.3 python代碼
6.3.1 遞歸（不對原數組引入一個輔助元素）
global
length
# 定義全局變量
def
buildMaxHeap
(
numList
)
:
# 構建最大堆，
global
length
length
=
len
(
numList
)
for
i
in
range
(
length
//
2
,
-
1
,
-
1
)
:
# 從最后一個有子節點的根節點節點開始構建的時候從下往上，從右向左構建
heapify
(
numList
,
i
)
def
heapify
(
numList
,
i
)
:
# 堆調整，將剩下的元素調整成最大堆
global
left
,
right
,
largest
,
length
leftChildren
=
2
*
i
+
1
rightChildren
=
2
*
i
+
2
largest
=
i
if
leftChildren
<
length
and
numList
[
leftChildren
]
>
numList
[
largest
]
:
# leftChildren < length先判斷是否有子節點，因為python數組下標從零開始的緣故，下標為length/2的元素可能會沒有子節點。
largest
=
leftChildren
if
rightChildren
<
length
and
numList
[
rightChildren
]
>
numList
[
largest
]
:
largest
=
rightChildren
if
largest
!=
i
:
# 如果largest（最大的節點所在的下標），不是根節點，說明這三個借點不滿足堆的規則，
# 需要進行調整，根節點的下標是i，最大節點的下標是largest，交換即可。
swap
(
numList
,
i
,
largest
)
# 當當前的根節點和子節點滿足堆的關系之后，由子節點作為根節點的樹可能又不滿足了，必須在對下一層的樹進行檢查和調整。
heapify
(
numList
,
largest
)
def
swap
(
numList
,
i
,
j
)
:
numList
[
i
]
,
numList
[
j
]
=
numList
[
j
]
,
numList
[
i
]
def
heapSort
(
numList
)
:
global
length
buildMaxHeap
(
numList
)
for
i
in
range
(
len
(
numList
)
-
1
,
0
,
-
1
)
:
swap
(
numList
,
0
,
i
)
length
-=
1
# 在調整的時候就不會在調整最后一個元素了
heapify
(
numList
,
0
)
# 由于交換之前，已經都調整為最大堆了，而交換之后，大部分都符合堆的規則，
# 只從堆頂元素（下標為1）開始，只進行局部的調整就好，
# 這時候不用再像剛開始構建最大堆一樣從下往上，從右往左調整交換了。
return
numList
numlist
=
[
4
,
5
,
4
,
1
,
8
,
7
,
2
,
6
,
3
]
print
(
heapSort
(
numlist
)
)
6.3.2非遞歸（引入一個輔助因素，將數組的下標往后加1）
def
swap
(
arr
,
i
,
j
)
:
arr
[
i
]
,
arr
[
j
]
=
arr
[
j
]
,
arr
[
i
]
def
heapAdjust
(
arr
,
start
,
end
)
:
i
=
start
temp
=
arr
[
start
]
j
=
2
*
i
while
j
<=
end
:
if
j
<
end
and
arr
[
j
]
<
arr
[
j
+
1
]
:
j
+=
1
if
arr
[
i
]
<
arr
[
j
]
:
arr
[
i
]
=
arr
[
j
]
i
=
j
j
=
2
*
i
else
:
break
arr
[
i
]
=
temp
def
heapSort
(
numList
)
:
numList
.
insert
(
0
,
0
)
# 由于python，數組的下標從0開始，因此需要加入一個輔助元素，是所有的元素的下標都往后移動一位。
length
=
len
(
numList
)
-
1
firstAdjustRoot
=
length
//
2
for
i
in
range
(
firstAdjustRoot
)
:
# 在構造最大堆的時候，不會對最左側的0進行處理，因為i不會取到firstAdjustRoot。
heapAdjust
(
numList
,
firstAdjustRoot
-
i
,
length
)
for
i
in
range
(
length
-
1
)
:
swap
(
numList
,
1
,
length
-
i
)
# 由于大頂堆的堆頂元素是最大的，把它和數組最后的元素（堆的最下層最右元素）
# 進行互換，就相當于把最大值放在了最后，下一次，把最后一個元素撇出來，對剩下來的在排序
heapAdjust
(
numList
,
1
,
length
-
i
-
1
)
# 由于交換之前，已經都調整為最大堆了，而交換之后，大部分都符合堆的規則，
# 只從堆頂元素（下標為1）開始，只進行局部的調整就好，
# 這時候不用再像剛開始構建最大堆一樣從下往上，從右往左調整交換了。
return
[
numList
[
i
]
for
i
in
range
(
1
,
len
(
numList
)
)
]
numlist
=
[
50
,
16
,
30
,
10
,
60
,
90
,
2
,
80
,
70
]
print
(
heapSort
(
numlist
)
)
參考文章
有輔助元素的堆排序
https://www.cnblogs.com/chengxiao/p/6129630.html
https://www.cnblogs.com/onepixel/articles/7674659.html
7.歸并排序
7.1算法思想
歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
歸并排序是一種穩定的排序方法。時間復雜度為O(nlogn）。但是和的排序算法不同，歸并排序需要需要額外的空間，空間復雜度為o（n）。
7.2算法過程
歸并排序算法的過程是先分在合，即：
- 將一個序列從中間位置分成兩個序列；
- 在將這兩個子序列按照第一步繼續二分下去；
-
直到所有子序列的長度都為1，也就是不可以再二分截止。這時候再一步一步往上子序列兩兩合并，最終合并成一個有序序列即可。
詳細的過程可以通過下面這個圖來理解（來源于百度）：
7.3 python代碼
def
mergeSort
(
numList
)
:
if
len
(
numList
)
==
0
or
len
(
numList
)
==
1
:
return
numList
# 分，將原來的序列分成從中間分成兩個子序列
mid
=
len
(
numList
)
//
2
left
=
numList
[
:
mid
]
right
=
numList
[
mid
:
]
# 分別對左子序列和右子序列進行遞歸，得到排好序的左右子序列
sortedLeft
=
mergeSort
(
left
)
# 同樣的進行分分合合
sortedRight
=
mergeSort
(
right
)
# 將左右兩個排好序的子序列在合并成一個總的排好序的序列，并返回
return
merge
(
sortedLeft
,
sortedRight
)
def
merge
(
left
,
right
)
:
# 將兩個排好序的子序列合并成一個排好序的子序列
result
=
[
]
# 需要額外的存儲空間來存儲最后的排好序的結果，所以空間復雜度是o（n）
while
len
(
left
)
>
0
and
len
(
right
)
>
0
:
# left和right可能不等長。
if
left
[
0
]
<=
right
[
0
]
:
result
.
append
(
left
.
pop
(
0
)
)
else
:
result
.
append
(
right
.
pop
(
0
)
)
# 這里也可以不用pop，而是利用兩個移動指針，達到遍歷兩個數組的目的。
#最后根據兩個指針是否等于數組長度來判斷這個子序列里的元素是否已經都進入result中了。
# 循環結束，不管最后哪個非空，都加上就行。
result
+=
right
result
+=
left
return
result
numlist
=
[
2
,
4
,
7
,
5
,
8
,
1
,
3
,
6
]
print
(
mergeSort
(
numlist
)
)
# 輸出結果為：[1,2,3,4,5,6,7,8]
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]
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]
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]
參考文章
https://www.cnblogs.com/onepixel/articles/7674659.html
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
