排序算法通览

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

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

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

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

排序算法分类

• 稳定/不稳定：稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。
• 适应性/非适应性：非适应性的算法执行的操作序列独立于数据的顺序。自适应的排序执行不同的操作序列。
• 内部排序/外部排序：内部排序允许随机访问，而外部排序算法必须顺序访问元素（至少在大数据块内）
• 可否应用于链表。
• 是否为原地排序（in-place），原地排序的算法除了少量变量不需要使用额外的空间保存副本。

排序算法性能速查

速记方法

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

分析框架

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

这里给出了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

特性

• 不稳定的排序
• 原地操作
• 非适应性排序：对输入的初始次序不敏感，最坏情况和最好情况区别不大。
• 交换次数在所有基本排序算法中最少，但比较次数较多
• 选择排序在执行中，有序区域前段保持不变。
• 适合对链表排序。

插入排序 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]处生成最小元素观察哨，顺便消除一些逆序对。在后续的循环中，迭代条件就不需要判断索引是否越界了。同时将迭代中的交换改为赋值，可以减少一倍的赋值操作。

特性

• 稳定的排序
• 原地排序
• 适应性排序算法，初始序列大量有序的情况下执行很快。
• 比较次数少，但交换次数多。
• 只访问有序部分的元素，而且是顺序访问，局部性较强。但有序区域在排序过程中会发生变化。

冒泡排序 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)。

希尔排序 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。

归并排序 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)$，需要基本等量的额外存储空间。

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

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

• 可以并行运行

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

堆排序 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。
• 使用哑元有助于简化堆排序的代码