如果你已经很熟悉了，只是需要看下总结的图，那么这就是喽。
冒泡排序（Bubble Sort）
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为更大的元素会经由交换慢慢“浮”到数列的一端。通过一个优化策略————在发现某次循环没有交换时提前退出，
冒泡排序在输入的数据已经是正序时可达到最优时间复杂度 O(N)。
def bubble_sort(arr: List[int]):
for i in range(len(arr)):
order = True
for j in range(len(arr) - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
order = False
if order:
return
选择排序（Selection Sort）
选择排序是最易于理解的排序算法（个人意见）。 主要思想是不断地在未排序序列中找到最小元素， 交换到排序序列的最后即可。
def selection_sort(arr: List[int]):
for i in range(len(arr)):
min_idx = i
for j in range(i + 1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
插入排序（Insertion Sort）
它的工作原理是不断地将每一个未排序数据插入已排序序列中的正确位置。 如果你打过扑克牌，应该能够秒懂：人会在手中把牌按一定规律排好， 摸牌时再把新的牌插入适当位置。
def insertion_sort(arr: List[int]):
for i in range(len(arr)):
preIndex = i - 1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex + 1] = arr[preIndex]
preIndex -= 1
arr[preIndex + 1] = current
插入排序是三大经典 O(N^2) 排序算法中唯一一个在工程实际中还有应用的算法。在数据集较小或基本有序时它甚至比快速排序还要高效。
数据集较小时，快排的递归函数调用开销掩盖了算法效率的提升；
插入排序在数据集已经是正序时可达到最优时间复杂度 O(N)，
而且它不同于冒泡，它对于不同程度的有序性都能有对应程度的效率提升。
因而，对于一些分治排序算法（如归并、快排），在工程上
通常不选择只有一个元素的数据集为递归终点，而是在数据集大小小于特定值时
使用插入排序收尾。
希尔排序（Shell Sort）
它是第一个时间复杂度突破 O(N^2) 的排序算法，基于插入排序改进而来。
它的工作原理是对不相邻的记录进行比较和移动：
- 将待排序序列分为若干子序列（每个子序列的元素在原始数组中间距相同）；
- 对这些子序列进行插入排序；
- 减小每个子序列中元素之间的间距，重复上述过程直至间距减少为 1。
它的原理相对较复杂，而效率又不突出，故实际中基本不用。
归并排序（Merge Sort）
它是分治法（Divide and Conquer）的一个非常典型的应用。
它主要分为三个步骤：
- 将数组等分为左右两部分；
- 递归地分别对两个子数组进行归并排序；
- 合并两个有序的子数组为一个有序的数组。
def mergeSort(arr: List[int]) -> List[int]:
if len(arr) < 2:
return arr
middle = len(arr) // 2
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))
def merge(left: List[int], right: List[int]) -> List[int]:
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
result.extend(left)
result.extend(right)
return result
快速排序（Quicksort）
它同样是基于分而治之思想的排序算法，也是最常用的排序算法。
它是处理大数据最快的排序算法之一，
其时间复杂度的 O(NlogN) 记号中隐含的常数因子很小，
因而在大多数情况下都比复杂度为 O(NlogN) 的其他排序算法表现要更好。
它的主要步骤是：
- 从数列中挑出一个元素，称为 “基准”（
pivot）; - 重新排序数列，所有比基准值小的元素摆放在基准前面，比基准值大的摆在基准的后面（相同的数可以到任一边），这步称为分区（
partition）操作； - 递归地把小于基准值元素的子数列和大于它的子数列排序。
def quick_sort(arr: List[int], first: int, last: int):
if first >= last:
return
pivot = arr[first]
low, high = first, last
while low < high:
while low < high and arr[high] >= pivot:
high -= 1
arr[low] = arr[high]
while low < high and arr[low] < pivot:
low += 1
arr[high] = arr[low]
arr[low] = pivot
quick_sort(arr, first, low - 1)
quick_sort(arr, low + 1, last)
注意分区这里是怎么实现的。默认选择了第一个元素作为基准。
pivot 变量保存了 arr[low]，那么 arr[low] 就相当于一个空穴，
它的值可以被覆盖；从右向左找到第一个比 pivot 小的元素，
把它填进空穴，现在它原来的位置 arr[high] 又变成了新的空穴，
我们再从左向右找到第一个比 pivot 大的元素填过去……最终，
大循环退出时，low == high，留下的空穴刚好填入变量 pivot。
快排的另一种写法如下，它主要是 partition 的写法不同。
def quick_sort(array, left, right):
if left >= right:
return
def partition(nums: List[int], left: int, right: int, pred: Callable[[int], bool])-> int:
i = left
for j in range(left, right + 1):
if pred(j):
nums[i], nums[j] = nums[j], nums[i]
i += 1
return i
pivot = array[right]
mid = partition(array, left, right - 1, lambda j: array[j] <= pivot)
array[right], array[mid] = array[mid], array[right]
quick_sort(array, left, mid - 1)
quick_sort(array, mid + 1, right)
对于 partition 函数，nums[left:right+1] 是要 partition 的区间，pred 是一个接收索引返回布尔值的函数，
令 pred 返回 True 的索引处的元素最终会聚集在区间的左侧，反之在右侧。
partition 函数最终返回分界面右端索引，即右侧区域起始索引。
因而 pivot 选择区间右端点，这样才能保证 pivot 与分界点交换后，
分界点依然在右侧。同时注意 partition 函数划分的区间不包括末尾的 pivot。
快排一般都用递归法实现，需要 O(logN) 的栈空间；
当然也可借助辅助栈来用迭代法实现。
快排的效率与 pivot 的选取直接相关，
每次按 pivot 分区恰好能均分序列时效率最佳，
而每次划分只能将序列分为一个元素与其他元素两部分时效率最差（退化为 O(N^2)）。若像示例实现中那样始终选择第一个元素为 pivot，
那么在数列完全有序时快排效率最差。为了保证快排效率的稳定，
我们可以采用其他的 pivot 选取策略。
不难想到，pivot 最好能取数列的中位数，但是寻找中位数本身开销就较大。
我们可以转而采用近似策略，即三数取中法：
选取数列第一个、最后一个以及中间位置的元素————这三个数中的中位数为 pivot。
堆排序（Heapsort）
它是指利用堆这种数据结构所设计的一种排序算法。 堆的详细介绍参考往期文章。我们可以开辟一个额外数组来单独建立堆， 再遍历原数组，将元素依次送进堆中，最后不断弹出堆顶元素即可获得有序数组。 更优的方法是原地进行堆排序。
- 首先，我们对原始数组进行堆化，即从第一个非叶子结点开始（因为叶子结点无可下沉），
从后向前依次将各个结点下沉（
sift down）至正确位置； - 然后，将堆顶元素交换到末尾（索引
n）， 此时末尾存放着最值而前面的堆结构（[0, n-1]）遭到破坏； - 我们接着将堆顶下沉以完成修复，
[0, n-1]的元素形成了新堆； - 继续将堆顶元素交换到索引
n-1位置，继续修复堆……整个过程中， 数组的后半部分是排好序的，前半部分维持着规模逐渐减小的堆， 直至最终排序完成。
# 数组要求升序排列，则前半部分维护的堆应为最大堆
# sift_down 处理 arr[left:right+1] 的子堆，将堆顶下沉至合适位置
def sift_down(arr: List[int], left: int, right: int):
# 计算父结点和子结点的下标
parent = left
child = parent * 2 + 1
# 子结点下标在范围内才做比较
while child <= right:
# 先比较两个子结点大小，选择最大的
if child + 1 <= right and arr[child] < arr[child + 1]:
child += 1
# 如果父结点比子结点大，代表调整完毕，直接跳出函数
if arr[parent] >= arr[child]:
return
else:
# 否则交换父子内容，子结点再和孙结点比较
arr[parent], arr[child] = arr[child], arr[parent]
parent = child
child = parent * 2 + 1
def heap_sort(arr: List[int]):
# 从最后一个节点的父节点开始 sift down 以完成堆化 (heapify)
for i in range((len(arr) - 1 - 1) // 2, -1, -1):
sift_down(arr, i, len(arr) - 1)
# 先将第一个元素和已经排好的元素前一位做交换，再重新调整（刚调整的元素之前的元素），直到排序完毕
for i in range(len(arr) - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
sift_down(arr, 0, i - 1)
计数排序（Counting Sort）
它是一种线性时间的排序算法。它的高效背后有着额外空间的开销， 与对待排序数据集的苛刻要求————它们必须都是在一定范围（范围不能太大）内的整数。
计数排序的原理核心就是计数：使用一个额外的数组 bucket，
其中第 i 个元素是待排序数组中值等于 i 的元素的个数，
然后顺序遍历数组 bucket 即可正确填充排序数组。
# 假设数据范围为 [0, maxValue]
def counting_sort(arr: List[int], maxValue: int):
bucket = [0] * (maxValue + 1)
sortedIndex = 0
for i in range(len(arr)):
bucket[arr[i]] += 1
for i in range(len(bucket)):
while bucket[i] > 0:
arr[sortedIndex] = i
sortedIndex += 1
bucket[i] -= 1
桶排序（Bucket Sort）
桶排序是计数排序的升级版。它的工作原理是将所有元素分到有限数量的桶子里，然后对每个桶子再分别用上面提到的任一算法排序，最后将各个桶中的数据有序地合并起来。或者，计数排序也可当成每个桶里只有一个元素的情况。
基数排序（英语：Radix Sort）
它与前两种算法一样，都是非比较型的排序算法。
基数排序的中文名字很容易与计数排序相混淆，实际上两者截然不同。
基数（Radix）是指进位记数法中某一位可以有的不同数字（或符号）的数量，
比如 10 进制的基数为 10。
基数排序的本质是按各个数位排序。
通常而言，它比基于比较的排序算法（比如快速排序）要快，
但需要额外的内存空间。
参考资料：
如果你喜欢我的文章，请我吃根冰棒吧 (o゜▽゜)o ☆
最后附上 GitHub：https://github.com/gonearewe
