排序算法是最基础、应用最广泛、也是面试最常考的算法。

一个排序算法（Sorting algorithm）是一种能将一串数据依照特定排序方式进行排列的一种算法。其中：

  • 输出结果为递增序列
  • 输出结果是原输入的一种排列或重组

可排序对象所需的两个基本操作为：比较（Compare）与交换（Swap）

排序算法分类

大类 细分
交换排序 冒泡排序 鸡尾酒排序 奇偶排序 梳排序 侏儒排序 快速排序 臭皮匠排序 Bogo排序
选择排序 选择排序 堆排序 平滑排序 笛卡尔树排序 锦标赛排序 圈排序
插入排序 插入排序 希尔排序 伸展排序 二叉查找树排序 图书馆排序 耐心排序
归并排序 归并排序 梯级归并排序 振荡归并排序 多相归并排序 列表排序
并发排序 双调排序器 Batcher归并网络 两两排序网络
混合排序 块排序 Tim排序 内省排序 Spread排序 J排序
其他 拓扑排序 煎饼排序 意粉排序
  • 稳定/不稳定：稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。
  • 适应性/非适应性：非适应性的算法执行的操作序列独立于数据的顺序。自适应的排序执行不同的操作序列。
  • 内部排序/外部排序：内部排序允许随机访问，而外部排序算法必须顺序访问元素（至少在大数据块内）
  • 可否应用于链表。
  • 是否为原地排序（in-place），原地排序的算法除了少量变量不需要使用额外的空间保存副本。

排序算法性能速查

类别 排序方法 平均时间复杂度 最好时间复杂度 最坏时间复杂度 空间复杂度 稳定性
插入排序 直接插入 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定
希尔排序 $O(n^{1.3})$ $O(n)$ $O(n^2)$ $O(1)$ 不稳定
选择排序 直接选择 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
堆排序 $O(n\log_{2}{n})$ $O(n\log_{2}{n})$ $O(n\log_{2}{n})$ $O(1)$ 不稳定
交换排序 冒泡排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
快速排序 $O(n\log_{2}{n})$ $O(n\log_{2}{n})$ $O(n^2)$ $O(n\log_{2}{n})$ 不稳定
归并排序 归并排序 $O(n\log_{2}{n})$ $O(n\log_{2}{n})$ $O(n\log_{2}{n})$ $O(1)$ 稳定

速记方法

  • 四大类基本排序：插入，选择，交换，归并。
  • 插入进阶版本为希尔，选择进阶版本为堆排，冒泡进阶版本为快排。
  • 只有简单的排序方法才是稳定的，但选择排序是不稳定的。直接插入，冒泡和归并是稳定的。
  • 只有堆排序和归并排序能保证最坏情况下的时间复杂度
  • 对于小规模的数据，基本排序算法反而具有一定优势。

分析框架

任何待排序的元素，都需要实现两种操作，比较与交换。

这里给出了Python的例子，包括生成随机数组，检验数组是否有序，检验排序函数是否正确的函数。

# Auxiliary Functions
def swap(A,i,j):
     A[i],A[j] = A[j],A[i]
    
def less(i,j):
  	 return i < j

# generate random data
import random
def random_data(size=1000):
    data = range(size)
    random.shuffle(data)
    return data

# test array is sorted
def is_sorted(data, cmp=None):
    if not cmp: cmp = less
    for i in range(1, len(data)):
        if cmp(data[i], data[i - 1]) < 0: return False
    return True
  
def test_sort(func=sorted):print(is_sorted(func(random_data())))

选择排序 Selection Sort

选择排序是一种最简单的基本排序算法，它通过不断选择出剩余元素中的最小元素实现。

插入排序的核心思路是：将数据分为（有序区，无序区），每次选择无序区的最小元素，放入有序区的末尾。对于有n个元素的数组，它会执行n-1次选择，因为最后一次剩下的肯定是最大的元素。

