概述

提示：本文上万字，陆陆续续疏理知识点加测试代码，耗时近一个月。阅读时长40分钟左右。

本文将十大经典排序算法进行汇总，从源码实现、复杂度、稳定性进行分析，并对每种排序的特性进行点评。对典型算法，给出了具体应用场景。

通俗地讲：

• 如果说插入排序是步步维艰的乌龟，那么希尔排序是跳跃的兔子，冒泡排序就是一个基本无用的小乌龟。选择排序，聊胜于无，比冒泡强一点点。
• 归并排序，将大问题分解成小问题，各个击破，分治思想的完整体现。老板拆解任务，下放给小兵解决，最后老板汇总上报。从国家到公司治理，这个套路很常见。
• 快速排序，人如其名，就是非常快！
• 堆排序，将一维数据建成高维的二叉树，有点“三体”维度打击的意思。

从技术体系上看，共两大类排序算法：

• 比较类排序：通过比较决定元素的相对顺序，理论上可证明：时间复杂度不能突破O(NlogN)的限制, 是非线性排序。
• 非比较类排序，可以突破比较排序的下界O(NlogN), 达到O(N), 故也称为线性排序。但有一些前提假设，后文会一一说明。

排序体系图

每种算法复杂度汇总如下：

说明:

• N：输入序列长度
• k: 桶个数
• d: 最高位数(基数排序)

选择排序

每次找到最小值，放到目标位置。

def selection_sort(x, start: int, end: int):
    for i in range(start, end + 1):
        imin = i
        for j in range(i + 1, end + 1):
            if x[j] < x[imin]:
                imin = j
        x[i], x[imin] = x[imin], x[i]

实现：

• 每次遍历确认x[i]的正确值
• imin: [i, end]中最小元素的index (参见示意图)

时间复杂度:

• i, j两层For循环, 最好最坏区间为[O(N^2),O(N^2)]
• 每次必须遍历完，才能确定最小值, avg/best/worst均为O(N^2)

空间复杂度：通过交换实现原址排序, O(1)

稳定性: 最后一行的 跨越交换 ，会打乱排序，不能保证稳定。比如[5, 5, 2]:

1. [5(1), 5(2), 2]
2. [2, 5(2), 5(1)]

点评：最朴素的思想: 依次选出第一名、第二名、第三名

冒泡排序

逆序遍历，查看相邻元素，如果逆序，偏小值上浮。

def bubble_sort(x, start: int, end: int):
    for i in range(start, end):
        swapped = False
        for j in range(end, i, -1):
            if x[j] < x[j - 1]:
                x[j], x[j - 1] = x[j - 1], x[j]
                swapped = True
        if not swapped:
            break

def bubble_sort_raw(x, start: int, end: int):
    for i in range(start, end):
        for j in range(end, i, -1):
            if x[j] < x[j - 1]:
                x[j], x[j - 1] = x[j - 1], x[j]

实现：

• 正序遍历，最大值下沉；或逆序遍历，最小值上浮。
• 通过检查当前遍历是否有过交换操作，如果无，表明已经排序好，可提前退出。

时间复杂度：

• 双层For循环，时间复杂度为O(N^2)
• 最好：数组已经排序好，可达到O(N)
• 平均、最坏：O(N2)

空间复杂度：原址排序，O(1)

稳定性：相邻的元素才可能交换，非跨越使交换，保证稳定。

点评：

• 频繁交换 相邻 元素，而不能跨越式地交换，是一个缺陷，但带来的好处是能实现稳定排序。和选择排序类似，遍历一遍，确定一个最小元素。
• 玩具算法 ，最简单但基本无用，唯一用法是快速判断一个数组是否已排序。很多新版教材都不提及。

插入排序

从前到后依次构建有序序列；对于待排序元素，在已排序列中从后向前扫描，找到对应位置插入。

