技術部落格： https://github.com/yongxinz/tech-blog
同時，也歡迎關注我的微信公衆号 AlwaysBeta，更多精彩内容等你來。
本文用 Python 實作了插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序。
先整體看一下各個算法之間的對比，然後再進行詳細介紹：
排序算法 平均時間複雜度 最好情況 最壞情況 空間複雜度 排序方式 穩定性
插入排序 O(n²) O(n) O(n²) O(1) In-place 穩定
冒泡排序 O(n²) O(n) O(n²) O(1) In-place 穩定
選擇排序 O(n²) O(n²) O(n²) O(1) In-place 不穩定
快速排序 O(n log n) O(n log n) O(n²) O(log n) In-place 不穩定
希爾排序 O(n log n) O(n log n) O(n log n) O(1) In-place 不穩定
堆排序 O(n log n) O(n log n) O(n log n) O(1) In-place 不穩定
歸并排序 O(n log n) O(n log n) O(n log n) O(n) Out-place 穩定
n：資料規模
In-place：占用常數記憶體，不占用額外記憶體
Out-place：占用額外記憶體
穩定性：排序後 2 個相等鍵值的順序和排序之前它們的順序相同
插入排序
描述
時間複雜度為 O(n^2)，是穩定的排序方法。
插入排序的基本操作就是将一個資料插入到已經排好序的有序資料中，進而得到一個新的、個數加一的有序資料，算法适用于少量資料的排序。
插入算法把要排序的數組分成兩部分：第一部分包含了這個數組的所有元素，但将最後一個元素除外(讓數組多一個空間才有插入的位置)，而第二部分就隻包含這一個元素(即待插入元素)。在第一部分排序完成後，再将這個最後元素插入到已排好序的第一部分中。
代碼實作
# -*- coding: UTF-8 -*-def insert_sort(lists): # 插入排序 時間複雜度為 O(n^2) count = len(lists) for i in range(1, count): key = lists[i] j = i - 1 while j >= 0: if lists[j] > key: lists[j + 1] = lists[j] lists[j] = key j -= 1 return listsif __name__ == "__main__": test = [2, 5, 4, 6, 7, 3, 2] print(insert_sort(test))
希爾排序
描述
時間複雜度為 O(n log n)，是不穩定的排序方法。
希爾排序(Shell Sort)是插入排序的一種，也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。
該方法因 DL．Shell 于 1959 年提出而得名。 希爾排序是把記錄按下标的一定增量分組，對每組使用直接插入排序算法排序；随着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，整個檔案恰被分成一組，算法便終止。
代碼實作
# -*- coding: UTF-8 -*-def shell_sort(lists): # 希爾排序 時間複雜度是 O(n log n) count = len(lists) step = 2 group = int(count / step) while group > 0: for i in range(0, group): j = i + group while j < count: k = j - group key = lists[j] while k >= 0: if lists[k] > key: lists[k + group] = lists[k] lists[k] = key k -= group j += group group = int(group / step) return listsif __name__ == "__main__": test = [2, 5, 4, 6, 7, 3, 2] print(shell_sort(test))
冒泡排序
描述
時間複雜度是 O(n²)， 是穩定排序算法。
它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。
代碼實作
# -*- coding: UTF-8 -*-def bubble_sort(lists): # 冒泡排序 時間複雜度是 O(n²) count = len(lists) for i in range(0, count - 1): for j in range(0, count - i - 1): if lists[j] > lists[j + 1]: lists[j], lists[j + 1] = lists[j + 1], lists[j] return listsif __name__ == "__main__": test = [2, 5, 4, 6, 7, 3, 2] print(bubble_sort(test))
快速排序
描述
快速排序的時間複雜度是 O(n log n)， 是不穩定排序算法。
通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。
代碼實作
# -*- coding: UTF-8 -*-def quick_sort(lists, left, right): # 快速排序 時間複雜度是 O(n log n) if left >= right: return lists key = lists[left] low = left high = right while left < right: while left < right and lists[right] >= key: right -= 1 lists[left] = lists[right] while left < right and lists[left] <= key: left += 1 lists[right] = lists[left] lists[right] = key quick_sort(lists, low, left - 1) quick_sort(lists, left + 1, high) return listsif __name__ == "__main__": test = [2, 5, 4, 6, 7, 3, 2] print(quick_sort(test, 0, len(test) - 1))
直接選擇排序
描述
選擇排序的時間複雜度是 O(n²)， 是不穩定排序算法。
基本思想：第 1 趟，在待排序記錄 r1 ~ r[n] 中選出最小的記錄，将它與 r1 交換；第 2 趟，在待排序記錄 r2 ~ r[n] 中選出最小的記錄，将它與 r2 交換；以此類推，第 i 趟在待排序記錄 r[i] ~ r[n] 中選出最小的記錄，将它與 r[i] 交換，使有序序列不斷增長直到全部排序完畢。
代碼實作
# -*- coding: UTF-8 -*-def select_sort(lists): # 選擇排序 時間複雜度是 O(n²) count = len(lists) for i in range(0, count): min = i for j in range(i + 1, count): if lists[min] > lists[j]: min = j lists[min], lists[i] = lists[i], lists[min] return listsif __name__ == "__main__": test = [2, 5, 4, 6, 7, 3, 2] print(select_sort(test))
堆排序
描述
堆排序的時間複雜度是 O(n log n)， 是不穩定排序算法。
堆排序(Heapsort)是指利用堆積樹(堆)這種資料結構所設計的一種排序算法，它是選擇排序的一種。可以利用數組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個節點的值都不大于其父節點的值，即 A[PARENT[i]] >= A[i]。在數組的非降序排序中，需要使用的就是大根堆，因為根據大根堆的要求可知，最大的值一定在堆頂。
代碼實作
# -*- coding: UTF-8 -*-from collections import dequedef swap_param(lists, i, j): lists[i], lists[j] = lists[j], lists[i] return listsdef heap_adjust(lists, start, end): temp = lists[start] i = start j = 2 * i while j <= end: if (j < end) and (lists[j] < lists[j + 1]): j += 1 if temp < lists[j]: lists[i] = lists[j] i = j j = 2 * i else: break lists[i] = tempdef heap_sort(lists): length = len(lists) - 1 first_sort_count = length / 2 for i in range(first_sort_count): heap_adjust(lists, first_sort_count - i, length) for i in range(length - 1): lists = swap_param(lists, 1, length - i) heap_adjust(lists, 1, length - i - 1) return [lists[i] for i in range(1, len(lists))]def main(): lists = deque([50, 16, 30, 10, 60, 90, 2, 80, 70]) lists.appendleft(0) print heap_sort(lists)if __name__ == '__main__': main()
歸并排序
描述
時間複雜度是 O(n log n)， 是穩定排序算法。
歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。将已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若将兩個有序表合并成一個有序表，稱為二路歸并。
歸并過程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則将第一個有序表中的元素a[i]複制到r[k]中，并令i和k分别加上1；否則将第二個有序表中的元素a[j]複制到r[k]中，并令j和k分别加上1，如此循環下去，直到其中一個有序表取完，然後再将另一個有序表中剩餘的元素複制到r中從下标k到下标t的單元。歸并排序的算法我們通常用遞歸實作，先把待排序區間[s,t]以中點二分，接着把左邊子區間排序，再把右邊子區間排序，最後把左區間和右區間用一次歸并操作合并成有序的區間[s,t]。
代碼實作
# -*- coding: UTF-8 -*-def merge_sort(lists): # 歸并排序 時間複雜度是 O(n log n) if len(lists) <= 1: return lists num = int(len(lists) / 2) left_lists = merge_sort(lists[:num]) right_lists = merge_sort(lists[num:]) return merge(left_lists, right_lists)def merge(left_lists, right_lists): left, right = 0, 0 result = [] while left < len(left_lists) and right < len(right_lists): if left_lists[left] < right_lists[right]: result.append(left_lists[left]) left += 1 else: result.append(right_lists[right]) right += 1 result += left_lists[left:] result += right_lists[right:] return resultif __name__ == "__main__": test = [2, 5, 4, 6, 7, 3, 2] print(merge_sort(test))
參考文檔：
https://baagee.vip/index/article/id/101.html
https://www.jianshu.com/p/d174f1862601