知識星球開源最前線（ID：OpenSourceTop） 整編
綜合自：GitHub詳情頁
GitHub月度Trending榜單已經出爐，感興趣的夥伴可點選檢視上榜前十的開源專案：《9月份GitHub上最熱門的開源專案》
本月榜單有一個專案成功吸引了我的註意，該專案用Python實現了所有的排序演演算法，包括插入排序、氣泡排序、快速排序、選擇排序、歸併排序等。
截至今日，該專案已經獲得了 13200 個「star」以及 3758 個「fork」（GitHub專案地址：https://github.com/TheAlgorithms/Python）
該建立者表示這些僅用於演示學習。由於效能的原因，Python標準庫中有許多排序實現。
1、氣泡排序
氣泡排序，有時也稱為下沉排序，是一種簡單的排序演演算法，它反覆遍歷要排序的串列，一次比較兩個元素，如果它們的順序錯誤則交換它們。重覆遍歷串列，直到不再需要交換，說明該串列排序完成。
效能分析
● 氣泡排序在最壞的情況下的比較次數是O(N^2)
● 氣泡排序在最壞的情況下的比較次數是O(N)
程式碼實現
for i = 1:n,
swapped = false
for j = n:i+1,
if a[j] 1],
swap a[j,j-1]
swapped = true
→ invariant: a[1..i] in final position
break if not swapped
end
2、插入排序
插入排序是一種簡單的排序演演算法，可以一次構建一個專案的最終排序陣列（或串列）。它在大型串列上的效率遠低於更高階的演演算法，如快速排序，對堆排序或歸併排序。
程式碼實現
for i = 2:n,
for (k = i; k > 1 and a[k] 1]; k--)
swap a[k,k-1]
→ invariant: a[1..i] is sorted
end
3、歸併排序
歸併排序(MERGE-SORT)是一種有效的、通用的，基於比較的排序演演算法,該演演算法是採用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。由John von Neumann於1945年發明。
屬性
● 最好時間複雜度O(nlogn)
● 最壞時間複雜度O(nlogn)
● 平均時間複雜度O(nlogn)
程式碼實現
# split in half
m = n / 2
# recursive sorts
sort a[1..m]
sort a[m+1..n]
# merge sorted sub-arrays using temp array
b = copy of a[1..m]
i = 1, j = m+1, k = 1
while i <= m and j <= n,
a[k++] = (a[j] → invariant: a[1..k] in final position
while i <= m,
a[k++] = b[i++]
→ invariant: a[1..k] in final position
歸併排序在多種情況下都是首選的演演算法：當需要穩定性時，當排序連結串列時，當隨機訪問比順序訪問複雜得多時(例如，磁帶上的外部排序)。
4、快速排序
快速排序（也被稱為分割槽交換排序）是一種有效的排序演演算法，用作按順序放置陣列元素的系統方法。
程式碼實現
_# choose pivot_
swap a[1,rand(1,n)]
_# 2-way partition_
k = 1
for i = 2:n, if a[i] 1], swap a[++k,i]
swap a[1,k]
_→ invariant: a[1..k-1] 1..n]_
_# recursive sorts_
sort a[1..k-1]
sort a[k+1,n]
5、選擇排序
選擇排序(Selection sort)是一種簡單直觀的排序演演算法。它的工作原理是每一次從待排序的資料元素中選出最小(或最大)的一個元素，存放在序列的起始位置，直到全部待排序的資料元素排完。
程式碼實現
for i = 1:n,
k = i
for j = i+1:n, if a[j] → invariant: a[k] smallest of a[i..n]
swap a[i,k]
→ invariant: a[1..i] in final position
end
選擇排序的特性是最小化交換的數量。在交換項成本很高的應用程式中，選擇排序可能是一種很好的選擇演演算法。
6、希爾排序
希爾排序(Shell Sort)是插入排序的一種。是針對直接插入排序演演算法的改進。該方法又稱縮小增量排序，因D.L.Shell於1959年提出而得名。
屬性
● 最好時間複雜度O（nlog2 2n）
● 最壞時間複雜度O（n log n）
● 平均時間複雜度表現取決於差距序列
實現程式碼
h = 1
while h 3*h + 1
while h > 0,
h = h / 3
for k = 1:h, insertion sort a[k:h:n]
→ invariant: each h-sub-array is sorted
end
●編號529，輸入編號直達本文
●輸入m獲取文章目錄
