1 概述

本文对经典排序算法进行汇总，覆盖实现、复杂度分系、稳定性分析，并对每种排序算法的特性进行总结，其中对典型算法，给出了具体应用场景。

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

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

对7种比较类排序算法进行通俗解读：

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

在数据符合特定条件(如整数、范围有限)时，用非计数排序：

• ​桶排序​，先粗分桶，再桶内排序。

-​ 计数排序​，直接统计数量，然后“数”出顺序。

• ​基数排序​，从最低位到最高位排序，进行多轮稳定的“分发-收集”。

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

说明:

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

2 选择排序

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

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]

• 实现：

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

• 时间复杂度: i, j两层For循环, 最好最坏区间为\([O(N^2), O(N^2)]\)

  • 每次必须遍历完，才能确定最小值, avg/best/worst均为O(N^2)
• 空间复杂度：通过交换实现原址排序, O(1)

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

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

• 点评：

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

3 冒泡排序

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

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(N^2)\)
• 空间复杂度：原址排序，O(1)
• 稳定性：相邻的元素才可能交换，非跨越式交换，保证稳定。

• 点评：

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

4 插入排序

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

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更简洁
  • vbubble版本类似冒泡排序，将当前元素冒泡到正确位置，代码简洁，但交换频繁
  • vfor版本For-Else, 需要判断边界条件
  • 对于短序列或近似排序好的序列，复杂度非常低

5 希尔排序

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

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的子序列排序，可快速交换，逐步让序列近似排好序
  • 过程中本质上还是插入排序，但不是笨笨的顺序遍历
  • 如果说插入排序是乌龟，一步一步地移动；那么希尔排序就时兔子，可以几步几步地跳跃

6 快速排序

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

def quick_sort(x: Sequence, start: int, end: int):
    """
    对[x[start], x[end]]进行排序
    Args:
      x:
      start: 待排序的区间为[x[start], x[end]]
      end: 待排序的区间为[x[start], x[end]]
    """
    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]  # <--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(), m: 表示 \(\ge x[end]\) 的首个位置, \(m-start\) 为累积小于x[end]的元素个数, 初始值设定 \(m-start==0\)

• 时间复杂度:

  • 理想情况下，每次选取的x[end]都为中位数, 每次将长度N的原问题平均分为两个子问题, 达到最好的\(O(N\log N)\)
  • 最坏情况下, 每次选取的x[end]都为最大值或最小值, 最坏为\(O(N^2)\)
• 空间复杂度: 通常实现为原址排序，平均空间复杂(函数调用栈空间，非尾递归，栈空间不能避免）为O(logN)
• 稳定性: 通常都是不稳定的(最后一次跨越交换导致，x[end], x[m]=x[m], x[end]，举例x=[5,5,5])，也有稳定版本

• 点评：

  • quick_sort, partition 中的start, end均为闭区间，即[start, end]
  • partition有两个版本，Lomuto版易写；Hoare版通过双指针实现，容易出错，但交换次数会小些，标准库通常基于Hoare版本。

  • 解决三色排序问题时，遍历一遍同时实现三个分区的划分

    

  • 标准库的排序算法，基本都是快速排序，因为快速排序的常数因子非常小

6.1 三色排序

Leetcode 75题，颜色分类中，对输入数组进行排序，数组只含0、1、2，对应三种不同的颜色

• i: 0的个数
• j: “0, 1”的个数
• k: “0, 1, ?”的个数

• n-k: 2的个数

  def sortColors(self, nums: List[int]) -> None:
      i, j, k = 0, 0, len(nums)
      while j < k:
          if nums[j] == 0:
              nums[j], nums[i] = nums[i], nums[j]
              i = i + 1
              j = j + 1
          elif nums[j] == 1:
              j += 1
          else:
              k = k - 1
              nums[j], nums[k] = nums[k], nums[j]

  注意：如果把less, equal, greater全部放在一起，会有三数（i, j, k）同时交换，存在类似（i==j）边界问题，极易写错。

7 归并排序

标准的分治思想：

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

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)]\)
  • T(N) = 2T(N/2) + f(N) => O(NlogN)

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

  • left: 1 21 34 39
  • right: 10 20 30 40
  • 1和10比较，选择1; 10和21比较，选择10, 不能交换10, 21, 因为21 20 30 40 破坏了有序的性质

• 稳定性:

  • 当left和right中比较的两数相等时，优先选择left，因为left本身就比right靠前,这样可以保证稳定
• 点评： 快排、归并排序: 均为分治算法，顶层结构一致（分解，解决，合并）

• 100M内存，100G数据，如何排序? 多路归并排序

  • 合并的时候，每个数据块读取1个元素，最小值写入目标文件

8 堆排序

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

8.1 堆的基本性质

堆，是具有下列性质的近似*完全二叉树*：每个节点的值都小于等于其左右孩 子节点值是小根堆（大于等于则是大根堆）。下图为大小为N=9的堆，高度、 深度为log2(9)=3，为从根节点到叶结点的最长路径长度（边的个数）。根节 点深度为0（相当于海平面），叶子结点深度最深。而高度的计算方式与深度 相反，认为叶结点为地平面。

近似完全二叉树中，父子关系下标满足：

• left(i) = 2i+1
• right(i) = 2(i+1)

• parent(i) = (i-1)//2 故内部可用数组直接实现。

  

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

  • 非叶结点范围：[0,N//2-1], 构建堆时在这个范围内自底向上siftdown
  • 叶结点范围：[N//2, N-1]

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()

9 桶排序

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

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_{worst}(inner-sort)\)

    • 如果为快排，分布到同一个桶，且快排每次选取的标杆值运气很差，则最坏为\(O(N^2)\)
    • 如果为插入排序，则最坏为\(O(N^2)\)

  • 平均:

    • 划分入桶：O(N)

    • 桶内排序：\(k O_{avg}(inner-sort, \frac{n}{k})\)

      • 如果用快排：\(k O(\frac{N}{k}\log\frac{N}{k}) = N \log \frac{N}{k}\)
      • 如果用插入：\(k O({\frac{N}{k}}^{2}) = O(\frac{N^2}{k})\)
    • 合计：\(O(N+N \log \frac{N}{k})\) 或 \(O(N + \frac{N^2}{k})\), 一般\(k=O(N)\), 最终为 O(N)
• 空间复杂度：O(N+k)
• 稳定性：取决于桶内排序算法的稳定性
• 点评： 数据服从均匀分布、将其映射到[0, 1) 区间

10 计数排序

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

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

• (k+1)个桶

• N个数

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

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

  def counting_sort(x: List[int]) -> List[int]:
      k, n = max(x), len(x) #
      c, ans = [0] * (k + 1), [None] * n
  
      for e in x:                # i -> count(k), O(N)
          c[e] += 1
  
      # <=i的数有个c个
      for i in range(1, k + 1):  # i -> count(<=k), O(k)
          c[i] += c[i - 1]
  
      # <=i的数有个c个, 当前数为x[j], x[j]必然位于<c-1>
      # 逆序遍历，保证稳定性，因为c[i]由大到小递减，第一个i会放到较大的位置
      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]区间内的整数，可用计数排序

11 基数排序

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

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会很小

  

12 总结

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

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

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

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

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

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

13 参考文献

• 算法导论
• 除最后三个动图外，其余动图均来自wiki: sorting algorithm

14 更新日志

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