排序算法¶

排序是把一组元素按指定规则重新排列。它是学习复杂度、稳定性、分治、原地操作和工程优化的典型入口。

评价排序算法时常看：

算法	平均复杂度	稳定性	额外空间
插入排序	`O(n^2)`	稳定	`O(1)`
希尔排序	依增量序列而定	不稳定	`O(1)`
归并排序	`O(n log n)`	稳定	`O(n)`
快速排序	`O(n log n)`	不稳定	递归栈
堆排序	`O(n log n)`	不稳定	`O(1)`

插入排序¶

插入排序维护一个已排序区间，每次把新元素插入到正确位置。

for i in 1..n-1:
    x = a[i]
    j = i
    while j > 0 and a[j-1] > x:
        a[j] = a[j-1]
        j -= 1
    a[j] = x

它对近乎有序数组表现很好，也常用于小规模分段排序。

希尔排序是插入排序的改进。它先按较大间隔分组做插入排序，再逐步缩小间隔，最后以间隔 1 完成排序。

关键在增量序列。不同增量序列会影响复杂度和实际性能。希尔排序通常不稳定。

归并排序使用分治：先把数组拆成两半，分别排序，再合并两个有序数组。

merge_sort(l, r):
    if r - l <= 1: return
    mid = (l + r) / 2
    merge_sort(l, mid)
    merge_sort(mid, r)
    merge(l, mid, r)

归并排序复杂度稳定为 O(n log n)，且可以稳定排序，代价是需要额外空间。

快速排序选择一个基准值，把数组划分为小于基准和大于基准的两部分，再递归排序。

随机化基准可以降低遇到恶意或特殊输入退化到 O(n^2) 的概率。

randomly choose pivot
partition array by pivot
quick_sort(left)
quick_sort(right)

双路快速排序使用左右两个指针同时扫描，把小于基准的元素放左边，大于基准的元素放右边。

它比单路划分更适合存在较多重复元素的情况，但仍可能在大量相等元素时不够理想。

三路快速排序把数组分成三段：小于基准、等于基准、大于基准。

[l+1, lt] < pivot
[lt+1, i) == pivot
[gt, r] > pivot

当数组中重复元素很多时，三路快速排序能显著减少无意义递归。

排序常用于解决衍生问题：

做题时不要只套排序模板，应判断排序后是否能暴露单调性、相邻关系或分组结构。