排序算法实战篇（二）：4大进阶排序原理+Python代码+运行过程-平芜编程栈

上次分享了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问题