选择排序的缺点是，它的运行时间对文件中已有序的部分依赖较少，每一次都会找最小元素，没有充分利用原有序列中的有序部分。反过来讲，选择排序对输入的初始次序不敏感，最坏情况和最好情况区别不大。

其优点在于，选择排序比较次数较多，但交换次数是所有排序算法中最少的。对于交换的开销远大于比较的元素类型（大元素小关键字），可以使用选择排序。但对于比较的开销较大（例如字符串类型比较）的元素，插入排序是更好的选择。

其进阶版本是堆排序(Heap Sort)

分析

i ∈ [0, N)
    swap(A[i], A[min_index(A[i:N])] )
  • 循环不变量：每次循环开始时，前段A[0:i]有序，后段A[i:N]无序。
  • 初始条件：排序开始前i=0，前段空数组A[0:0]有序，后段全数组A[0:N]无序。
  • 结束条件：迭代结束时i=N，此时前段全数组A[0:N]有序，后段空数组A[N:N]无序，整个数组有序。
  • 保持性质：
    • 每轮迭代结束，会使无序区A[i:N]内最小元素与A[i]互换位置。该元素为有序区内最大元素。
    • 每轮迭代使得A[i]加入有序区，前段有序区增长为A[0:i+1]，后段无序区收缩为A[i+1:N]。
    • 下一轮迭代开始时i=i+1，循环不变量得到保持。

实现

def selection_sort(A):
    n = len(A)
    for i in range(0,n):
        min_index = i
        for j in range(i,n):
            if less(A[j], A[min_index]): min_index = j
        swap(A,i , min_index)
    return A

特性

  • 不稳定的排序
  • 原地操作
  • 非适应性排序：对输入的初始次序不敏感，最坏情况和最好情况区别不大。
  • 交换次数在所有基本排序算法中最少，但比较次数较多
  • 选择排序在执行中，有序区域前段保持不变。
  • 适合对链表排序。
项目\情况 平均情况 最差情况 最好情况
时间复杂度 $O(n^2)$ $O(n^2)$ $O(n^2)$
比较次数 $\frac{n(n-1)}{2}$ $\frac{n(n-1)}{2}$ $\frac{n(n-1)}{2}$
交换次数 $n-1$ $n-1$ $n-1$

插入排序 Insertion Sort

插入排序是一种简单直观的基本排序算法，它从无序区首部拉取一个元素，放入有序区的恰当位置。类似扑克牌理牌的操作。它是稳定的原地排序算法，而且具有较强的局部性。

插入排序的核心思路是：将数据分为（有序区，无序区），把无序区的第一个元素插入到有序区中的正确位置中。通常是通过不断前移至合适的位置实现的。

与选择排序不同，插入排序是适应性算法，其运行时间与原始序列的有序程度密切相关。同时它还是稳定的排序算法，也是原地排序。

分析

i ∈ [1, N)
    A[0:i+1] = put_properly( A[0,i) , A[i] )
  • 循环不变量：每次循环开始时，前段A[0:i]有序，后段A[i:N]无序。
  • 初始条件：排序开始前i=1，前段单元素数组A[0:1]有序，后段数组A[1:N]无序。
  • 结束条件：迭代结束时i=N，此时前段全数组A[0:N]有序，后段空数组A[N:N]无序，整个数组有序。
  • 保持性质：
    • 每轮迭代结束，会使元素A[i]位于前段有序数组中的合适位置，
    • 每轮迭代使得A[i]加入有序区，前段有序区增长为A[0:i+1]，后段无序区收缩为A[i+1:N]。
    • 下一轮迭代开始时i=i+1，循环不变量得到保持。

实现

def insertion_sort(A):
    n = len(A)
    for i in range(1,n):
        j = i
        while less(A[j-1], A[j]) and j > 0:
            swap(A, j-1, j)
            j -= 1
    return A

如果当前元素的前一个元素比当前元素还要小，那么就交换两个元素。

