Hello 算法之十大排序

写在前面

本文复习自用，因为近期的几次面试都考察了比较基础的排序算法，所以记录一下。内容均来自Hello 算法 - 排序，这本书中详细描述了算法基础、各种数据结构以及各种算法类型，对我的帮助很大。再次感谢作者和各位贡献者的分享。

冒泡排序

通过连续比较与交换相邻元素实现排序。即使是经过优化，最差和最优的平均复杂度也为O(n^2)，但是在输入数组完全有序的情况下，可以达到最佳的时间复杂度 O(n)，属于稳定排序，在冒泡中遇到的相等元素不交换。

数组从最左端向右遍历，依次比较相邻元素大小，如果左元素>右元素就交换它俩，遍历完成后，最大的元素会被移到数组最右端。比较次数：n-1, n-2, …, 2, 1 总和为 (n - 1)n/2

nums = [5, 3, 1, 2, 4]
n = len(nums)
for i in range(n - 1, 0, -1): # 外循环，未排序区间[0, i]
    for j in range(i): # 内层循环将[0, i]的最大元素交换至区间最右端
        if nums[j] > nums[j + 1]:
            nums[j + 1], nums[j] = nums[j], nums[j + 1]
print(nums)

优化：标志位记录，如果没有交换，提前结束

nums = [5, 3, 1, 2, 4]
n = len(nums)
for i in range(n - 1, 0, -1): # 外循环，未排序区间[0, i]
    flag = False # 标志位记录是否完成排序
    for j in range(i): # 内层循环将[0, i]的最大元素交换至区间最右端
        if nums[j] > nums[j + 1]:
            flag = True
            nums[j + 1], nums[j] = nums[j], nums[j + 1]
    if not flag:
        break
print(nums)

归并排序

基于分治策略的排序算法，通过划分和合并组成。时间复杂度O(nlogn)，空间复杂度 O(n)，属于稳定排序，合并过程中，相等元素的次序保持不变。

划分：通过递归将数组从中点处分开，将长数组的排序转换为短数组的排序问题

合并：当子数组长度为 1 时，开始合并，持续将左右两个较短的有序数组组合为一个较长的有序数组，直到结束。

可以看到每一层都是 n，合并排序每一层的时间复杂度是 o(n)（可以参考合并两个有序数组），有 logn 层，因此时间复杂度是 O(nlogn)。

nums = [5, 3, 1, 2, 4]
n = len(nums)
def merge_sort(nums, left, right):
    if left >= right:
        return
    mid = (left + right) >> 1
    merge_sort(nums, left, mid)
    merge_sort(nums, mid + 1, right)
    merge(nums, left, mid, right)

def merge(nums, left, mid, right):
    tmp = list(nums[left:right + 1]) # 辅助数组，记录原先的值
    left_start = 0 # 左子数组的起始索引和结束索引
    left_end = mid - left
    right_start = mid + 1 - left # 右子数组的起始索引和结束索引
    right_end = right - left
    i = left_start # 左右子数组首元素索引
    j = right_start
    for k in range(left, right + 1):
        if i > left_end: # 只剩右子数组
            nums[k] = tmp[j]
            j += 1
        elif j > right_end or tmp[i] <= tmp[j]: # 只剩左子数组，或者左子数组的值更小
            nums[k] = tmp[i]
            i += 1
        else:
            nums[k] = tmp[j]
            j += 1
merge_sort(nums, 0, n - 1)
print(nums)

选择排序

开启一个循环，每轮从未排序区间选择最小的数，放到已排序区间的末尾。时间复杂度O(n^2)，比较次数包括 n, n-1, n-2, …, 3, 2 总共 (n - 1)(n + 2) / 2。非稳定排序，在经过选择后，相对顺序会更改。

流程如下

1. 初始状态所有元素未排序，未排序区间[0,n-1]
2. 从[0,n-1]找到最小的数的下标，与 0 交换
3. 从[1,n-1]找到最小的数的下标，与 1 交换
4. …直到 n-1 轮

nums = [5, 3, 1, 2, 4]
n = len(nums)

for i in range(n):
    minn = i
    for j in range(i, n):
        if nums[j] <= nums[minn]:
            minn = j
    nums[minn], nums[i] = nums[i], nums[minn]
print(nums)

插入排序

在未排序区间选择一个基准元素，将其与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确位置。基于元素赋值实现

时间复杂度O(n^2)，最差情况下分别需要比较 n-1, n-2, …, 2, 1 次，总和为 n(n-1)/2。实际遇到有序后会提前终止，当数组完全有序，复杂度为 O(n)。属于稳定排序，插入时会将元素插入到同等元素的右边，不会更改顺序。

流程如下

