上次分享了6种基础排序算法后，不少同学催更进阶款——毕竟面试和作业里，基数排序、快速排序、随机快速排序、堆排序这些“高效选手”才是常客。作为被数据结构折磨过的大学生，我把这4种进阶排序的原理、代码和运行过程扒得明明白白，这篇一次性讲透！
基数排序
定义与基本思想
- 非比较型整数排序算法
- 按照低位先排序，再收集；再按照高位排序，再收集；依次类推直到最高位
算法步骤
- 取得数组中的最大数确定位数
- 从最低位开始，使用稳定的排序算法（如计数排序）对每一位进行排序
- 重复过程直到最高位完成排序
时间复杂度分析
- 时间复杂度：O(d*(n+k))，其中d为最大位数，k为基数范围
- 空间复杂度：O(n+k)
适用场景与优缺点
- 适用于整数或字符串排序
- 优点：线性时间复杂度，稳定排序
- 缺点：对非整数数据不适用，空间开销较大
快速排序
定义与基本思想
- 分治策略的排序算法
- 通过选取基准元素将数组分为两部分，递归排序子数组
算法步骤
- 选择基准元素（通常为第一个或最后一个元素）
- 分区操作：将小于基准的元素移到左侧，大于基准的元素移到右侧
- 递归排序左右子数组
时间复杂度分析
- 平均时间复杂度：O(n log n)
- 最坏时间复杂度：O(n²)（当数组已有序时）
- 空间复杂度：O(log n)（递归栈空间）
适用场景与优缺点
- 适用于大规模数据排序
- 优点：平均性能优秀，原地排序
- 缺点：最坏情况下性能较差，不稳定排序
随机快速排序
定义与基本思想
- 快速排序的优化版本，通过随机化选择基准元素避免最坏情况
算法步骤
- 随机选择基准元素
- 分区操作与快速排序相同
- 递归排序左右子数组
时间复杂度分析
- 平均时间复杂度：O(n log n)
- 最坏时间复杂度概率极低
- 空间复杂度：O(log n)
适用场景与优缺点
- 适用于需要避免最坏情况的场景
- 优点：性能稳定，避免极端情况
- 缺点：随机化增加额外开销
堆排序
定义与基本思想
- 基于二叉堆的排序算法
- 通过构建最大堆或最小堆实现排序
算法步骤
- 构建最大堆（或最小堆）
- 将堆顶元素与末尾元素交换，调整剩余元素为新堆
- 重复过程直到堆为空
时间复杂度分析
- 时间复杂度：O(n log n)（建堆和调整堆）
- 空间复杂度：O(1)（原地排序）
适用场景与优缺点
- 适用于需要原地排序的场景
- 优点：时间复杂度稳定，不需要额外空间
- 缺点：不稳定排序，缓存不友好
对比与总结
性能对比
- 基数排序：线性时间但限制较多
- 快速排序：平均性能最优但最坏情况差
- 随机快速排序：避免最坏情况
- 堆排序：稳定但缓存效率低
选择建议
- 整数排序：基数排序
- 通用排序：快速排序或随机快速排序
- 内存受限：堆排序
应用场景举例
- 基数排序：电话号码排序
- 快速排序：大规模数据排序
- 堆排序：优先级队列实现
一、基数排序：“按位拆分，逐位排序”
核心思路（大学生白话版）
像整理学号：先按个位把数字分到0-9号桶里，排好序；再按十位重新分桶排序；直到最高位处理完，整个数组就有序了。本质是“按位拆分+桶排序”的组合，专克多位数排序。
代码与运行过程
def RadixSort(a): base = 1 # 初始按个位排序（base=1） maxv = max(a) while base < maxv: bucket = [] # 初始化0-9共10个桶 for idx in range(10): bucket.append([]) # 按当前位（base）的值分桶 for num in a: idx = (num // base) % 10 # 取当前位的数字 bucket[idx].append(num) # 把桶里的元素按顺序放回原数组 l = 0 for idx in range(10): for v in bucket[idx]: a[l] = v l += 1 print(a) # 打印每轮排序结果 base *= 10 # 切换到更高位（个位→十位→百位...） a = [3121,897,3122,3,23,5,55,7,97,123,345,1423] RadixSort(a)每轮按一位排序，逐步让数组整体有序：
[3121, 3122, 3, 23, 123, 1423, 5, 55, 345, 897, 7, 97] # 按个位排序 [3, 5, 7, 3121, 3122, 23, 123, 1423, 345, 55, 897, 97] # 按十位排序 [3, 5, 7, 23, 55, 97, 3121, 3122, 123, 345, 1423, 897] # 按百位排序 [3, 5, 7, 23, 55, 97, 123, 345, 897, 1423, 3121, 3122] # 按千位排序（最终有序）特点
时间复杂度：$O(d \times (n + k))$（$d$是最高位数，$k=10$）
空间复杂度：$O(n + k)$（需要10个桶）
稳定排序
适合多位数整数排序（如学号、手机号）
二、快速排序：“选基准，分左右，递归排序”
核心思路（大学生白话版）
像分水果：选一个“基准”（比如苹果），把比它小的放左边，比它大的放右边；再对左右两堆分别选基准、重复分堆，直到每堆只有一个水果——这就是“分治”思想的经典应用。
代码与运行过程
def QuickSortPivot(a, start, end): pivot = start # 选第一个元素做基准 j = start + 1 # 把比基准小的元素移到左边 for i in range(start+1, end+1): if a[i] < a[pivot]: a[j], a[i] = a[i], a[j] j += 1 # 把基准放到左右区间的中间 a[pivot], a[j-1] = a[j-1], a[pivot] pivot = j - 1 print(a[pivot], a[start:pivot], a[pivot+1:end+1]) # 打印基准和左右区间 return pivot def QuickSort(a, start, end): if start >= end: return pivot = QuickSortPivot(a, start, end) QuickSort(a, start, pivot-1) # 递归排序左区间 QuickSort(a, pivot+1, end) # 递归排序右区间 a = [8,5,12,6,4,3,7,9,2,1,10,11] QuickSort(a, start=0, end=11) print(a)每轮选基准、分左右，逐步缩小排序区间：
8 [1,5,6,4,3,7,2] [12,9,10,11] # 基准8，左小右大 1 [] [5,6,4,3,7,2] # 左区间基准1，右边都是大的 5 [2,4,3] [7,6] # 左区间基准5，再分左右 ...最终得到有序数组：[1,2,3,4,5,6,7,8,9,10,11,12]特点
时间复杂度：$O(n\log n)$（平均），$O(n^2)$（最坏，数组已近有序）
空间复杂度：$O(\log n)$（递归栈）
不稳定排序
实际应用中效率极高，是工业界常用排序算法
三、随机快速排序：“随机选基准，避免最坏情况”
核心思路（大学生白话版）
解决普通快速排序的“致命缺点”：如果数组已近有序，选第一个元素当基准会导致时间复杂度飙升到$O(n^2)$。随机选基准能避免这种极端情况，让时间复杂度稳定在$O(n\log n)$。
代码与运行过程
import random def QuickSortPivot(a, start, end): # 随机选一个元素和第一个元素交换，作为基准 randIdx = random.randint(start, end) a[start], a[randIdx] = a[randIdx], a[start] pivot = start j = start + 1 for i in range(start+1, end+1): if a[i] < a[pivot]: a[j], a[i] = a[i], a[j] j += 1 a[pivot], a[j-1] = a[j-1], a[pivot] pivot = j - 1 print(a[pivot], a[start:pivot], a[pivot+1:end+1]) return pivot def QuickSort(a, start, end): if start >= end: return pivot = QuickSortPivot(a, start, end) QuickSort(a, start, pivot-1) QuickSort(a, pivot+1, end) a = [8,5,12,6,4,3,7,9,2,1,10,11] QuickSort(a, start=0, end=11) print(a)随机选基准后，区间划分更均匀：
6 [5,4,3,2,1] [8,12,7,9,10,11] # 随机选基准6，左小右大 3 [2,1] [5,4] # 左区间随机选基准3，划分均衡 ...最终同样得到有序数组：[1,2,3,4,5,6,7,8,9,10,11,12]特点
时间复杂度：$O(n\log n)$（平均/期望）
空间复杂度：$O(\log n)$
不稳定排序
比普通快速排序更稳定，是实际开发的首选快速排序版本
四、堆排序：“利用堆结构，依次取最值”
核心思路（大学生白话版）
先把数组构建成大顶堆（堆顶是最大值），然后把堆顶（最大值）和堆尾元素交换，再把堆的规模缩小1，重新调整成大顶堆；重复这个过程，直到堆为空——最终数组就是升序排列的。
代码与运行过程
def maxHeapify(heap, start, end): """堆调整函数：将以start为根的子树调整为大顶堆""" son = start * 2 # 打印当前要调整的节点和其子节点范围 print(f" 调整堆节点 {start} (子节点范围: {son}~{end}) | 当前堆: {heap}") while son <= end: # 选择左右子节点中较大的那个 if son + 1 <= end and heap[son + 1] > heap[son]: son += 1 print(f" 选择右子节点 {son} (值更大)") # 如果子节点大于父节点，交换 if heap[son] > heap[start]: print(f" 交换节点 {start}({heap[start]}) 和 {son}({heap[son]})") heap[start], heap[son] = heap[son], heap[start] start, son = son, son * 2 # 继续向下调整 print(f" 调整后堆: {heap}") else: print(f" 无需交换，当前子树已是大顶堆") break def HeapSort(a): """堆排序主函数""" heap = [None] + a # 堆从索引1开始，方便计算父子节点 root = 1 l = len(heap) print("===== 第一步：构建大顶堆 =====") # 从最后一个非叶子节点开始，自下而上构建大顶堆 for i in range(l//2, root-1, -1): print(f"\n开始调整非叶子节点 {i}:") maxHeapify(heap, i, l-1) print("\n===== 第二步：堆排序（逐步取出最大值） =====") # 逐步将堆顶最大值放到数组末尾，然后调整剩余堆 for i in range(l-1, root, -1): print(f"\n将堆顶({heap[root]})与末尾节点 {i}({heap[i]}) 交换 | 交换前: {heap}") heap[i], heap[root] = heap[root], heap[i] print(f"交换后: {heap} (已确定位置 {i} 的值为 {heap[i]})") print(f"调整剩余堆（范围: 1~{i-1}）:") maxHeapify(heap, root, i-1) return heap[root:] # 测试数组 a = [1,2,3,4,5,6,7,8,9,10,11,12,13,14] print("原始数组:", a) result = HeapSort(a) print("\n===== 最终排序结果 =====") print(result)构建大顶堆后，依次取最值得到有序数组：
原始数组: [1,2,3,4,5,6,7,8,9,10,11,12,13,14] ===== 第一步：构建大顶堆 ===== 开始调整非叶子节点 7: 调整堆节点 7 (子节点范围: 14~14) | 当前堆: [None, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] 无需交换，当前子树已是大顶堆 开始调整非叶子节点 6: 调整堆节点 6 (子节点范围: 12~14) | 当前堆: [None, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] 无需交换，当前子树已是大顶堆 ... ===== 第二步：堆排序（逐步取出最大值） ===== 将堆顶(14)与末尾节点 14(7) 交换 | 交换前: [None, 14, 13, 12, 10, 11, 6, 7, 8, 9, 4, 5, 2, 3, 1] 交换后: [None, 1, 13, 12, 10, 11, 6, 7, 8, 9, 4, 5, 2, 3, 14] (已确定位置 14 的值为 14) 调整剩余堆（范围: 1~13）: 调整堆节点 1 (子节点范围: 2~13) | 当前堆: [None, 1, 13, 12, 10, 11, 6, 7, 8, 9, 4, 5, 2, 3, 14] 选择左子节点 2 (值更大) 交换节点 1(1) 和 2(13) 调整后堆: [None, 13, 1, 12, 10, 11, 6, 7, 8, 9, 4, 5, 2, 3, 14] ... ===== 最终排序结果 ===== [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]特点
时间复杂度：$O(n\log n)$（最好/最坏/平均）
空间复杂度：$O(1)$（原地排序）
不稳定排序
适合需要找最值的场景（比如TopK问题）
4大进阶排序算法选型总结
算法 | 时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|
基数排序 | $O(d \times (n+k))$ | $O(n+k)$ | 稳定 | 多位数整数排序 |
快速排序 | $O(n\log n)$（平均） | $O(\log n)$ | 不稳定 | 大规模数据（实际效率高） |
随机快速排序 | $O(n\log n)$（期望） | $O(\log n)$ | 不稳定 | 大规模数据（更稳定） |
堆排序 | $O(n\log n)$ | $O(1)$ | 不稳定 | 大规模数据、TopK问题 |
到这里，基础+进阶共10种排序算法就全讲完啦！从$O(n^2)$的简单排序，到$O(n\log n)$的高效排序，每种算法都有自己的“生存空间”——理解它们的适用场景，写代码时才能既高效又省心。