def insertion_sort(x, start: int, end: int):
    for i in range(start + 1, end + 1):
        j, key = i - 1, x[i]
        while j >= start and key < x[j]:  # swap only <(NOT<=)
            x[j + 1] = x[j]     # <---------
            j -= 1
        x[j + 1] = key          # <---------


def insertion_sort_vfor(x, start: int, end: int):  # for-loop version
    for i in range(start + 1, end + 1):
        key = x[i]
        for j in range(i - 1, start - 1, -1):
            if key >= x[j]:       # '='保证稳定性
                x[j + 1] = key    # <-- x[j+1]
                break
            x[j + 1] = x[j]   # <-- x[j+1]
        else:
            x[j] = key          # <-------- j==start


def insertion_sort_vbubble(x, start: int, end: int):      # bubble version, slow, but understandable
    for i in range(start + 1, end + 1):
        j = i
        while j >= start + 1 and x[j] < x[j - 1]:
            x[j], x[j - 1] = x[j - 1], x[j]
            j -= 1

实现

• 将已经观察过的元素排序好，待观察元素往里插
• 每次都将x[j+1]赋值: 要么右移x[j+1]=x[j]; 要么x[j+1]=key

时间复杂度

• 最好：虽和选择排序位于O(N^2)同一梯队，但最好可达到O(N)，假设原序列已经排序好，只需要O(N)
• 最坏、平均：均为O(N^2)
• 拿当前处理位置i和之前的位置(i-1, i-2, …)比较, 如果大于或等于, 不交换。最好，只比较N次。

空间复杂度: O(1)

稳定性: 插入时的如果和历史元素值相同，不移动历史数据，能保证稳定

点评：

• 内层循环用while比for更简洁
• 对于短序列或近似排序好的序列，复杂度非常低

希尔排序

对子序列进行插入排序，实现最终排序（子序列步长递减），是对插入排序的优化。

def shell_sort(x, start: int, end: int, version="knuth"):
    n = end - start + 1
    h_list = gaps(n, version=version)

    for h in h_list:
        for i in range(start + h, end + 1):  # h-sort
            j, key = i - h, x[i]
            while j >= start and key < x[j]:
                x[j + h] = x[j]
                j -= h
            x[j + h] = key

def gaps(n: int, version="knuth") -> List[int]:
    """
    get the shell-sort gap list for length=n input sequence
    """
    if version == "shell":
        h_list, h = [], 1           # (3**k-1)//2 for k in [1, 2, 3, ...]
        while h < n // 2:           # 1, 4, 13, 40, 121, 364, 1093
            h_list.append(h)
            h = h * 2
    else:  # "knuth":                     # (3**k-1)//2 for k in [1, 2, 3, ...]
        h_list, h = [], 1
        while h < n // 3:           # 1, 4, 13, 40, 121, 364, 1093
            h_list.append(h)
            h = 3 * h + 1
    return h_list[::-1]

代码：

• 常用的步长序列：reverse(1, 2, 4, 8, 16, 32, …)、reverse(1, 4, 13, 40, 121, 364, 1093, …)
• 理解：对间隔为h的子序列，分别应用插入排序
• 实现：从start+h往后遍历一遍，交替地实现对间隔为h的多个子序列的插入排序

时间复杂度：

• 基于插入排序，最好最坏区间为：[O(N),O(N^2)/(N^1.5)], 取决于步长序列的设计
• 平均：O(N^1.2)

空间复杂度：O(1)

稳定性：虽基于插入排序，但是子序列导致排序不稳定

点评：

• 插入排序两个特征，一个优点是对于近似排好序的序列，复杂度很低；一个缺点是需要频繁移动相邻元素。希尔排序，扬长避短，充分利用插入排序的优点，避免插入排序的缺点。
• 通过对间隔为h的子序列排序，可快速交换，逐步让序列近似排好序过程中本质上还是插入排序，但不是笨笨的顺序遍历
• 如果说插入排序是乌龟，一步一步地移动；那么希尔排序就时兔子，可以几步几步地跳跃

快速排序

随机选取一个标杆元素，左边放小元素，右边放大元素，再递归对左边、右边的子序列快排。