1. 初始时第一个元素已完成排序
2. 选择第二个元素作为 base，将其插入已排序的里面的正确位置
3. 选择第三个元素作为 base，将其插入已排序区间的正确位置
4. 直到最后一轮

nums = [5, 3, 1, 2, 4]
n = len(nums)

for i in range(1, n): # 遍历未排序区间[1, n - 1]
    base = nums[i]
    j = i - 1
    while j >= 0 and base < nums[j]: # 将base插到已排序区间[0, i]的某个正确位置
        nums[j + 1] = nums[j] # 将nums[j]后移一位，为base腾出空间
        j -= 1
    nums[j + 1] = base
print(nums)

虽然比快排的复杂度高，但插入排序的优势在于小数据量下通常会更快。

快速排序

基于分治策略的排，核心操作是哨兵划分，选择数组中某个元素作为基准数，将所有小于基准数的元素移到其左侧，将所有大于基准数的元素移到其右侧。时间复杂度为O(nlogn)，平均情况下哨兵划分递归层数为 log n，每层总循环 n 次，共 O(nlogn) 时间。最差情况下，每次划分为 0 和 n-1 长度的数组，递归层数为 n，每层循环数为 n，总体就是 O(n^2)。属于非稳定排序，在哨兵划分的最后一步，基准数可能会被交换到相等元素的右侧。

流程如下

1. 选择数组最左侧元素作为基准数，初始化 i 和 j 指向数组左右两端
2. 设置一个循环，每轮用 i、j 分别寻找到第一个比基准数大、小的元素，然后交换这俩元素
3. 重复直到 i 和 j 相遇，交换基准数至俩子数组的分界线。

nums = [5, 3, 1, 2, 4]
n = len(nums)

def partition(nums, left, right):
    i, j = left, right # 以nums[left]作为基准数
    while i < j:
        while i < j and nums[j] >= nums[left]: # 找到右区间第一个比基准数小的
            j -= 1
        while i < j and nums[i] <= nums[left]: # 找到左区间第一个比基准数大的
            i += 1
        nums[i], nums[j] = nums[j], nums[i] # 交换这俩，保证左边都比基准数小，右边都比基准数大
    nums[i], nums[left] = nums[left], nums[i] # 将基准数放中间
    return i # 哨兵位置

def quick_sort(nums, left, right):
    if left >= right:
        return
    pivot = partition(nums, left, right) # 哨兵划分
    quick_sort(nums, left, pivot) # 递归左、右区间
    quick_sort(nums, pivot + 1, right)

quick_sort(nums, 0, n - 1)
print(nums)

快排优点：

大多数情况下都是以 O(nlogn) 复杂度运行，在执行哨兵划分时能用到系统缓存（将整个子数组加载到系统缓存，因为是连续的），快排的比较、赋值、交换次数更少（如果插入排序比冒泡排序快一样）

优化：

如果数组完全倒序，那么每次选择最左元素为基准数都会交换到最右端，导致 O(n^2)，退化为冒泡排序。可以优化基准数的选择策略，随机选择一个元素为基准数，或者说从前中后三个数中选择中位数作为基准数。

尾递归优化，某些输入下快排占用空间会很多，比如完全倒序，会占 O(n) 的栈空间。可以在每轮哨兵完成排序后，比较左右俩子数组的长度，仅对长度较小的子数组进行递归。

def quick_sort2(nums, left, right):
    while left < right:
        pivot = partition(nums, left, right)
        if pivot - left < right - pivot:
            quick_sort2(nums, left, pivot - 1) # 对左子区间递归
            left = pivot + 1 # 剩余未排序区间为[pivot + 1, right]
        else:
            quick_sort2(nums, pivot + 1, right) # 对右子区间递归
            right = pivot - 1

堆排序

基于堆的排序。时间复杂度O(nlogn)，其中建堆用 O(n)，取最大元素时间复杂度 O(logn)，共循环 n-1 轮。非稳定排序，在交换堆顶元素和堆底元素时，相等元素的位置可能会发生变化。

流程如下：

1. 输入数组并建立大顶
2. 将堆顶元素与堆底元素（最后一个）交换，完成交换后，堆长度 -1，已排序元素数量 +1
3. 从堆顶开始，从顶到底执行堆化（sift down），调整堆
4. 循环执行 2、3 步，直到 n-1 轮完成

nums = [5, 3, 1, 2, 4]
n = len(nums)

def sift_down(nums, root, k):
    t = nums[root] # 父节点
    while root << 1 < k: # k指堆大小
        child = root << 1 # 左子节点
        if child | 1 < k and nums[child | 1] > nums[child]: # 检查右子节点是否有机会
            child |= 1
        if nums[child] > t: # 如果当前元素更小，则递归向下，使得堆顶元素更大
            nums[root] = nums[child]
            root = child
        else: # 如果到了合适的位置，则赋值
            break
    nums[root] = t