如果选择的A[i]比有序区的所有元素都要小，它就应当放到A[0]的位置，这时候在循环条件中还需要额外检查索引是否到头j>0，如果已经到头，则上一次循环已经执行了swap(A,0,1)，将元素放在了合适的位置，就应当跳出循环避免索引越界。

可以通过观察哨关键字来简化插入排序，但并不是所有的时候都好用，例如最小值难以定义，没有额外的空间。一种取巧的办法是在第一次迭代中执行一次冒泡或选择排序，将最小的元素放在数组首部，当做观察哨。改进实现：

def insertion_sort2(A):
    n = len(A)
    for i in range(n-1, 0, -1):
        if less(A[i], A[i-1]):
            swap(A, i , i-1)
            
    for i in range(1, n):
        j = i
        v = A[j]
        while less( v , A[j-1]):
            A[j] = A[j-1]
            j -= 1
        A[j] = v
    return A

改进实现主要包括，第一次使用逆向冒泡，在A[0]处生成最小元素观察哨，顺便消除一些逆序对。在后续的循环中，迭代条件就不需要判断索引是否越界了。同时将迭代中的交换改为赋值，可以减少一倍的赋值操作。

特性

  • 稳定的排序
  • 原地排序
  • 适应性排序算法，初始序列大量有序的情况下执行很快。
  • 比较次数少，但交换次数多。
  • 只访问有序部分的元素，而且是顺序访问，局部性较强。但有序区域在排序过程中会发生变化。
项目\情况 平均情况 最差情况 最好情况
时间复杂度 $O(n^2)$ $O(n^2)$ $O(n)$
空间复杂度 $O(n^2)$ $O(n^2)$ $O(1)$
比较次数 $\frac{n^2} 4$ $\frac{n(n-1)}{2}$ $n-1$
交换次数 $\frac{n^2} 4$ $\frac{n(n-1)}{2}$ 0

冒泡排序 Bubble Sort

冒泡排序是一种交换排序，它通过不断修正序列中的逆序对实现，每一轮冒泡都会使前面无序区的最大元素上浮至后段有序区。它的实现是最简单的。

冒泡排序的核心思路是：将数据分为（无序区，有序区），从无序区通过交换找出最大元素放到有序区前端。重复n-1次后即可保证数组有序。

分析

