話不多數(shù)，先上兩張圖：
名詞解釋：
n：數(shù)據(jù)規(guī)模
k：“桶”的個(gè)數(shù)
In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存
Out-place：占用額外內(nèi)存
穩(wěn)定性：排序后2個(gè)相等鍵值的順序和排序之前它們的順序相同
冒泡排序（Bubble Sort）
冒泡排序須知：
冒泡排序每次找出一個(gè)最大的元素，因此需要遍歷 n-1 次。還有一種優(yōu)化算法，就是立一個(gè)flag，當(dāng)在一趟序列遍歷中元素沒有發(fā)生交換，則證明該序列已經(jīng)有序。但這種改進(jìn)對(duì)于提升性能來說并沒有什么太大作用。
什么時(shí)候最快（Best Cases）：
當(dāng)輸入的數(shù)據(jù)已經(jīng)是正序時(shí)。
什么時(shí)候最慢（Worst Cases）：
當(dāng)輸入的數(shù)據(jù)是反序時(shí)。
冒泡排序動(dòng)圖演示：
冒泡排序 Python 代碼實(shí)現(xiàn)：
def bubbleSort(nums):
for i in range(len(nums) - 1): # 遍歷 len(nums)-1 次
for j in range(len(nums) - i - 1): # 已排好序的部分不用再次遍歷
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j] # Python 交換兩個(gè)數(shù)不用中間變量
return nums
選擇排序（Selection Sort）
選擇排序須知：
選擇排序不受輸入數(shù)據(jù)的影響，即在任何情況下時(shí)間復(fù)雜度不變。選擇排序每次選出最小的元素，因此需要遍歷 n-1 次。
選擇排序動(dòng)圖演示：
選擇排序 Python 代碼實(shí)現(xiàn)：
def selectionSort(nums):
for i in range(len(nums) - 1): # 遍歷 len(nums)-1 次
minIndex = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[minIndex]: # 更新最小值索引
minIndex = j
nums[i], nums[minIndex] = nums[minIndex], nums[i] # 把最小數(shù)交換到前面
return nums
插入排序（Insertion Sort）
插入排序須知：
插入排序如同打撲克一樣，每次將后面的牌插到前面已經(jīng)排好序的牌中。插入排序有一種優(yōu)化算法，叫做拆半插入。因?yàn)榍懊媸蔷植颗藕玫男蛄?，因此可以用折半查找的方法將牌插入到正確的位置，而不是從后往前一一比對(duì)。折半查找只是減少了比較次數(shù)，但是元素的移動(dòng)次數(shù)不變，所以時(shí)間復(fù)雜度仍為 O(n^2) ！
插入排序動(dòng)圖演示：
插入排序 Python 代碼實(shí)現(xiàn)：
def insertionSort(nums):
for i in range(len(nums) - 1): # 遍歷 len(nums)-1 次
curNum, preIndex = nums[i+1], i # curNum 保存當(dāng)前待插入的數(shù)
while preIndex >= 0 and curNum < nums[preIndex]: # 將比 curNum 大的元素向后移動(dòng)
nums[preIndex + 1] = nums[preIndex]
preIndex -= 1
nums[preIndex + 1] = curNum # 待插入的數(shù)的正確位置
return nums
希爾排序（Shell Sort）
希爾排序須知：
希爾排序是插入排序的一種更高效率的實(shí)現(xiàn)。它與插入排序的不同之處在于，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素。
【例子】對(duì)于待排序列 {44，12，59，36，62，43，94，7，35，52，85}，我們可設(shè)定增量序列為 {5，3，1}。
【解析】第一個(gè)增量為 5，因此 {44，43，85}、{12，94}、{59，7}、{36，35}、{62，52} 分別隸屬于同一個(gè)子序列，子序列內(nèi)部進(jìn)行插入排序；然后選取第二個(gè)增量3，因此 {43，35，94，62}、{12，52，59，85}、{7，44，36} 分別隸屬于同一個(gè)子序列；最后一個(gè)增量為 1，這一次排序相當(dāng)于簡單插入排序，但是經(jīng)過前兩次排序，序列已經(jīng)基本有序，因此此次排序時(shí)間效率就提高了很多。希爾排序過程如下：
希爾排序的核心在于間隔序列的設(shè)定。既可以提前設(shè)定好間隔序列，也可以動(dòng)態(tài)的定義間隔序列。動(dòng)態(tài)定義間隔序列的算法是《算法（第4版》的合著者 Robert Sedgewick 提出的。在這里，我就使用了這種方法。
希爾排序 Python 代碼實(shí)現(xiàn)：
def shellSort(nums):
lens = len(nums)
gap = 1
while gap < lens // 3:
gap = gap * 3 + 1 # 動(dòng)態(tài)定義間隔序列
while gap > 0:
for i in range(gap, lens):
curNum, preIndex = nums[i], i - gap # curNum 保存當(dāng)前待插入的數(shù)
while preIndex >= 0 and curNum < nums[preIndex]:
nums[preIndex + gap] = nums[preIndex] # 將比 curNum 大的元素向后移動(dòng)
preIndex -= gap
nums[preIndex + gap] = curNum # 待插入的數(shù)的正確位置
gap //= 3 # 下一個(gè)動(dòng)態(tài)間隔
return nums
歸并排序（Merge Sort）
歸并排序須知：
作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實(shí)現(xiàn)由兩種方法：
- 自上而下的遞歸（所有遞歸的方法都可以用迭代重寫，所以就有了第2種方法）
- 自下而上的迭代
和選擇排序一樣，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多，因?yàn)槭冀K都是O(n log n）的時(shí)間復(fù)雜度。代價(jià)是需要額外的內(nèi)存空間。
歸并排序動(dòng)圖演示：
歸并排序 Python 代碼實(shí)現(xiàn)：
def mergeSort(nums):
# 歸并過程
def merge(left, right):
result = [] # 保存歸并后的結(jié)果
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result = result + left[i:] + right[j:] # 剩余的元素直接添加到末尾
return result
# 遞歸過程
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = mergeSort(nums[:mid])
right = mergeSort(nums[mid:])
return merge(left, right)
快速排序（Quick Sort）
快速排序須知：
又是一種分而治之思想在排序算法上的典型應(yīng)用。本質(zhì)上來看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。它是處理大數(shù)據(jù)最快的排序算法之一，雖然 Worst Case 的時(shí)間復(fù)雜度達(dá)到了 O(n2)，但是在大多數(shù)情況下都比平均時(shí)間復(fù)雜度為 O(n log n) 的排序算法表現(xiàn)要更好，因?yàn)?O(n log n) 記號(hào)中隱含的常數(shù)因子很小，而且快速排序的內(nèi)循環(huán)比大多數(shù)排序算法都要短小，這意味著它無論是在理論上還是在實(shí)際中都要更快，比復(fù)雜度穩(wěn)定等于 O(n log n) 的歸并排序要小很多。所以，對(duì)絕大多數(shù)順序性較弱的隨機(jī)數(shù)列而言，快速排序總是優(yōu)于歸并排序。它的主要缺點(diǎn)是非常脆弱，在實(shí)現(xiàn)時(shí)要非常小心才能避免低劣的性能。
快速排序動(dòng)圖演示：
快速排序 Python 代碼實(shí)現(xiàn)：
def quickSort(nums): # 這種寫法的平均空間復(fù)雜度為 O(nlogn)
if len(nums) <= 1:
return nums
pivot = nums[0] # 基準(zhǔn)值
left = [nums[i] for i in range(1, len(nums)) if nums[i] < pivot]
right = [nums[i] for i in range(1, len(nums)) if nums[i] >= pivot]
return quickSort(left) + [pivot] + quickSort(right)
'''
@param nums: 待排序數(shù)組
@param left: 數(shù)組上界
@param right: 數(shù)組下界
'''
def quickSort2(nums, left, right): # 這種寫法的平均空間復(fù)雜度為 O(logn)
# 分區(qū)操作
def partition(nums, left, right):
pivot = nums[left] # 基準(zhǔn)值
while left < right:
while left < right and nums[right] >= pivot:
right -= 1
nums[left] = nums[right] # 比基準(zhǔn)小的交換到前面
while left < right and nums[left] <= pivot:
left += 1
nums[right] = nums[left] # 比基準(zhǔn)大交換到后面
nums[left] = pivot # 基準(zhǔn)值的正確位置，也可以為 nums[right] = pivot
return left # 返回基準(zhǔn)值的索引，也可以為 return right
# 遞歸操作
if left < right:
pivotIndex = partition(nums, left, right)
quickSort2(nums, left, pivotIndex - 1) # 左序列
quickSort2(nums, pivotIndex + 1, right) # 右序列
return nums
堆排序（Heap Sort）
堆排序須知：
堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：
- 大根堆：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值，用于升序排列；
- 小根堆：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值，用于降序排列。
如下圖所示，首先將一個(gè)無序的序列生成一個(gè)最大堆，如圖（a）所示。接下來我們不需要將堆頂元素輸出，只要將它與堆的最后一個(gè)元素對(duì)換位置即可，如圖（b）所示。這時(shí)我們確知最后一個(gè)元素 99 一定是遞增序列的最后一個(gè)元素，而且已經(jīng)在正確的位置上。 現(xiàn)在問題變成了如何將剩余的元素重新生成一個(gè)最大堆——也很簡單，只要依次自上而下進(jìn)行過濾，使其符合最大堆的性質(zhì)。圖（c）是調(diào)整后形成的新的最大堆。要注意的是，99 已經(jīng)被排除在最大堆之外，即在調(diào)整的時(shí)候，堆中元素的個(gè)數(shù)應(yīng)該減 1 。結(jié)束第 1 輪調(diào)整后，再次將當(dāng)前堆中的最后一個(gè)元素 22 與堆頂元素?fù)Q位，如圖（d）所示，再繼續(xù)調(diào)整成新的最大堆……如此循環(huán)，直到堆中只剩 1 個(gè)元素，即可停止，得到一個(gè)從小到大排列的有序序列。
堆排序動(dòng)圖演示：
堆排序 Python 代碼實(shí)現(xiàn)：
# 大根堆（從小打大排列）
def heapSort(nums):
# 調(diào)整堆
def adjustHeap(nums, i, size):
# 非葉子結(jié)點(diǎn)的左右兩個(gè)孩子
lchild = 2 * i + 1
rchild = 2 * i + 2
# 在當(dāng)前結(jié)點(diǎn)、左孩子、右孩子中找到最大元素的索引
largest = i
if lchild < size and nums[lchild] > nums[largest]:
largest = lchild
if rchild < size and nums[rchild] > nums[largest]:
largest = rchild
# 如果最大元素的索引不是當(dāng)前結(jié)點(diǎn)，把大的結(jié)點(diǎn)交換到上面，繼續(xù)調(diào)整堆
if largest != i:
nums[largest], nums[i] = nums[i], nums[largest]
# 第 2 個(gè)參數(shù)傳入 largest 的索引是交換前大數(shù)字對(duì)應(yīng)的索引
# 交換后該索引對(duì)應(yīng)的是小數(shù)字，應(yīng)該把該小數(shù)字向下調(diào)整
adjustHeap(nums, largest, size)
# 建立堆
def builtHeap(nums, size):
for i in range(len(nums)//2)[::-1]: # 從倒數(shù)第一個(gè)非葉子結(jié)點(diǎn)開始建立大根堆
adjustHeap(nums, i, size) # 對(duì)所有非葉子結(jié)點(diǎn)進(jìn)行堆的調(diào)整
# print(nums) # 第一次建立好的大根堆
# 堆排序
size = len(nums)
builtHeap(nums, size)
for i in range(len(nums))[::-1]:
# 每次根結(jié)點(diǎn)都是最大的數(shù)，最大數(shù)放到后面
nums[0], nums[i] = nums[i], nums[0]
# 交換完后還需要繼續(xù)調(diào)整堆，只需調(diào)整根節(jié)點(diǎn)，此時(shí)數(shù)組的 size 不包括已經(jīng)排序好的數(shù)
adjustHeap(nums, 0, i)
return nums # 由于每次大的都會(huì)放到后面，因此最后的 nums 是從小到大排列
計(jì)數(shù)排序（Counting Sort）
計(jì)數(shù)排序須知：
計(jì)數(shù)排序要求輸入數(shù)據(jù)的范圍在 [0,N-1] 之間，則可以開辟一個(gè)大小為 N 的數(shù)組空間，將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在該數(shù)組空間中，數(shù)組中的元素為該元素出現(xiàn)的個(gè)數(shù)。它是一種線性時(shí)間復(fù)雜度的排序。
計(jì)數(shù)排序動(dòng)圖演示：
計(jì)數(shù)排序 Python 代碼實(shí)現(xiàn)：
def countingSort(nums):
bucket = [0] * (max(nums) + 1) # 桶的個(gè)數(shù)
for num in nums: # 將元素值作為鍵值存儲(chǔ)在桶中，記錄其出現(xiàn)的次數(shù)
bucket[num] += 1
i = 0 # nums 的索引
for j in range(len(bucket)):
while bucket[j] > 0:
nums[i] = j
bucket[j] -= 1
i += 1
return nums
桶排序（Bucket Sort）
桶排序須知：
桶排序是計(jì)數(shù)排序的升級(jí)版。它利用了函數(shù)的映射關(guān)系，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定。
為了使桶排序更加高效，我們需要做到這兩點(diǎn)：
- 在額外空間充足的情況下，盡量增大桶的數(shù)量
- 使用的映射函數(shù)能夠?qū)⑤斎氲?N 個(gè)數(shù)據(jù)均勻的分配到 K 個(gè)桶中
同時(shí)，對(duì)于桶中元素的排序，選擇何種比較排序算法對(duì)于性能的影響至關(guān)重要。
什么時(shí)候最快（Best Cases）：
當(dāng)輸入的數(shù)據(jù)可以均勻的分配到每一個(gè)桶中
什么時(shí)候最慢（Worst Cases）：
當(dāng)輸入的數(shù)據(jù)被分配到了同一個(gè)桶中
桶排序 Python 代碼實(shí)現(xiàn)：
def bucketSort(nums, defaultBucketSize = 5):
maxVal, minVal = max(nums), min(nums)
bucketSize = defaultBucketSize # 如果沒有指定桶的大小，則默認(rèn)為5
bucketCount = (maxVal - minVal) // bucketSize + 1 # 數(shù)據(jù)分為 bucketCount 組
buckets = [] # 二維桶
for i in range(bucketCount):
buckets.append([])
# 利用函數(shù)映射將各個(gè)數(shù)據(jù)放入對(duì)應(yīng)的桶中
for num in nums:
buckets[(num - minVal) // bucketSize].append(num)
nums.clear() # 清空 nums
# 對(duì)每一個(gè)二維桶中的元素進(jìn)行排序
for bucket in buckets:
insertionSort(bucket) # 假設(shè)使用插入排序
nums.extend(bucket) # 將排序好的桶依次放入到 nums 中
return nums
基數(shù)排序（Radix Sort）
基數(shù)排序須知：
基數(shù)排序是桶排序的一種推廣，它所考慮的待排記錄包含不止一個(gè)關(guān)鍵字。例如對(duì)一副牌的整理，可將每張牌看作一個(gè)記錄，包含兩個(gè)關(guān)鍵字：花色、面值。一般我們可以將一個(gè)有序列是先按花色劃分為四大塊，每一塊中又再按面值大小排序。這時(shí)“花色”就是一張牌的“最主位關(guān)鍵字”，而“面值”是“最次位關(guān)鍵字”。
基數(shù)排序有兩種方法：
- MSD （主位優(yōu)先法）：從高位開始進(jìn)行排序
- LSD （次位優(yōu)先法）：從低位開始進(jìn)行排序
LSD基數(shù)排序動(dòng)圖演示：
基數(shù)排序 Python 代碼實(shí)現(xiàn)：
# LSD Radix Sort
def radixSort(nums):
mod = 10
div = 1
mostBit = len(str(max(nums))) # 最大數(shù)的位數(shù)決定了外循環(huán)多少次
buckets = [[] for row in range(mod)] # 構(gòu)造 mod 個(gè)空桶
while mostBit:
for num in nums: # 將數(shù)據(jù)放入對(duì)應(yīng)的桶中
buckets[num // div % mod].append(num)
i = 0 # nums 的索引
for bucket in buckets: # 將數(shù)據(jù)收集起來
while bucket:
nums[i] = bucket.pop(0) # 依次取出
i += 1
div *= 10
mostBit -= 1
return nums
補(bǔ)充：外部排序
外部排序是指大文件排序，即待排序的數(shù)據(jù)記錄以文件的形式存儲(chǔ)在外存儲(chǔ)器上。由于文件中的記錄很多、信息容量龐大，所以整個(gè)文件所占據(jù)的存儲(chǔ)單元往往會(huì)超過了計(jì)算機(jī)的內(nèi)存量，因此，無法將整個(gè)文件調(diào)入內(nèi)存中進(jìn)行排序。于是，在排序過程中需進(jìn)行多次的內(nèi)外存之間的交換。在實(shí)際應(yīng)用中，由于使用的外設(shè)不一致，通?？梢苑譃榇疟P文件排序和磁帶文件排序兩大類。
外部排序基本上由兩個(gè)相對(duì)獨(dú)立的階段組成。首先，按可用內(nèi)存大小，將外存上含 N 個(gè)記錄的文件分成若干長度為 L(<N) 的子文件，依次讀入內(nèi)存，利用內(nèi)部排序算法進(jìn)行排序。然后，將排序后的文件寫入外存，通常將這些文件稱為歸并段（Run）或“順串”；對(duì)這些歸并段進(jìn)行逐步歸并，最終得到整個(gè)有序文件?？梢娡獠颗判虻幕痉椒ㄊ菤w并排序法，下面的例子給出了一個(gè)簡單的外部排序解決過程。
【例子】給定磁盤上有6大塊記錄需要排序，而計(jì)算機(jī)內(nèi)存最多只能對(duì)3個(gè)記錄塊進(jìn)行內(nèi)排序，則外部排序的過程如下圖所示。
【解析】首先將連續(xù)的3大塊記錄讀入內(nèi)存，用任何一種內(nèi)部排序算法完成排序，再寫回磁盤。經(jīng)過2次3大塊記錄的內(nèi)部排序，得到上圖（a）的結(jié)果。然后另用一個(gè)可容納6大塊記錄的周轉(zhuǎn)盤，輔助最后的歸并。方法是將內(nèi)存分成3塊，其中2塊用于輸入，1塊用于輸出，指定一個(gè)輸入塊只負(fù)責(zé)讀取一個(gè)歸并段中的記錄，如上圖（b）所示。歸并步驟為：
當(dāng)任一輸入塊為空時(shí)，歸并暫停，將相應(yīng)歸并段中的一塊信息寫入內(nèi)存
將內(nèi)存中2個(gè)輸入塊中的記錄逐一歸并入輸出塊
當(dāng)輸出塊寫滿時(shí)，歸并暫停，將輸出塊中的記錄寫入周轉(zhuǎn)盤
如此可將2個(gè)歸并段在周轉(zhuǎn)盤上歸并成一個(gè)有序的歸并段。上例的解決方法是最簡單的歸并法，事實(shí)上外部排序的效率還可以進(jìn)一步提高。要提高外排的效率，關(guān)鍵要解決以下4個(gè)問題：
- 如何減少歸并輪數(shù)
- 如何有效安排內(nèi)存中的輸入、輸出塊，使得機(jī)器的并行處理能力被最大限度利用
- 如何有效生成歸并段
- 如何將歸并段進(jìn)行有效歸并
針對(duì)這四大問題，人們?cè)O(shè)計(jì)了多種解決方案，例如釆用多路歸并取代簡單的二路歸并，就可以減少歸并輪數(shù)；例如在內(nèi)存中劃分出2個(gè)輸出塊，而不是只用一個(gè)，就可以設(shè)計(jì)算法使得歸并排序不會(huì)因?yàn)榇疟P的寫操作而暫停，達(dá)到歸并和寫周轉(zhuǎn)盤同時(shí)并行的效果；例如通過一種“敗者樹”的數(shù)據(jù)結(jié)構(gòu)，可以一次生成2倍于內(nèi)存容量的歸并段；例如利用哈夫曼樹的貪心策略選擇歸并次序，可以耗費(fèi)最少的磁盤讀寫時(shí)間等。
其他一些比較：
基數(shù)排序 vs 計(jì)數(shù)排序 vs 桶排序
這三種排序算法都利用了桶的概念，但對(duì)桶的使用方法上有明顯差異：
基數(shù)排序：根據(jù)鍵值的每位數(shù)字來分配桶
計(jì)數(shù)排序：每個(gè)桶只存儲(chǔ)單一鍵值
桶排序：每個(gè)桶存儲(chǔ)一定范圍的數(shù)值
哪些排序算法可以在未結(jié)束排序時(shí)找出第 k 大元素？
冒泡、選擇、堆排序、快排（想想為什么？）
總結(jié)：
本章用 Python3 語言實(shí)現(xiàn)了經(jīng)典的十大排序算法，對(duì)它們的優(yōu)缺點(diǎn)、復(fù)雜度等方面進(jìn)行了詳細(xì)的比較。最后，還對(duì)外部排序進(jìn)行了簡單的介紹。
快排、歸并排序、堆排序、計(jì)數(shù)排序（桶排序）一般是面試中常問的題目，筆者覺得其中比較難的是堆排序，因?yàn)樯婕敖ǘ?、調(diào)整堆的過程，手寫該算法還是有一定難度的。
筆者在寫文章時(shí)，難免有些地方會(huì)出現(xiàn)一些表述不清的問題，歡迎指正！
