0.概述
01.算法分類
在排序算法中，根據(jù)時間復(fù)雜度的不同可以將排序算法分為兩類：
比較類排序
：通過比較來決定元素間的相對次序，由于其時間復(fù)雜度不能突破O(nlogn)（下限），因此稱為非線性時間比較類排序。
非比較類排序
：不通過比較來決定元素間的相對次序，它可以突破基于比較排序的時間下界，以線性時間運(yùn)行，因此稱為線性時間非比較類排序。
02.算法復(fù)雜度
03.穩(wěn)定和不穩(wěn)定
穩(wěn)定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不穩(wěn)定：如果a原本在b的前面，而a=b，排序之后 a 可能會出現(xiàn)在 b 的后面。
一：比較類排序
交換排序
1. 冒泡排序
2. 快速排序
插入排序
3. 簡單插入排序
4. 希爾排序
選擇排序
5. 簡單選擇排序
6. 堆排序
歸并排序
7. 歸并排序
二：比較類排序
8. 計(jì)數(shù)排序
9.桶排序
10.基數(shù)排序
詳細(xì)介紹
1.冒泡排序
1.1算法思想
冒泡排序是一種簡單的排序算法。通過重復(fù)地遍歷要排序的數(shù)列，一次比較兩個元素，從最開始的一對到最后的一對（相當(dāng)于一個長度為2的滑動窗口），如果它們的順序錯誤（看從小到達(dá)排列還是從大到小排列）就把它們交換過來。如果是升序排列的話，每次遍歷都會把最大值交換到最右邊。然后重復(fù)這個過程，直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因?yàn)樵叫〉脑貢?jīng)由交換慢慢“浮”到數(shù)列的頭部，就像冒泡一樣。
這個算法不需要額外的空間，空間復(fù)雜度為o（1），同時對n個數(shù)據(jù)要進(jìn)行n-1次比較，才能將最大的數(shù)固定在數(shù)列尾部，所以要固定好n個數(shù)，需要進(jìn)行（n-1）+（n-2）+……+1+0次操作，時間復(fù)雜度為o（n^2）
1.2算法過程
- 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
- 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對，這樣在最后的元素應(yīng)該會是最大的數(shù)；
- 針對所有的元素重復(fù)以上的步驟，除了最后一個；
- 重復(fù)步驟1~3，直到排序完成。
1.3 python實(shí)現(xiàn)
def
bubbleSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
for
i
in
range
(
n
)
:
# i在這里起到一個類似于計(jì)數(shù)的作用，看目前有多少個數(shù)排好序了
for
j
in
range
(
n
-
i
-
1
)
:
# 由于目前數(shù)組中，有i+1個數(shù)已經(jīng)固定到數(shù)組尾部，因此只要對前n-i-1對數(shù)進(jìn)行比較即可
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
)
)
# 輸出結(jié)果為 ：[1, 2, 3, 3, 5, 6, 6, 7, 10]
2.快速排序
2.1 算法思想
快速排序是對冒泡排序的一種改進(jìn)。通過一次排序（
設(shè)要排序的數(shù)組是A[0]……A[N-1]，首先任意選取一個數(shù)據(jù)（通常選用數(shù)組的第一個數(shù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它左邊，所有比它大的數(shù)都放到它右邊，這個過程稱為一次快速排序
）將要排序的數(shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。
快速排序的時間復(fù)雜度為o（nlogn），空間復(fù)雜度為o（nlogn）
2.2 算法過程
- 從數(shù)列中挑出一個元素，稱為 “基準(zhǔn)”（pivot），通常選取數(shù)組的第一個數(shù)；
- 遍歷數(shù)組，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊，因此這不是穩(wěn)定的排序算法）。分區(qū)完成之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作；
- 遞歸把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序，具體過程合步驟1、2一樣。
2.3 python實(shí)現(xiàn)
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
)
:
# 分區(qū)
if
numList
[
i
]
<
pivot
:
left
.
append
(
numList
[
i
]
)
else
:
right
.
append
(
numList
[
i
]
)
return
quickSort
(
left
)
+
[
pivot
]
+
quickSort
(
right
)
# 對左右兩個子數(shù)組粉筆進(jìn)行快排，并連同基準(zhǔn)值一塊返回
numlist
=
[
3
,
2
,
5
,
6
,
7
,
4
,
1
,
8
]
print
(
quickSort
(
numlist
)
)
# 輸出結(jié)果為：[1,2,3,4,5,6,7,8]
3. 插入排序（簡單插入排序）
3.1算法思想
如果有一個已經(jīng)有序的數(shù)據(jù)序列，要求在這個已經(jīng)排好的數(shù)據(jù)序列中插入一個數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個時候就要用到一種新的排序方法——插入排序法,插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的、長度增加1的有序數(shù)據(jù)。
插入排序的基本思想是：每步將一個待排序的記錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的文件中適當(dāng)位置上，直到全部插入完為止。
同樣，這個算法不需要額外的存儲空間，空間復(fù)雜度為o（1），時間復(fù)雜度為o（n^2）
3.2算法過程
- 從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序；
- 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描；
- 如果該元素（已排序）大于新元素，將該元素移到下一位置；
- 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
- 將新元素插入到該位置后；
- 重復(fù)步驟2~5。直到排完序?yàn)橹埂?
3.3 python實(shí)現(xiàn)
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
)
)
# 輸出結(jié)果為：[1, 2, 2, 3, 4, 5, 6, 6, 8]
4.希爾排序（縮小增量排序）
4.1 算法思想
希爾排序是插入排序的一種優(yōu)化，又稱“縮小增量排序”，是直接插入排序算法的一種更高效的改進(jìn)版本。
希爾排序是把記錄
按下標(biāo)的一定增量分組
，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時，整個文件恰被分成一組，算法便終止。
先取一個正整數(shù)d1
4.2 算法分析
希爾排序的時間復(fù)雜度與增量序列的選取有關(guān)，例如希爾增量時間復(fù)雜度為O(n2)，而Hibbard增量的希爾排序的時間復(fù)雜度為O( n^(3/2) )，希爾排序時間復(fù)雜度的下界是n*log2n。希爾排序沒有快速排序算法快 O(n(logn))，因此中等大小規(guī)模表現(xiàn)良好，對規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇。
Shell排序的執(zhí)行時間依賴于增量序列。
好的增量序列的共同特征：
① 最后一個增量必須為1；
② 應(yīng)該盡量避免序列中的值(尤其是相鄰的值)互為倍數(shù)的情況。
這種算法不需要額外的空間，時間復(fù)雜度為o(1)
4.3 算法過程
先將整個待排序的元素序列按照增量分割成為若干子序列分別進(jìn)行直接插入排序，具體算法描述：
- 選擇一個增量序列t1，t2，…，tk，其中t1>t2>……>tk，tk=1；
- 按增量序列個數(shù)k，對序列進(jìn)行k 次排序；
- 每次排序，根據(jù)對應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進(jìn)行直接插入排序。僅增量為1 時，即把所有的元素進(jìn)行一個插入排序處理，表長度即為整個序列的長度。
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個空出來，以便進(jìn)行各組之間的插入排序(插入排序也是把第一個元素空出來，當(dāng)成已經(jīng)排好序的序列)
tempindex
=
i
while
tempindex
>=
gap
and
numList
[
tempindex
-
gap
]
>
numList
[
tempindex
]
:
numList
[
i
-
gap
]
,
numList
[
tempindex
]
=
numList
[
tempindex
]
,
numList
[
tempindex
-
gap
]
tempindex
-=
gap
# 先把一個子序列中的元素排好序，某個子序列中的元素下標(biāo)之間的間隔為gap
gap
=
gap
//
2
return
numList
numlist
=
[
4
,
5
,
7
,
8
,
6
,
1
,
2
,
3
,
4
]
print
(
shellSort
(
numlist
)
)
# 輸出結(jié)果為：[1, 2, 3, 4, 4, 5, 6, 7, 8]
5.選擇排序
5.1算法思想
選擇排序(Selection-sort)的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
這種算法不需要額外的空間，空間復(fù)雜度為o（1）。由于每找一個最小（大）元素，都要遍歷一遍這個數(shù)組，因此時間復(fù)雜度為o（n^2）
5.2算法過程
無序數(shù)組為num
- 初始狀態(tài)：num[0,1,……,n-1]，有序區(qū)為空；
- 第i次排序(i=1,2,3…n-1)開始時，當(dāng)前有序區(qū)和無序區(qū)分別為num[0,1,……,i-1]以及num[i,……,n-1]。該趟排序從當(dāng)前無序區(qū)中選出最小的元素 num[k]，將它與無序區(qū)的第1個元素交換，使num[1,……,i]和num[i+1……n]分別變?yōu)橛涗泜€數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)；
- 當(dāng)進(jìn)行完n-1次排序之后，數(shù)組變成有序數(shù)組。
5.3舉例
例如:給定n=8，數(shù)組R中的8個元素的排序碼為(8,3,2,1,7,4,6,5),則直接選擇排序的過程如下
所示：
初始狀態(tài) [ 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實(shí)現(xiàn)
def
selectionSort
(
numList
)
:
n
=
len
(
numList
)
if
n
==
0
or
n
==
1
:
return
numList
minIndex
=
-
1
# 記錄當(dāng)前最小值所在的下標(biāo)
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
)
)
# 輸出結(jié)果為：[1, 2, 2, 3, 4, 5, 6, 6, 8]
6.堆排序
6.1算法思想
堆排序是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)（同層節(jié)點(diǎn)不進(jìn)行比較）。并且一般來說，升序排列通過構(gòu)造大頂堆來實(shí)現(xiàn)，降序排列通過構(gòu)造小頂堆來實(shí)現(xiàn)。
這種算法不用額外的空間，空間復(fù)雜度為o（1），時間復(fù)雜度為o（nlogn）
6.1.1堆
堆是一種完全二叉樹（完全二叉樹 是 一種除了最后一層之外的其他每一層都被完全填充，并且所有結(jié)點(diǎn)都保持向左對齊的樹）
堆有兩種類型: 大頂堆和小頂堆：
大頂堆：每個結(jié)點(diǎn)的值都大于或等于左右孩子結(jié)點(diǎn)
小頂堆：每個結(jié)點(diǎn)的值都小于或等于左右孩子結(jié)點(diǎn)
大頂堆和小頂堆可以通過下面的圖進(jìn)行直觀的感受：
6.2 算法過程
- 首先將待排序的數(shù)組構(gòu)造出一個大頂堆（這里以升序排列為例）
- 取出這個大頂堆的堆頂節(jié)點(diǎn)(最大值)，與堆的最下最右的元素進(jìn)行交換，然后把剩下的元素再構(gòu)造出一個大根堆。
- 重復(fù)第二步，直到這個大根堆的長度為1，此時完成排序
ps：將數(shù)組中的元素構(gòu)造成大頂堆的時候，堆頂元素就是所有元素的最大值，而堆的最下最右是數(shù)組的最后一個元素，這就相當(dāng)于把最大值放在了數(shù)組的最后，然后在對剩下的元素進(jìn)行相同操作。
對于這個算法的具體過程的圖示，大家可以看一下堆排序圖解這篇博客。
過程動圖如下
6.3 python代碼
6.3.1 遞歸（不對原數(shù)組引入一個輔助元素）
global
length
# 定義全局變量
def
buildMaxHeap
(
numList
)
:
# 構(gòu)建最大堆，
global
length
length
=
len
(
numList
)
for
i
in
range
(
length
//
2
,
-
1
,
-
1
)
:
# 從最后一個有子節(jié)點(diǎn)的根節(jié)點(diǎn)節(jié)點(diǎn)開始構(gòu)建的時候從下往上，從右向左構(gòu)建
heapify
(
numList
,
i
)
def
heapify
(
numList
,
i
)
:
# 堆調(diào)整，將剩下的元素調(diào)整成最大堆
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先判斷是否有子節(jié)點(diǎn)，因?yàn)閜ython數(shù)組下標(biāo)從零開始的緣故，下標(biāo)為length/2的元素可能會沒有子節(jié)點(diǎn)。
largest
=
leftChildren
if
rightChildren
<
length
and
numList
[
rightChildren
]
>
numList
[
largest
]
:
largest
=
rightChildren
if
largest
!=
i
:
# 如果largest（最大的節(jié)點(diǎn)所在的下標(biāo)），不是根節(jié)點(diǎn)，說明這三個借點(diǎn)不滿足堆的規(guī)則，
# 需要進(jìn)行調(diào)整，根節(jié)點(diǎn)的下標(biāo)是i，最大節(jié)點(diǎn)的下標(biāo)是largest，交換即可。
swap
(
numList
,
i
,
largest
)
# 當(dāng)當(dāng)前的根節(jié)點(diǎn)和子節(jié)點(diǎn)滿足堆的關(guān)系之后，由子節(jié)點(diǎn)作為根節(jié)點(diǎn)的樹可能又不滿足了，必須在對下一層的樹進(jìn)行檢查和調(diào)整。
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
# 在調(diào)整的時候就不會在調(diào)整最后一個元素了
heapify
(
numList
,
0
)
# 由于交換之前，已經(jīng)都調(diào)整為最大堆了，而交換之后，大部分都符合堆的規(guī)則，
# 只從堆頂元素（下標(biāo)為1）開始，只進(jìn)行局部的調(diào)整就好，
# 這時候不用再像剛開始構(gòu)建最大堆一樣從下往上，從右往左調(diào)整交換了。
return
numList
numlist
=
[
4
,
5
,
4
,
1
,
8
,
7
,
2
,
6
,
3
]
print
(
heapSort
(
numlist
)
)
6.3.2非遞歸（引入一個輔助因素，將數(shù)組的下標(biāo)往后加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，數(shù)組的下標(biāo)從0開始，因此需要加入一個輔助元素，是所有的元素的下標(biāo)都往后移動一位。
length
=
len
(
numList
)
-
1
firstAdjustRoot
=
length
//
2
for
i
in
range
(
firstAdjustRoot
)
:
# 在構(gòu)造最大堆的時候，不會對最左側(cè)的0進(jìn)行處理，因?yàn)閕不會取到firstAdjustRoot。
heapAdjust
(
numList
,
firstAdjustRoot
-
i
,
length
)
for
i
in
range
(
length
-
1
)
:
swap
(
numList
,
1
,
length
-
i
)
# 由于大頂堆的堆頂元素是最大的，把它和數(shù)組最后的元素（堆的最下層最右元素）
# 進(jìn)行互換，就相當(dāng)于把最大值放在了最后，下一次，把最后一個元素撇出來，對剩下來的在排序
heapAdjust
(
numList
,
1
,
length
-
i
-
1
)
# 由于交換之前，已經(jīng)都調(diào)整為最大堆了，而交換之后，大部分都符合堆的規(guī)則，
# 只從堆頂元素（下標(biāo)為1）開始，只進(jìn)行局部的調(diào)整就好，
# 這時候不用再像剛開始構(gòu)建最大堆一樣從下往上，從右往左調(diào)整交換了。
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）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
歸并排序是一種穩(wěn)定的排序方法。時間復(fù)雜度為O(nlogn）。但是和的排序算法不同，歸并排序需要需要額外的空間，空間復(fù)雜度為o（n）。
7.2算法過程
歸并排序算法的過程是先分在合，即：
- 將一個序列從中間位置分成兩個序列；
- 在將這兩個子序列按照第一步繼續(xù)二分下去；
-
直到所有子序列的長度都為1，也就是不可以再二分截止。這時候再一步一步往上子序列兩兩合并，最終合并成一個有序序列即可。
詳細(xì)的過程可以通過下面這個圖來理解（來源于百度）：
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
:
]
# 分別對左子序列和右子序列進(jìn)行遞歸，得到排好序的左右子序列
sortedLeft
=
mergeSort
(
left
)
# 同樣的進(jìn)行分分合合
sortedRight
=
mergeSort
(
right
)
# 將左右兩個排好序的子序列在合并成一個總的排好序的序列，并返回
return
merge
(
sortedLeft
,
sortedRight
)
def
merge
(
left
,
right
)
:
# 將兩個排好序的子序列合并成一個排好序的子序列
result
=
[
]
# 需要額外的存儲空間來存儲最后的排好序的結(jié)果，所以空間復(fù)雜度是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，而是利用兩個移動指針，達(dá)到遍歷兩個數(shù)組的目的。
#最后根據(jù)兩個指針是否等于數(shù)組長度來判斷這個子序列里的元素是否已經(jīng)都進(jìn)入result中了。
# 循環(huán)結(jié)束，不管最后哪個非空，都加上就行。
result
+=
right
result
+=
left
return
result
numlist
=
[
2
,
4
,
7
,
5
,
8
,
1
,
3
,
6
]
print
(
mergeSort
(
numlist
)
)
# 輸出結(jié)果為：[1,2,3,4,5,6,7,8]
8.計(jì)數(shù)排序
8.1 算法思想
計(jì)數(shù)排序是一個非基于比較的排序算法。它的優(yōu)勢在于在對一定范圍內(nèi)的整數(shù)排序時，它的復(fù)雜度為Ο(n+k)（其中k是整數(shù)的范圍），當(dāng)o（k）< o（nlogn）時快于任何比較排序算法。這是一種 犧牲空間換取時間 的做法，而且當(dāng)O(k)>O(n log(n))的時候其效率反而不如基于比較的排序（基于比較的排序的時間復(fù)雜度在理論上的下限是O(n log(n)), 如歸并排序，堆排序）。 作為一種線性時間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。
計(jì)數(shù)排序的基本思想是對于給定的輸入序列中的每一個元素x，確定該序列中值小于x的元素的個數(shù)（此處并非比較各元素的大小，而是通過對元素值的計(jì)數(shù)和計(jì)數(shù)值的累加來確定）。一旦有了這個信息，就可以將x直接存放到最終的輸出序列的正確位置上。
計(jì)數(shù)排序只需遍歷一次數(shù)據(jù)，在計(jì)數(shù)數(shù)組中記錄，輸出計(jì)數(shù)數(shù)組中有記錄的下標(biāo)，時間復(fù)雜度為O(n+k)。
這種算法同時也有額外空間開銷計(jì)數(shù)數(shù)組和結(jié)果數(shù)組，空間復(fù)雜度為o（n+k）
8.2 算法過程
- 找出待排序的數(shù)組中最大和最小的元素；
- 統(tǒng)計(jì)數(shù)組中每個值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)； （由于這個原因，要排序的數(shù)必須在大于等于0，且由于時間復(fù)雜度的問題，數(shù)組元素的上限也有一定的限制，否則，時間復(fù)雜度不如比較類排序。）
- 對所有的計(jì)數(shù)累加（從C中的第一個元素開始，每一項(xiàng)和前一項(xiàng)相加）；
- 反向填充目標(biāo)數(shù)組：將每個元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個元素就將C(i)減去1.
8.2.1 算法舉例
以下說明下計(jì)數(shù)排序的過程。以《算法導(dǎo)論》這本書的一個例子進(jìn)行說明：
初始化數(shù)組： A[2,5,3,0,2,3,0,3]
假設(shè)我們已經(jīng)事先知道A數(shù)組的最大值5，排序過程如下：
a）創(chuàng)建一個長度為6的臨時存儲數(shù)組空間C，并將C數(shù)組每一個元素初始化為0。
b）統(tǒng)計(jì)重復(fù)元素的個數(shù)。A數(shù)組的元素作為數(shù)組C的下標(biāo)，掃描數(shù)組A，A數(shù)組元素每出現(xiàn)一次，數(shù)組C等于該元素的下標(biāo)位置的元素加一。例如第一次掃描到的是2，則C[2]=0+1=1,…,第五次再次掃描到了2，C[2]=1+1=2，說明這個數(shù)組2的個數(shù)為2個。C[2,0,2,3,0,1]
c）計(jì)算有多少（y）個元素小于或等于數(shù)組C的下標(biāo)。根據(jù)計(jì)數(shù)數(shù)組累加得到C[2,2,4,7,7,8] (小于等于0的有2個，小于等于1的有2個，小于等于2的4個，…小于等于5的有8個)
d）倒序掃描數(shù)組A的元素x，依次將元素放置于輸出序列res[y]位置,y為小于或者等于這個元素的個數(shù),同時臨時數(shù)組C[x]=C[x]-1;重復(fù)這個過程直至掃描到數(shù)組A的首位元素。res[0,0,2,2,3,3,3,5]
因?yàn)榈箶⒈闅v原數(shù)組，不會改變原來相等元素的相對位置，所以這是穩(wěn)定的
簡而言之就是先統(tǒng)計(jì)出數(shù)組A元素x小于或等于自身的元素個數(shù)y，將x放置于res[y]處，y-1，接著重復(fù)這個過程。
簡而言之
以[5,3,6,6]數(shù)組為例，小于等于5的元素個數(shù)為2，小于等于3的元素個數(shù)為1，小于等于6的元素個數(shù)為4。res = [0,0,0,0]，從后往前遍歷原數(shù)組，6，小于等于6的元素個數(shù)為4，最后一個6，放在res[4-1]的位置，這是在剩下的元素中，小于等于6的個數(shù)為4-1=3；在繼續(xù)遍歷，6，小于等于6的元素個數(shù)為3，放在res[3-1]的位置。再繼續(xù)遍歷，3，這時候小于等于3的元素個數(shù)為1，不變，放在res[1-1]的位置；5，小于等于5的元素個數(shù)為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中的位置是由計(jì)數(shù)數(shù)組的值來決定的。
# 當(dāng)遍歷了元素x之后，小于x的元素不會受影響，大于x的元素不會受影響，
# 只有等于x的元素會受影響，在往res中壓的時候，要比x的位置往前移動一位，
# 因此需要將計(jì)數(shù)數(shù)組中的下標(biāo)為x的值減1，使得下次在遍歷到x的時候，
# 壓入的位置在前一個x的位置之前
return
res
numlist
=
[
5
,
8
,
9
,
3
,
2
,
5
,
1
,
6
,
8
]
print
(
countingSort
(
numlist
)
)
# 輸出結(jié)果為：[1, 2, 3, 5, 5, 6, 8, 8, 9]
9.桶排序
9.1 算法思想
桶排序假設(shè)待排序的一組數(shù)均勻獨(dú)立的分布在一個范圍中，并將這一范圍劃分成幾個子范圍（桶）。然后基于某種映射函數(shù)f （ 高效與否的關(guān)鍵就在于這個映射函數(shù)的確定 ），將待排序列的關(guān)鍵字 k 映射到第i個桶中 (即桶數(shù)組B 的下標(biāo)i) ，那么該關(guān)鍵字k 就作為 B[i]中的元素。接著將各個桶中的數(shù)據(jù)分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排） 。然后依次枚舉輸出 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)的桶里去；
- 對每個不是空的桶進(jìn)行排序；
-
從不是空的桶里把排好序的數(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]
10.基數(shù)排序
10.1 算法思想
基數(shù)排序是對桶排序的擴(kuò)展。
第一類：最低位優(yōu)先法，簡稱LSD法：先從最低位開始排序，再對次低位排序，直到對最高位排序后得到一個有序序列；
第二類：最高位優(yōu)先法，簡稱MSD法：先從最高位開始排序，再逐個對各分組按次高位進(jìn)行子排序，循環(huán)直到最低位。（位沒有數(shù)的話，補(bǔ)0）
這里以LSD為例，由于待排序元素每一位上的數(shù)字的取值范圍是0—9，因此每按照某一位，需要10個桶，這樣每一位上相同的數(shù)字會分配到一個桶里。
10.2 算法過程
假設(shè)有一未排序數(shù)組：
3,44,38,5,47,15,36,26,27,2,46,4,19,50,48
首先根據(jù)個位數(shù)的數(shù)值，在遍歷數(shù)值時將它們分配至編號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,
第二步
接下來將這些桶中的數(shù)值重新串接起來，成為以下的數(shù)列：
50,2,3,44,4,5,15,36,26,46,47,27,38,48,19
接著再進(jìn)行一次分配，這次是根據(jù)十位數(shù)來分配：
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：
第三步
接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：
2,3,4,5,15,19,26,27,36,38,44,46,47,48,50
這時候整個數(shù)列已經(jīng)排序完畢。
如果排序的對象有三位數(shù)以上，則持續(xù)進(jìn)行以上的動作直至最高位數(shù)為止。
10.3 python代碼
def
getbit
(
num
,
i
)
:
# 獲取元素第i位的數(shù)
return
(
num
%
(
i
*
10
)
-
(
num
%
i
)
)
//
i
def
getMax
(
numList
)
:
# 獲取數(shù)組中的最大值
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
# 統(tǒng)計(jì)一下最大值的bitCount（有多少位），因?yàn)楸容^多少次，是有最大值的位數(shù)決定的
while
currentBit
<=
10
**
(
bitCount
-
1
)
:
# 開始循環(huán)的進(jìn)行每一個位的比較
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
)
)
# 輸出結(jié)果為：[1, 3, 12, 45, 214, 3543, 4553]
參考文章
https://www.cnblogs.com/onepixel/articles/7674659.html
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