def quick_sort(x: Sequence, start: int, end: int):
    def partition(x, start, end) -> int:  # Lomuto
        idx = int((start + end) // 2)  # random
        x[idx], x[end] = x[end], x[idx]

        m = start
        for i in range(start, end):  # without x[end]
            if x[i] < x[end]:
                x[i], x[m] = x[m], x[i]  # <--------
                m += 1
        x[end], x[m] = x[m], x[end]  # <--- i=end
        return m

    if start >= end: return
    m = partition(x, start, end)
    quick_sort(x, start, m - 1)
    quick_sort(x, m + 1, end)


def quick_sort_hoare(x: Sequence, start: int, end: int):
    def partition(x, start, end) -> int:
        i, j = start - 1, end + 1
        pivot = x[int((start + end) // 2)]
        while True:
            j -= 1
            while x[j] > pivot:
                j -= 1

            i += 1
            while x[i] < pivot:
                i += 1

            if i < j:
                x[i], x[j] = x[j], x[i]
            else:
                return j

    if start >= end: return
    m = partition(x, start, end)
    quick_sort_hoare(x, start, m)
    quick_sort_hoare(x, m + 1, end)

代码:

• 由上而下编程，上层代码只有最后4行，加上partition()
• 函数核心是partition()

时间复杂度:

• 理想情况下，每次选取的x[end]都为中位数, 每次将长度N的原问题平均分为两个子问题, 达到最好的O(NlogN)
• 最坏情况下, 每次选取的x[end]都为最大值或最小值, 最坏为O(N^2)

空间复杂度: 通常实现为原址排序，平均空间复杂(函数调用栈空间，非尾递归，栈空间不能避免）为O(logN)

稳定性: 通常都是不稳定的(最后一次跨越交换导致)，也有稳定版本

点评：

• partition有两个版本，Lomuto版易写；Hoare版通过双指针实现，容易出错，但交换次数会小些，标准库通常基于Hoare版本。
• 解决三色排序问题时，遍历一遍同时实现三个分区的划分标准库的排序算法，基本都是快速排序，因为快速排序的常数因子非常小

三色排序的问题，请访问一次遍历，实现三色排序

归并排序

标准的分治思想：

• 分解：分解成长度相等的左右子序列
• 解决：递归调用归并排序，解决左右子问题
• 合并：合并排序好的左右子序列

def merge_sort(x: Sequence, start: int, end: int):
    def merge(x, start, end):
        m = (start + end) >> 1
        left, right = x[start:m + 1], x[m + 1:end + 1]
        left.append(float('inf'))
        right.append(float('inf'))

        i_left, i_right = 0, 0
        for i in range(start, end + 1):
            if left[i_left] <= right[i_right]: # <=, 保证稳定性
                x[i] = left[i_left]
                i_left += 1
            else:
                x[i] = right[i_right]
                i_right += 1
    if start >= end: return
    m = (start + end) >> 1
    merge_sort(x, start, m)
    merge_sort(x, m + 1, end)
    merge(x, start, end)

代码

• 顶层代码有5行，比quick_sort多出了合并的一行(分治=分解、解决、合并)
• 难点为merge(): 确保稳定性、用哨兵结点

时间复杂度:

• 利用多核, 高度并行化版本，可做到O(logN)
• 不同于quick_sort(), 没有初始化的困惑，每次都严格2分, 最好最坏区间范围：[O(NlogN),O(NlogN)]

空间复杂度: 合并时，需要将left, right合并到新空间，复杂为O(N), 无法直接覆盖原数组

稳定性:

• 当left和right中比较的两数相等时，优先选择left
• 因为left本身就比right靠前,这样可以保证稳定

点评： 快排、归并排序: 均为分治算法，顶层结构一致（分解，解决，合并）

堆排序

优先队列和Top k问题中经常用到 堆 这种数据结构。本节介绍堆的基本性质、堆排序、优先队列、利用堆解决Top k问题。

堆的基本性质

堆，是具有下列性质的近似完全二叉树：每个节点的值都小于等于其左右孩子节点值是小根堆（大于等于则是大根堆）。

下图为大小为N=9的堆，高度、深度为log2(9)=3，为从根节点到叶结点的最长路径长度（边的个数）。根节点深度为0（相当于海平面），叶子结点深度最深。而高度的计算方式与深度相反，认为叶结点为地平面。

父子关系满足：

• left(i) = 2i+1
• right(i) = 2i+2
• parent(i) = (i-1)//2

最后一个非叶结点index为parent(N-1) = (N-1-1)//2。故：

• 非叶结点范围：[0,N//2-1]
• 叶结点范围：[N//2, N-1]

堆化

建立堆(堆化)的过程：

• 从最后一个非叶结点开始，自底向上构建堆。
• 核心函数为heapify(x, i), 假设i的左孩子、有孩子都满足堆的性质。以维护最小堆的性质为例：将i结点依次下沉, 所以复杂度为Height(i)。尾递归, 空间复杂可优化为O(1)，用循环实现

def build_min_heap(x):
    n = len(x)
    for i in range((n-2)//2, -1, -1): # 必须递减，满足heapify中孩子为堆的假设
        min_heapify(x, i, n)

def min_heapify(x, i:int, size:int):
    imin, left, right = i, 2*i+1, 2*i+2
    if left<size and x[left]<x[imin]:
        imin=left
    if right<size and x[right]<x[imin]:
        imin=right
    if i!=imin:
        x[i], x[imin] = x[imin], x[i]
        min_heapify(x, imin, size)

建立堆复杂度为O(N)：

• 有1/2的元素向下比较了1次; 有1/4的元素向下比较了两次; …;
• 根据数学推导，可得比较次数<=2n

堆排序

• 构建最小堆，依次弹出堆顶元素
• 构建最大堆，首尾交换，size缩减1，堆顶元素下沉

def max_heapify(x, i: int, size: int):
    imax, left, right = i, 2 * i + 1, 2 * i + 2
    if left < size and x[left] > x[imax]:
        imax = left
    if right < size and x[right] > x[imax]:
        imax = right
    if i != imax:
        x[i], x[imax] = x[imax], x[i]
        heapify(x, imax, size)

def heap_sort(x):
    n = len(x)                  # build max-heap, O(N)
    for i in range((n - 1 - 1) // 2, -1, -1):
        max_heapify(x, i, n)

    for i in range(n - 1, 0, -1):  # swap and siftdown, O(NlogN)
        x[0], x[i] = x[i], x[0]
        max_heapify(x, 0, size=i)

原址排序，时间复杂度O(NlogN)

实现：

• 建立最大堆：O(N)
• 首尾元素交换，然后堆大小缩减1，堆顶元素下沉：log(N) + log(N-1) + … = O(NlogN)

时间复杂度: O(N+NlogN) = O(NlogN)

• 构建堆: 倒数第二层的元素每个比较1次，倒数底三层元素每个比较2次, …: 微积分计算可得O(N)
• 首尾元素交换，然后堆大小缩减1，堆顶元素下沉：log(N) + log(N-1) + … = O(NlogN)
• heapify()维持堆的性质不变，即使已经排好序，首尾交换也会打乱，使得最好最坏复杂度[O(NlogN),O(NlogN)]

空间复杂度：O(1)如果heapify()递归实现，似乎也需要O(logN)的栈空间，但是是尾递归, 可优化为O(1)的迭代实现

稳定性：每次首尾交换, 跨越式交换，必然不稳定 [5,5,5]

点评：优先先队列、Top k问题，用堆排序非常合适

一种更加容易理解的堆排序(非原址、且建堆复杂度提高)方式如下：

import queue
def heap_sort_using_pq(x, start: int, end: int):
    pq = queue.PriorityQueue()  # 构建堆(优先队列), O(NlogN)
    for i in range(start, end + 1):
        pq.put(x[i])

    for i in range(start, end + 1):  # 弹出最小值, O(NlogN)
        x[i] = pq.get()

实现：

• 构建最小堆（优先队列）: O(NlogN)
• 依次弹出最小值（堆顶元素，并维护堆性质不变）: O(NlogN)

时间复杂度

• O(2NlogN) = O(NlogN), 常数因子比原址排序大
• 从堆顶端拿出最值, 底部末尾拿一个最补上去, 每次POP的复杂度均为O(logN): O(NlogN)

空间复杂度为O(N)

稳定性：每次pop(), 从顶端拿出一个, 末尾拿一个放上去, 必然不稳定 [5,5,5]

优先级队列

Python中，queue.PriorityQueue()是对heapq的OOP封装

• put(item)
• get()

核心源码如下：

from heapq import heappush, heappop
class PriorityQueue(Queue):
    '''Variant of Queue that retrie Entries are typically tuples of
    '''

    def _init(self, maxsize):
        self.queue = []

    def _qsize(self):
        return len(self.queue)

    def _put(self, item):
        heappush(self.queue, item)

    def _get(self):
        return heappop(self.queue)

heapq源码解析

• heapq.heapify(x), 即build_heap()假设左右子树都已经满足堆的性质, 一层一层下沉
• heapq.heappush(e)堆尾部填入元素，一层一层上浮(该元素的祖已经排好序，进行插入排序 即可)
• heapq.heappop()堆顶元素弹出堆底元素放入堆顶, 一层一层下沉(heapify(x, i))

真正工业界的PQ,实现细节需要考虑清楚:

排序稳定性：你该如何令相同优先级的两个任务按它们最初被加入时的顺序返回？ A: 存储进入顺序

如果任务优先级发生改变，你该如何将其移至堆中的新位置？ A: 哈希表存储任务->value, 将value标记为REMOVED, 插入新的元素

或者如果一个挂起的任务需要被删除，你该如何找到它并将其移出队列？ A: 哈希表存储任务->value, 将value标记为REMOVED, 插入新的元素

利用堆，解决top k问题

top-k最小值是个常见问题。比如推荐排序中，给用户推荐用户最感兴趣的k个物品。一种本方法是利用快速排序，然后取前k个元素，复杂度为O(NlogN)。

更好地方法是利用堆。

一种方法是构建一个最小堆O(N)，然后取top-k O(klogN) , 时间复杂度为 O(N + klogN)，空间复杂度为O(N)

另外一种方法，构建大小为k的最大堆, heapq.nsmallest(k)采用的是这种方法，时间复杂度为O(k+Nlogk+klogk), 空间复杂度为O(k)。

想想你是一个功利的班主任，你拥有一间容量为k的教室，你需要从N多个学生中跳出Top k个好学生放进你的教室。

• 构建一个大小为k的最大堆O(k) [ 一个尖子班，人数限制为k ]
• 遍历元素，维护最大堆的性质：(Nlogk) [ 将其余同学依次插班到尖子班 ]如果该元素比最后一名好（小），则堆顶元素替换为该元素，并下沉 [ 只要与尖子班的最后一名比较，就能确认是否能进尖子班 ]
• 对最大堆元素进行快速排序(klogk)

点评：尖子班的最后一名很重要，用最大堆的堆顶，可快速获取最后一名

桶排序

假设输入服从均匀分布，将数据划分到有限数量的桶里，每个桶内部分别排序。

def bucket_sort(x: List[float], k: int = None):  # x ~ uniform [0, 1)
    n = len(x)
    k = n if k is None else k
    buckets = [[] for _ in range(k)]
    for e in x:
        buckets[int(e * k)].append(e)  # e//(1/k), 1/k is capacity of bucket

    for bucket in buckets:
        quick_sort(bucket, 0, len(bucket) - 1)

    ans = []
    for bucket in buckets:
        for e in bucket:
            ans.append(e)

    return ans

时间复杂度：

• 最好：数据服从均匀分布，均匀散落到每个桶，最好达到O(N)
• 最坏：数据严重偏离均匀分布，都算落到某一个桶中，取决于桶内排序算法的复杂度

空间复杂度：O(N+k)

稳定性：取决于桶内排序算法的稳定性

点评： 数据服从均匀分布、将其映射到[0, 1) 区间

巧用桶排序，解决Leetcode上Hard的最大间距问题

计数排序

假设输入为[0, k]区间内的非负整数，将输入数据计数存储在新的序列中，然后逆序遍历输入序列，将该元素写入正确位置。

计数排序，是一种特殊的桶排序，每个桶最多有一个元素。

计数排序强制每个桶容积为1, k可以远大与N, 所以时间、空间复杂度分析均为O(N+k), k必不可少，比如：

• x=[0, 10000]
• N=2
• k=10000

def counting_sort(x: List[int]):
    k, n = max(x), len(x)
    c, ans = [0] * (k + 1), [None] * n

    for e in x:                 # k -> count(k)
        c[e] += 1

    for i in range(1, k + 1):  # k -> count(<=k)
        c[i] += c[i - 1]

    for j in range(n - 1, -1, -1):  # stable sort
        ans[c[x[j]] - 1] = x[j]
        c[x[j]] -= 1

    return ans

实现：计数计数累积逆序输出

时间复杂度：计数序列累积O(k), 两次遍历输入序列O(N), 所以时间复杂度区间为[O(N+k), O(N+k)]

空间复杂度：计数数组、输出序列占用空间为O(N+k)

稳定性：最后一个For循环的逆序遍历输入，保证了稳定性

点评：输入的数据如果有确定范围的整数，通过偏移映射成[0, k]区间内的整数，可用计数排序

基数排序

先低位稳定排序，然后再高位稳定排序，直到最高位。

def counting_sort_for_radix(x: List[int], data: List):
    k, n = max(x), len(x)
    c, ans = [0] * (k + 1), [None] * n

    for e in x:                 # k -> count(k)
        c[e] += 1

    for i in range(1, k + 1):  # k -> count(<=k)
        c[i] += c[i - 1]

    for j in range(n - 1, -1, -1):  # stable sort
        ans[c[x[j]] - 1] = data[j]  # <----------
        c[x[j]] -= 1

    return ans

def radix_sort(x):
    d = len(str(max(x)))
    for i in range(d):
        tmp = [e // (10**i) % 10 for e in x]
        x = counting_sort_for_radix(tmp, x)
    return x

实现：

• 从低位到高位，依次调用稳定排序算法
• 计数排序只有一行和标准代码不通，赋值时用原始数据

空间复杂度:

• O(内部排序)
• 如果为计数排序，O(N+k)=O(N)

时间复杂度:

• d*O(内部排序)
• 如果为计数排序，d*O(N+k) = O(dN+dk) = O(dN)，因为基数排序中k很小（比如十进制中，k=10）

稳定性：是

点评：计数排序+基数排序，k会很小

总结

稳定性分析：有跨越交换的，都不稳定。

• 冒泡排序，相邻元素交换，可保证稳定。
• 归并排序，左右子块中左为先，右为后，保证稳定。
• 插入排序，元素一个一个逐步右移，保证稳定。
• 计数排序，逆序按count值写入，保证稳定。

本地运行的时间比较, 10240个随机整数，10次排序取均值，运行时间如下：

最后来一个动图，将七种比较排序放在一起，看下效果。通过监测对原数组的读写来大致模拟复杂度。注意：

• 归并排序中，新建的数组的操作未统计，会使得归并排序性能偏好
• 堆排序中，为递归实现，可通过循环优化，堆排序性能偏差
• 选取的N=16很小, 时间仅供参考

九宫格中，排序算法分布：

对于随机数据:

对于逆序数据：

对于已排序数据：

更新日志

• 2020-02-24 模板、复杂度、稳定性
• 2020-03-09 增加非比较排序
• 2020-03-11 shell sort