nums = [0] + nums # 哨兵，基于此可以通过位运算快速定位子节点以及父节点
k = len(nums)

for i in range((k - 1) >> 1, 0, -1): # 建堆
    sift_down(nums, i, k)
for i in range(k - 1, 0, -1): # 取最大元素与堆底元素交换，并从顶到底调整堆
    nums[1], nums[i] = nums[i], nums[1]
    sift_down(nums, 1, i)

print(nums[1:])

桶排序

基于分治，非比较的排序算法，通过设置一些具有大小的桶，每个桶对应一个数据范围，将数据平均分散到桶中，然后对桶内执行排序（往往不需要，因为多数只有一个数），最终按照桶范围合并。时间复杂度一般是线性的，n 个数 k 个桶，O(n + k)，假设分布均匀，每个桶内元素 O(n/k)，排序耗时 O((n/k)log(n/k))，所有桶排序则 O(nlog(n/k))。当桶足够大，分散足够均匀，每个桶一个数，则趋向于O(n)。是否稳定基于桶内排序是否稳定。

流程如下

1. 初始化 k 个桶，将 n 个数分到 k 个桶
2. k 个桶分别执行排序
3. 从小到大合并 k 个桶

nums = [56, 32, 13, 26, 43]
n = len(nums)

k = 6
bucket = [[] for _ in range(k)] # 分k个桶
for x in nums:
    i = x // 10
    bucket[i].append(x)
for b in bucket:
    b.sort()
i = 0
for x in bucket:
    for xx in x:
        nums[i] = xx
        i += 1
print(nums)

主要是如何去将原始数据平均分散到多个 bucket 中。可以创建递归树来做，对数量多的 bucket 进行再分桶，或者通过概率统计来分桶。

计数排序

通过统计数量来对元素实现排序，适用于较为密集的数组。时间复杂度O(n + m)，包括遍历数组以及计数器。一般 n >> m，趋近于 O(n)。通过倒序遍历可以避免修改元素之间的相对位置，正序则非稳定。

流程如下

1. 遍历数组找到最大数 m，创建一个 m+1 辅助数组
2. 遍历数组计数
3. 编辑计数器统计出现次数，填充即可

nums = [5, 3, 1, 2, 4, 3, 2, 1]
n = len(nums)

maxx = max(nums)
c = [0] * (maxx + 1)
for x in nums:
    c[x] += 1
idx = 0
for i, x in enumerate(c): # 遍历计数器
    while x > 0: # 递减计数器
        nums[idx] = i # 填充nums
        x -= 1
        idx += 1
print(nums) # [1, 1, 2, 2, 3, 3, 4, 5]

基数排序

通过统计个数实现排序，但是主要利用数字各个位之间的递进关系，依次对每一位排序，适用于数值范围较大的，较分散的数组。时间复杂度 O(nk)，n 为数据量，d 为进制，k 为最大位数。对一位执行计数排序是 O(n + d)，排序 k 位就是 O(k(n + d))，通常趋向于 O(n)。通过倒序遍历可以避免修改元素之间的相对位置，正序则非稳定。

流程如下

1. 初始化位数 k=1
2. 针对第 k 位进行计数排序，整个数进行变动
3. 将 k+1，返回第二步，直到结束

nums = [10546151, 35663510, 21233312, 97422133, 22188831]
n = len(nums)

def digit(x, exp): # 取x的第k位返回，对10 100 1000...整除后取模
    return (x // exp) % 10

def counting_sort_digit(nums, exp):
    counter = [0] * 10 # 对每一位计数 0~9
    n = len(nums)
    for i in range(n): # 统计0~9出现次数
        d = digit(nums[i], exp)
        counter[d] += 1
    for i in range(1, 10): # 前缀和, 将个数转换为索引，比如 0 1 1 2 0 1 -> 0 1 2 4 4 5
        counter[i] += counter[i - 1]
    print(counter)
    res = [0] * n # 倒序遍历存入结果数组
    for i in range(n - 1, -1, -1):
        d = digit(nums[i], exp) # d为nums[i]的第k位值
        j = counter[d] - 1 # 获取d所在索引
        res[j] = nums[i] # 填入
        counter[d] -= 1 # 索引-1，因为可能有重复的 0 1 2 4 4 5 -> 0 1 2 3 4 5
    for i in range(n):
        nums[i] = res[i] # 覆盖

def radix_sort(nums):
    m = max(nums)
    exp = 1
    while exp <= m:
        counting_sort_digit(nums, exp)
        exp *= 10
radix_sort(nums)
print(nums)

总结

排序算法各有特点，在选择使用时需要跟据适用的场景来选择，而不是盲目选择快排等更知名的排序。