i ∈ [0, N-1)
    j ∈ [0, N-i-1）
        if less( A[j+1], A[j] ):
            swap(A, j+1, j)
  • 循环不变量：每次循环开始时，前段A[0:N-i]无序，后段A[N-i:N]有序。
  • 初始条件：排序开始前i=0，前段全数组A[0:N]无序，后段空数组A[N:N]有序，整个数组无序。
  • 结束条件：迭代结束时i=N，此时前段空数组A[0:0]无序，后段全数组A[0:N]有序，整个数组有序。
  • 保持性质：
    • 每轮迭代结束，会使A[0:N-i]中最大元素上浮至A[N-i]，且该元素小于后段有序区中所有元素。
    • 每轮迭代使得无序区收缩为A[0:N-i-1]，有序区增长为A[N-i-1:N]。
    • 下一轮迭代开始时i=i+1，前段A[0:N-(i+1)]无序，后段A[N-(i+1):N]有序，循环不变量得到保持。

实现

def bubble_sort(A):
    n = len(A)
    for i in range(n-1):
        for j in range(0, n-1-i):
            if less(A[j+1], A[j]):
                swap(A, j, j+1)
    return A

特性

  • 属于交换排序
  • 稳定排序
  • 原地排序，空间复杂度 $O(1)$
  • 实现极其简单。两层迭代，外侧 range(n-1)，内侧range(n-1-i)。
项目\情况 平均情况 最差情况 最好情况
时间复杂度 $O(n^2)$ $O(n^2)$ $O(n^2)$
比较次数 $\frac{n(n-1)}{2}$ $\frac{n(n-1)}{2}$ $\frac{n(n-1)}{2}$
交换次数 逆序数 $\frac{n(n-1)}{2}$ 0

希尔排序 Shell Sort

希尔排序是一种指定步长的插入排序。也称为递减增量排序算法，是插入排序的改良版本。

插入排序运行效率低的原因在于，它所执行的交换操作都是近邻元素，所以每次元素至多移动一位。所以例如最小的元素在数组尾端的极端情况，插入排序就需要N次交换才能把它放回到数组的最前端。希尔排序通过允许非相邻元素之间的交换，能够显著提高执行效率。

希尔排序的本质是将文件重排列，使得文件具有如下性质：每第h元素产生一个排好序的序列。例如h=3

则要求数组中序列`[0,3,6,…,3n,…]是有序的。这样的文件称为h-排序的。通过较大的h排序文件会使小h排序更加容易。当h=1时，就是普通的插入排序。因此通过一个最后为1的步长序列，不断进行h-排序，就可以得到一个排好序的文件。

分析

希尔排序的的关键是使用合适的步长。当步长为1时，就是插入排序。所以任何步长序列都应当以1结束。通常可以使用knuth的步长序列。$h_{i+1} = 3h_i +1 $，即1,4, 13,40,121,364,...。

实现

def shell_sort(A):
    n = len(A)
    steps = []
    h = 1
    while h <= n / 9:
        steps.insert(0,h)
        h = h * 3 + 1
        
    for h in steps:
        for i in range(h, n, h):
            j = i
            while less( A[j-h], A[j] ) and j - h >= 0:
                swap(A, j - h, j)
                j -= h
    return A

首先生成步长序列，最大的步长取数组长度的十分之一左右为宜。然后按照...,40,13,4,1的步长序列，依次执行h-插入排序，区别就在于原来插入排序中的1都用h替代即可。

特性

  • 已知的最好希尔步长序列为：1, 5, 19, 41, 109

  • 属于高级插入排序

  • 不稳定排序

  • 适应性排序。

  • 原地排序，空间复杂度 $O(1)$

计数排序

计数排序又称为关键词索引统计排序，它不属于比较排序。当关键字的范围是确定而且比较小时，可以通过计数排序高效的进行排序。

计数排序用到的思想与计算百分位点类似。首先求得数据的分布CDF。然后依次查询原数组每个元素的rank()，并将该元素放入rank()指定的位置上。

实现

def count_sort(A):
    M, N = max(A) + 2, len(A)  # 若A中最大元素为M，则还需要0和M两个额外空间。
    buf = [0 for i in range(N)]  # A的重排列副本

    # 构造CDF, cnt[i]返回小于i的元素个数
    cnt = [0 for i in range(M)]
    for i in range(N): cnt[A[i] + 1] += 1  # 统计当前i出现次数,加到后面去。
    for j in range(1, M): cnt[j] += cnt[j - 1]  # 变PDF为CDF

    for i in range(0, N):  # 对A中所有元素执行遍历，准备分配新位置。
        # shortcut: res[ cnt[A[i]]++ ] = A[i]
        index = cnt[A[i]]  # 查阅CDF，找到该元素的排序分位点。
        cnt[A[i]] += 1  # 如果A[i]是重复的元素，下次查询分位数应当+1
        buf[index] = A[i]

    for i in range(N): A[i] = buf[i]
    return A

快速排序 Quick Sort

快速排序是一种高级的交换排序，又称为 划分-交换排序(partition-exchange sort)。快排是应用最广泛的排序算法。属于广义的选择排序，运用了分治法。

快排的核心思想是：将数组划分为两个部分，然后分别对两个部分进行排序。划分的过程是关键，它需要保证：

  • 对于某个i, a[i]在数组的最终位置上。
  • a[0],...,a[i-1]中的元素都比A[i]小。
  • a[i+1],...a[N-1]中的元素逗比A[i]大。

分析

递归版本的qsort可以简要表示如下(Fired version)

def qsort(A):
    if len(A) <= 1: return A
    return qsort([i for i in A[1:] if i<A[0]]) + [A[0]] + qsort([i for i in A[1:] if i>=A[0]])

如何选取pivot是一个大问题。通常来说可以选取最后一个元素作为pivot，但更好的方式是随机选择一个元素

实现

一个更为合理且简洁的实现如下：

def qsort(A, lo, hi):
    # hi is the last index of A. so it's n-1 not n
    if lo >= hi:  # 0 or 1 element: do nothing
        return

    pivot = A[random.randint(lo, hi)] 
    i, j = lo, hi
    while i <= j:
        while less(A[i], pivot): i += 1
        while less(pivot, A[j]): j -= 1
        if i <= j:
            swap(A, i, j)
            i, j = i + 1, j - 1
    qsort(A, lo, j)
    qsort(A, i, hi)

边界条件分析，当退出while循环时有i>j，这时候需要证明数组满足以下条件：

  • $k∈ [lo,j) , A_k < pivot$
  • $k∈ (j,i) , A_k = pivot$
  • $k∈ [i,hi) , A_k > pivot$

实在不想证明了。

特性

  • 不稳定的排序算法
  • 原位排序，递归版本需要空间复杂度$O(\log n)$保存调用信息，相比很小。
  • 平均排序复杂度为$O(n\log n)$，内部循环很小，可以高效地在大多数架构上实现。通常比其他的$O(n \log n)$排序算法要快。
  • 最坏情况下复杂度为$O(n^2)$
  • 对大型文件，快排的性能是希尔排序的5~10倍。但对于小文件，希尔反而可能更胜一筹。一种常见的优化方式是，当hi-lo小于某个特定值，例如12时，使用其他排序方法，例如希尔排序。这也是GO标准库sort中使用的方式。Sedgewick给出的一个小文件阈值是9。
项目\情况 平均情况 最差情况 最好情况ß
时间复杂度 $O(1.39 n\log_{2}{n})$ $O(n\log_{2}{n})$ $O(n\log_{2}{n})$
空间复杂度 $O(\log n)$ $O(n)$ $O(\log n)$
比较次数 $O(n\log n)$ $\frac{n(n-1)}{2}$ $O(n\log n)$

归并排序 Merge Sort

归并（merging）是将两个排好序的文件组合成一个较大的有序文件

  • 归并的实现

归并是归并排序的核心，核心思想是，如果某子数组已经到头，则续以另一个子数组的元素，如果都没有到头，再比较两个子数组当前元素的大小。

def merge_ab(a, b):
    na, nb, nc = len(a), len(b), len(a) + len(b)
    c = [0] * nc
    i, j = 0, 0
    for k in range(nc):
        if i == na:
            c[k] = b[j]
            j += 1
            continue
        if j == nb:
            c[k] = a[i]
            i += 1
            continue
        if a[i] < b[j]:
            c[k] = a[i]
            i += 1
        else:
            c[k] = b[j]
            j += 1
    return c

对于链表的归并，稍微复杂一点，这里考虑没有链表头节点，以nil结尾的链表，则合并链表的逻辑如下：

type Node struct {
	Val  int
	Next *Node
}

func MergeLinkList(a *Node, b *Node) *Node {
	var head Node
	cursor := &head

	for a != nil && b != nil {
		if a.Val < b.Val {
			cursor.Next = a
			cursor = cursor.Next
			a = a.Next
		} else {
			cursor.Next = b
			cursor = cursor.Next
			b = b.Next
		}
	}

	if a == nil {
		cursor.Next = b
	} else {
		cursor.Next = a
	}
	return head.Next
}

在有归并方法的基础上，归并排序实现相当简单：

def msort(A, lo, hi):
    if lo >= hi: return
    mid = lo + ((hi - lo) >> 1)
    msort(A, lo, mid)
    msort(A, mid + 1, hi)
    merge(A, lo, mid, hi)
    return

  • 稳定排序

  • 空间复杂度$O(n)$，需要基本等量的额外存储空间。

  • 如果使用的归并方法是稳定的，则归并排序是稳定的。

  • 采用分治法，由冯·诺依曼提出。

  • 可以并行运行

  • 可以方便地应用于链表，慢速外部存储，外部排序。

项目\情况 平均情况 最差情况 最好情况
时间复杂度 $O(n\log_{2}{n})$ $O(n\log_{2}{n})$ $O(n\log_{2}{n})$
比较次数 $O(n\log n)$ $n\log_2n - n+1$ $\frac{n\log_2n}{2}$

堆排序 Heap Sort 与优先队列

堆排序是特殊的排序方式，利用了优先队列的性质。实现良好的优先队列可以实现对数级别的插入元素/删除最大(最小)元素操作。因此对于待排序的n个元素，只要构建一个优先队列，并不断取出最大（最小）元素即可完成排序。

通常使用二叉堆来实现优先队列。

当一颗二叉树的每个节点都大于等于它的两个子节点时，称之为堆有序。这时根节点就是堆有序二叉树的根节点。

二叉堆是一组能够用堆有序的完全二叉树排序的元素，并且在数组中按照层级存储。

如何在数组中表示一颗完全二叉树，一种简单的方式是，首元素置空，然后A[1]放置二叉树的根，A[2],A[3]是根节点的两个子节点，而A[4],A[5],A[6],A[7]则是第三层的节点。

这样表示完全二叉树有一些优良的性质：位置为k的节点，其父节点位置为floor(n/2)，在计算中就是n/2，而其两个儿子的位置分别为2k与2k+1。一颗大小为N的完全二叉树，高度为floor(lgN)

堆的关键操作在于上浮和下沉操作的实现。插入元素其实是在堆尾添加一个元素，并使之上浮至合适的位置。删除最大元素，实质上是删除数组首元素，从数组尾部取元素填空，并使之下沉至合适位置。

class Heap(object):
	def __init__(self):
		self.N = 0
		self.A = [0]
	

	def sink(k):
		while 2*k <= self.N:
			son = 2*k
			# choose big son
			if son + 1 <= self.N and A[son+1]>A[son]:son += 1
			# big son fight papa
			if A[son] > A[k]: swap(A, son, k)
			# history never change
k = son  


	def swim(k):
		while k >= 1 and A[k>>1] < A[k]:
			swap(A, papa, k)
			k >>= 1


	def insert(e):
		self.A.append(e)
		self.N += 1
		self.swim(self.N)


	def delmax(e):
		max_item = self.A[1]
		spare = self.A.pop()
		self.N -= 1
		self.A[1] = spare
		self.sink(1)
return max_item

相应的，堆排序使用类似的机制。首先从数组中创建一个堆，然后依次取出堆中的最大元素。放在数组末尾。

def sink(A, k, N):
    """assume A has a dummy head, N is heap element count"""
    while 2 * k <= N:
        son = 2 * k
        if son + 1 <= N and A[son + 1] > A[son]:
            son += 1
        if A[son] > A[k]:
            A[son], A[k] = A[k], A[son]
        k = son
 
def heap_sort(A):
	if not A or len(A) == 1: return A
	n = len(A)
	A.insert(0,0)	# add dummy head make head operation a lot more easy
	
	# heap creation
	for i in range(n>>1, 0 , -1):
		sink(A, i , n)

	# heap destruction
	while n > 1:
		# first ele of heap is the max item, move to tail
		swap(A, 1, n)
		# adjust heap by sink head element down, with heap size down by 1
		n -= 1
		sink(A, 1, n)
		
	A.pop(0)	# pop out the dummy head
	return A

特性

  • 堆排序在最坏情况下也能保证$O(n\log n)$的时间复杂度，并使用恒定的额外空间。
  • 堆排序实现简单。
  • 堆排序的访问局部性很差，经常出现缓存miss。
  • 使用哑元有助于简化堆排序的代码