排序
三路快排（原地）¶
In [ ]:
Copied!
# 如果你忘记了这个代码的原理，请看下面的代码演示，能迅速帮助你回忆
"""
不变式把数组划成四段：[low, lt-1] 小于 pivot, [lt, i-1] 等于 pivot,[i, gt] 尚未处理，[gt+1, high] 大于 pivot。
整个循环的唯一任务是让未处理段 [i, gt] 不断收缩，直至消失，同时保证前述四段始终成立。由不变式直接推出循环体的三种情形。
当前元素小于 pivot 时，把它塞入左侧小于区的尾部，并前推 lt 与 i 两个指针。大于 pivot 时，塞入右侧大于区的头部，i 不前进，因为换过来的元素尚未检验。
等于 pivot 时,直接扩大等于区, i 前进一步。算法的全部逻辑就此闭合。
回到基准选择的问题。基准必须位于 low 的原因仅来自初始化:lt = low 且 i = low + 1 意味着 nums[low] 在循环中永远不会被指针 i 访问，
同时它又被默认划入等于区。若 nums[low] 的真实值与 pivot 不符，等于区从第一步起就被污染，不变式随之失效。
随机选基准与此并不冲突，只是随机得到的位置必须通过一次交换回到 low, 才能让初始化自洽。那一行 swap 的本质是将随机化与模板之间的接口对齐。
"""
def quick_sort_3way(nums):
def sort(low, high):
# 区间长度小于等于1时，结束递归
if high <= low:
return
# 选取当前区间第一个元素作为基准值
pivot = nums[low]
lt = low # 小于区的右边界
gt = high # 大于区的左边界
i = low + 1 # 当前扫描指针
"""
nums[low : lt-1] < pivot
nums[lt : i-1] == pivot
nums[i : gt] 未处理
nums[gt+1 : high] > pivot
"""
# 扫描到大于区间的左边界，表示全部元素已扫描
while i <= gt:
# 当前元素小于基准
if nums[i] < pivot:
nums[lt], nums[i] = nums[i], nums[lt]
lt += 1
i += 1
elif nums[i] > pivot:
nums[gt], nums[i] = nums[i], nums[gt]
gt -= 1
else:
i += 1
sort(low, lt - 1)
sort(gt + 1, high)
sort(0, len(nums) - 1)
nums = [200, 100 ,6, 10, 4, 10]
quick_sort_3way(nums)
nums
# 如果你忘记了这个代码的原理，请看下面的代码演示，能迅速帮助你回忆
"""
不变式把数组划成四段：[low, lt-1] 小于 pivot, [lt, i-1] 等于 pivot,[i, gt] 尚未处理，[gt+1, high] 大于 pivot。
整个循环的唯一任务是让未处理段 [i, gt] 不断收缩，直至消失，同时保证前述四段始终成立。由不变式直接推出循环体的三种情形。
当前元素小于 pivot 时，把它塞入左侧小于区的尾部，并前推 lt 与 i 两个指针。大于 pivot 时，塞入右侧大于区的头部，i 不前进，因为换过来的元素尚未检验。
等于 pivot 时,直接扩大等于区, i 前进一步。算法的全部逻辑就此闭合。
回到基准选择的问题。基准必须位于 low 的原因仅来自初始化:lt = low 且 i = low + 1 意味着 nums[low] 在循环中永远不会被指针 i 访问，
同时它又被默认划入等于区。若 nums[low] 的真实值与 pivot 不符，等于区从第一步起就被污染，不变式随之失效。
随机选基准与此并不冲突，只是随机得到的位置必须通过一次交换回到 low, 才能让初始化自洽。那一行 swap 的本质是将随机化与模板之间的接口对齐。
"""
def quick_sort_3way(nums):
def sort(low, high):
# 区间长度小于等于1时，结束递归
if high <= low:
return
# 选取当前区间第一个元素作为基准值
pivot = nums[low]
lt = low # 小于区的右边界
gt = high # 大于区的左边界
i = low + 1 # 当前扫描指针
"""
nums[low : lt-1] < pivot
nums[lt : i-1] == pivot
nums[i : gt] 未处理
nums[gt+1 : high] > pivot
"""
# 扫描到大于区间的左边界，表示全部元素已扫描
while i <= gt:
# 当前元素小于基准
if nums[i] < pivot:
nums[lt], nums[i] = nums[i], nums[lt]
lt += 1
i += 1
elif nums[i] > pivot:
nums[gt], nums[i] = nums[i], nums[gt]
gt -= 1
else:
i += 1
sort(low, lt - 1)
sort(gt + 1, high)
sort(0, len(nums) - 1)
nums = [200, 100 ,6, 10, 4, 10]
quick_sort_3way(nums)
nums
Out[ ]:
[4, 6, 10, 10, 100, 200]
In [ ]:
Copied!
import random
def quick_fast(nums):
def sort(low, high):
if high <= low:
return
pivot_idx = random.randint(low, high) # 从当前子区间随机选索引
nums[low], nums[pivot_idx] = nums[pivot_idx], nums[low] # 交换
pivot = nums[low]
lt = low
gt = high
i = low + 1
while i <= gt:
if nums[i] < pivot:
nums[lt], nums[i] = nums[i], nums[lt]
lt += 1
i += 1
elif nums[i] > pivot:
nums[gt], nums[i] = nums[i], nums[gt]
gt -= 1
else:
i += 1
sort(low, lt-1)
sort(gt+1, high)
sort(0, len(nums)-1)
nums = [200, 100 ,6, 10, 4, 10]
quick_fast(nums)
nums
import random
def quick_fast(nums):
def sort(low, high):
if high <= low:
return
pivot_idx = random.randint(low, high) # 从当前子区间随机选索引
nums[low], nums[pivot_idx] = nums[pivot_idx], nums[low] # 交换
pivot = nums[low]
lt = low
gt = high
i = low + 1
while i <= gt:
if nums[i] < pivot:
nums[lt], nums[i] = nums[i], nums[lt]
lt += 1
i += 1
elif nums[i] > pivot:
nums[gt], nums[i] = nums[i], nums[gt]
gt -= 1
else:
i += 1
sort(low, lt-1)
sort(gt+1, high)
sort(0, len(nums)-1)
nums = [200, 100 ,6, 10, 4, 10]
quick_fast(nums)
nums
Out[ ]:
[4, 6, 10, 10, 100, 200]
完整状态追踪：nums = [200, 100, 6, 10, 4, 10]¶
第一层：sort(0, 5)，pivot = 200¶
初始：[200, 100, 6, 10, 4, 10]
lt↑ gt↑
i↑
i=1: 100 < 200 → swap(lt=0, i=1) → [100, 200, 6, 10, 4, 10]，lt=1, i=2
i=2: 6 < 200 → swap(lt=1, i=2) → [100, 6,200, 10, 4, 10]，lt=2, i=3
i=3: 10 < 200 → swap(lt=2, i=3) → [100, 6, 10,200, 4, 10]，lt=3, i=4
i=4: 4 < 200 → swap(lt=3, i=4) → [100, 6, 10, 4,200, 10]，lt=4, i=5
i=5: 10 < 200 → swap(lt=4, i=5) → [100, 6, 10, 4, 10,200]，lt=5, i=6
结束：[100, 6, 10, 4, 10 | 200 |]
<200区间[0..4] ==区 >区(空)
递归：sort(0, 4) ／ sort(6, 5) 退出
第二层：sort(0, 4)，pivot = 100¶
初始：[100, 6, 10, 4, 10]
lt↑ gt↑
i↑
i=1: 6 < 100 → swap(lt=0, i=1) → [ 6,100, 10, 4, 10]，lt=1, i=2
i=2: 10 < 100 → swap(lt=1, i=2) → [ 6, 10,100, 4, 10]，lt=2, i=3
i=3: 4 < 100 → swap(lt=2, i=3) → [ 6, 10, 4,100, 10]，lt=3, i=4
i=4: 10 < 100 → swap(lt=3, i=4) → [ 6, 10, 4, 10,100]，lt=4, i=5
结束：[ 6, 10, 4, 10 | 100 |]
<100区间[0..3] ==区 >区(空)
递归：sort(0, 3) ／ sort(5, 4) 退出
第三层：sort(0, 3)，pivot = 6¶
初始：[ 6, 10, 4, 10]
lt↑ gt↑
i↑
i=1: 10 > 6 → swap(i=1, gt=3) → [ 6, 10, 4, 10]（值相同）, gt=2, i不动
i=1: 10 > 6 → swap(i=1, gt=2) → [ 6, 4, 10, 10]， gt=1, i不动
i=1: 4 < 6 → swap(lt=0, i=1) → [ 4, 6, 10, 10]，lt=1, i=2
结束：[ 4 | 6 | 10, 10]
<6区 ==区 >6区[2..3]
递归：sort(0, 0) 退出 ／ sort(2, 3)
第四层：sort(2, 3)，pivot = 10¶
初始：[10, 10]
lt↑ gt↑
i↑
i=3: 10 == 10 → i=4
结束：[| 10, 10 |]
<区(空) ==区 >区(空)
递归全部退出。
最终结果¶
[4, 6, 10, 10, 100, 200] ✓
为何 gt -= 1 时不能 i += 1¶
三个分支的逻辑不对称，根本原因在于换过来的元素是否已被检查过：
| 分支 | 换来的元素来自哪里 | 是否已检查 | 能否推进 i |
|---|---|---|---|
nums[i] < pivot |
nums[lt]，必然是 == pivot 的元素 |
已知，无需再判断 | ✅ i += 1 |
nums[i] == pivot |
无交换 | 当前元素已判断完毕 | ✅ i += 1 |
nums[i] > pivot |
nums[gt]，来自未处理区，值未知 |
未检查 | ❌ 不能推进 |
当 nums[i] > pivot 时，把 nums[gt] 换到位置 i 后，这个新来的元素可能小于、等于或大于 pivot，必须在下一轮重新判断。若此时贸然 i += 1，这个元素就被永远跳过，导致排序错误。
三路快排（非原地）¶
In [2]:
Copied!
import random
def quick_sort(nums):
if len(nums) <= 1:
return nums
pivot = random.choice(nums)
left = [x for x in nums if x < pivot]
middle = [x for x in nums if x == pivot]
right = [x for x in nums if x > pivot]
l_list = quick_sort(left)
r_list = quick_sort(right)
return l_list + middle + r_list
arr = [10, 7, 8, 9, 1, 20]
sorted_arr = quick_sort(arr)
print(f"原始数组: {arr}")
print(f"排序后数组: {sorted_arr}")
import random
def quick_sort(nums):
if len(nums) <= 1:
return nums
pivot = random.choice(nums)
left = [x for x in nums if x < pivot]
middle = [x for x in nums if x == pivot]
right = [x for x in nums if x > pivot]
l_list = quick_sort(left)
r_list = quick_sort(right)
return l_list + middle + r_list
arr = [10, 7, 8, 9, 1, 20]
sorted_arr = quick_sort(arr)
print(f"原始数组: {arr}")
print(f"排序后数组: {sorted_arr}")
原始数组: [10, 7, 8, 9, 1, 20] 排序后数组: [1, 7, 8, 9, 10, 20]
快速排序复杂度分析
一、每层的代价：O(n)
left = [x for x in arr if x < pivot]
right = [x for x in arr if x > pivot]
middle = [x for x in arr if x == pivot]
return quick_sort_basic(left) + middle + quick_sort_basic(right)
每次调用做两件事：三次列表推导式遍历 O(n)，以及列表拼接（Python + 会申请新内存逐元素复制）O(n)，合计单次调用代价为 O(n)。
二、时间复杂度：O(n log n)
时间复杂度的分析使用递归树横向分层模型，这是一种统计总工作量的思维工具，与实际执行顺序无关。
将递归树按层切割，观察每一层所有子问题处理的元素总数：
第 1 层：[10, 7, 8, 9, 1, 5] → 处理 6 个元素
第 2 层：[1, 5, 7] [9, 10] → 合计 6 个
第 3 层：[1] [5] [7] [9] [10] → 合计 6 个
每一层所有子问题的元素总数始终为 n，每层代价为 O(n)。pivot 随机选取时，平均每次将数组折半，递归树共 O(log n) 层。
$$T(n) = O(n) \times O(\log n) = O(n \log n)$$
最坏情况下（每次 pivot 取到边界值），树退化为一条链，深度变为 O(n)，总时间退化为 O(n²)。
三、空间复杂度：O(n)
这里需要区分分析模型与实际执行，两者回答的是不同问题。
实际执行：深度优先
Python 递归是深度优先执行的，并非同时处理某一整层：
quick_sort_basic([10,7,8,9,1,5])
└─ quick_sort_basic(left) ← 一路递归到底
└─ quick_sort_basic(left)
└─ ... 到 len<=1 返回
← 左边全部完成，才开始
└─ quick_sort_basic(right)
因此，任意时刻内存中存活的，只有从根到当前节点这一条路径上的临时列表，而非某一整层的所有列表。
内存峰值计算
这条路径上每层的列表大小平均折半：
$$n + \frac{n}{2} + \frac{n}{4} + \cdots + 1 = 2n = O(n)$$
因此内存峰值为 O(n)。
两种视角的对比
| 分析视角 | 回答的问题 | 结论 |
|---|---|---|
| 递归树横向分层 | 总计算量是多少？ | O(n log n) |
| 实际深度优先执行 | 内存峰值是多少？ | O(n) |
与原地快排对比： 原地快排不创建临时列表，空间仅来自调用栈本身，为 O(log n)。本实现额外创建了 left/middle/right 列表，使峰值从 O(log n) 升至 O(n)，是此实现相对于原地排序的主要代价。
四、汇总
| 平均情况 | 最坏情况 | |
|---|---|---|
| 时间复杂度 | O(n log n) | O(n²) |
| 空间复杂度（峰值） | O(n) | O(n) |
| 递归深度 | O(log n) | O(n) |
排序算法系统总结¶
一、排序算法核心评价指标¶
排序算法通常从三个维度评价：
| 指标 | 含义 |
|---|---|
| 时间复杂度 | 最好 / 平均 / 最坏情况 |
| 空间复杂度 | 是否需要额外辅助空间 |
| 稳定性 | 相同元素排序后相对顺序是否改变 |
补充面试常问指标：
| 指标 | 含义 |
|---|---|
| 是否原地排序 | 是否只使用 O(1) 额外空间（递归栈除外） |
| 是否基于比较 | 是否依赖元素大小比较 |
二、基础比较排序¶
基础排序是理解高级排序的基础。
排序思想发展路径：
冒泡排序
→ 选择排序
→ 插入排序
→ 希尔排序
2.1 冒泡排序（稳定原地排序）¶
思想：
相邻元素两两比较，将较大元素逐步交换到数组末尾。
标准实现：
def bubble_sort(nums):
n = len(nums)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
swapped = True
if not swapped:
break
复杂度：
| 指标 | 值 |
|---|---|
| 最好 | O(n) |
| 平均 | O(n²) |
| 最坏 | O(n²) |
| 空间 | O(1) |
| 稳定 | 是 |
| 是否原地 | 是 |
适用场景：
数据基本有序时效率较高
2.2 选择排序（原地但不稳定）¶
思想：
每轮选择未排序区最小元素放入已排序区末尾。
def selection_sort(nums):
n = len(nums)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if nums[j] < nums[min_idx]:
min_idx = j
nums[i], nums[min_idx] = nums[min_idx], nums[i]
关键特点：
交换次数最少（最多 n 次）
复杂度：
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(n²) |
| 空间复杂度 | O(1) |
| 稳定性 | 否 |
| 是否原地 | 是 |
注意：
选择排序不能减少比较次数，因此无法突破 O(n²)
2.3 插入排序（稳定原地排序）¶
思想：
维护一个已排序区，将新元素插入正确位置。
def insertion_sort(nums):
for i in range(1, len(nums)):
key = nums[i]
j = i - 1
while j >= 0 and nums[j] > key:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = key
复杂度：
| 指标 | 值 |
|---|---|
| 最好 | O(n) |
| 平均 | O(n²) |
| 最坏 | O(n²) |
| 空间 | O(1) |
| 稳定 | 是 |
| 是否原地 | 是 |
特点：
小规模数据排序最佳选择之一
工程排序的重要子模块
2.4 希尔排序（插入排序优化版）¶
思想：
通过 gap 分组降低移动距离。
def shell_sort(nums):
n = len(nums)
gap = n // 2
while gap > 0:
for i in range(gap, n):
key = nums[i]
j = i
while j >= gap and nums[j - gap] > key:
nums[j] = nums[j - gap]
j -= gap
nums[j] = key
gap //= 2
复杂度：
依赖 gap 序列：
| 指标 | 值 |
|---|---|
| 平均复杂度 | 优于 O(n²) |
| 最坏复杂度 | O(n²) |
| 空间复杂度 | O(1) |
| 稳定性 | 否 |
| 是否原地 | 是 |
说明：
不存在统一精确复杂度表达式
三、分治排序（核心面试重点）¶
包括：
归并排序
快速排序
3.1 归并排序（稳定但非原地）¶
思想：
递归拆分数组后再合并有序数组。
def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
复杂度：
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(n log n) |
| 空间复杂度 | O(n) |
| 稳定性 | 是 |
| 是否原地 | 否 |
说明：
标准实现需要辅助数组
链表排序优选归并排序
3.2 快速排序（最重要排序算法）¶
核心思想：
Partition 分区
小于 pivot
pivot
大于 pivot
递归排序左右区域
3.2.1 Lomuto 分区¶
简单直观版本
def lomuto_partition(nums, low, high):
pivot = nums[high]
i = low - 1
for j in range(low, high):
if nums[j] <= pivot:
i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1], nums[high] = nums[high], nums[i + 1]
return i + 1
def quick_sort_lomuto(nums, low, high):
if low < high:
pi = lomuto_partition(nums, low, high)
quick_sort_lomuto(nums, low, pi - 1)
quick_sort_lomuto(nums, pi + 1, high)
特点：
实现简单
交换次数较多
3.2.2 Hoare 分区¶
效率更高版本
def hoare_partition(nums, low, high):
pivot = nums[low]
i = low - 1
j = high + 1
while True:
i += 1
while nums[i] < pivot:
i += 1
j -= 1
while nums[j] > pivot:
j -= 1
if i >= j:
return j
nums[i], nums[j] = nums[j], nums[i]
def quick_sort_hoare(nums, low, high):
if low < high:
pi = hoare_partition(nums, low, high)
quick_sort_hoare(nums, low, pi)
quick_sort_hoare(nums, pi + 1, high)
特点：
交换次数更少
性能优于 Lomuto
3.2.3 三路快排（处理重复元素最优方案）¶
思想：
分为三段：
< pivot
= pivot
> pivot
def quick_sort_3way(nums, low, high):
if low >= high:
return
pivot = nums[low]
lt = low
gt = high
i = low + 1
while i <= gt:
if nums[i] < pivot:
nums[lt], nums[i] = nums[i], nums[lt]
lt += 1
i += 1
elif nums[i] > pivot:
nums[gt], nums[i] = nums[i], nums[gt]
gt -= 1
else:
i += 1
quick_sort_3way(nums, low, lt - 1)
quick_sort_3way(nums, gt + 1, high)
复杂度：
| 指标 | 值 |
|---|---|
| 平均复杂度 | O(n log n) |
| 最坏复杂度 | O(n²) |
| 空间复杂度 | O(log n) |
| 稳定性 | 否 |
| 是否原地 | 是 |
说明：
重复元素多时优势明显
快排工程优化策略总结¶
工程级优化包括：
随机 pivot
三数取中 pivot
三路切分
小数组使用插入排序
递归深度过大切换堆排序
形成：
introsort
pdqsort
四、堆排序（原地非稳定排序）¶
思想：
构建最大堆
依次交换堆顶元素
def heapify(nums, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and nums[l] > nums[largest]:
largest = l
if r < n and nums[r] > nums[largest]:
largest = r
if largest != i:
nums[i], nums[largest] = nums[largest], nums[i]
heapify(nums, n, largest)
def heap_sort(nums):
n = len(nums)
for i in range(n // 2 - 1, -1, -1):
heapify(nums, n, i)
for i in range(n - 1, 0, -1):
nums[0], nums[i] = nums[i], nums[0]
heapify(nums, i, 0)
复杂度：
| 指标 | 值 |
|---|---|
| 时间复杂度 | O(n log n) |
| 空间复杂度 | O(1) |
| 稳定性 | 否 |
| 是否原地 | 是 |
说明：
递归实现存在 O(log n) 调用栈空间
五、非比较排序¶
突破比较排序下界：
O(n log n)
5.1 计数排序¶
适用于：
整数范围有限场景
复杂度：
O(n + k)
稳定性：
取决于实现方式（可稳定）
空间：
O(k)
5.2 桶排序¶
思想：
分桶 + 桶内排序
复杂度：
平均：
O(n)
最坏：
O(n²)
稳定性：
取决于桶内排序方式
5.3 基数排序¶
思想：
按位排序
依赖稳定排序作为子过程
复杂度：
O(d(n+k))
稳定性：
可稳定（前提子排序稳定）
六、工程级排序算法¶
现代语言排序采用混合排序策略
Timsort¶
使用语言：
Python
Java
结构：
归并排序
+
插入排序
+
run 检测
特点：
稳定排序
利用局部有序性
Introsort¶
结构：
快速排序
+
堆排序
+
插入排序
特点：
防止退化
C++ STL 使用
pdqsort¶
结构：
三路快排
+
模式检测
+
堆排序 fallback
+
插入排序优化
特点：
现代最快通用排序之一
Rust / Go 使用
七、排序算法综合对比表¶
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定 | 原地 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 是 | 是 |
| 选择排序 | O(n²) | O(n²) | O(1) | 否 | 是 |
| 插入排序 | O(n²) | O(n²) | O(1) | 是 | 是 |
| 希尔排序 | 优于 O(n²) | O(n²) | O(1) | 否 | 是 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 是 | 否 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 否 | 是 |
| 三路快排 | O(n log n) | O(n²) | O(log n) | 否 | 是 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 否 | 是 |
| 计数排序 | O(n+k) | O(n+k) | O(k) | 可稳定 | 否 |
| 桶排序 | O(n) | O(n²) | O(n) | 可稳定 | 否 |
| 基数排序 | O(d(n+k)) | O(d(n+k)) | O(n+k) | 可稳定 | 否 |
八、面试建议排序算法掌握优先级¶
推荐掌握顺序：
第一优先级：
快速排序（三路）
归并排序
堆排序
第二优先级：
插入排序
希尔排序
第三优先级：
计数排序
桶排序
基数排序
工程级理解即可：
Timsort
Introsort
pdqsort
快速选择¶
你的判断也是对的。很多场景下我们只需要找到"第 k 大/小的元素"，而不需要整个数组有序。快速选择正是利用快速排序的分区思想，每次分区后根据 k 与各区间边界的位置关系，只递归进入目标所在的那一侧，丢弃另一侧，从而将平均时间复杂度从 O(n log n) 降至 O(n)。
常见算法中与"选择"相关的算法主要有三个：
| 算法 | 平均时间 | 最坏时间 | 特点 |
|---|---|---|---|
| 快速选择 | O(n) | O(n²) | 最常用，实现简单 |
| 堆选择 | O(n log k) | O(n log k) | 适合数据流、k 较小的场景 |
| BFPRT（中位数的中位数） | O(n) | O(n) | 理论最优，常数大，工程少用 |
面试和工程中绝大多数情况只需掌握快速选择即可。
核心思想对比快速排序¶
快速排序在分区后两侧都要递归，快速选择在分区后只递归目标所在的一侧。每次递归问题规模平均减半，因此总工作量是 n + n/2 + n/4 + ... ≈ 2n，即 O(n)。这是快速选择效率远高于先排序再取值的根本原因。
In [ ]:
Copied!
import random
def quick_select(nums, k):
"""
返回 nums 中第 k 小的元素（k 从 1 开始）
例如 k=1 返回最小值，k=len(nums) 返回最大值
"""
def select(low, high, k):
# 区间只有一个元素，直接返回
if low == high:
return nums[low]
# 随机选取 pivot，避免最坏情况
pivot_index = random.randint(low, high)
nums[low], nums[pivot_index] = nums[pivot_index], nums[low]
# 三路分区，与三路快排完全相同
pivot = nums[low]
lt = low # 小于区右边界
gt = high # 大于区左边界
i = low + 1 # 当前扫描指针
while i <= gt:
if nums[i] < pivot:
nums[lt], nums[i] = nums[i], nums[lt]
lt += 1
i += 1
elif nums[i] > pivot:
nums[gt], nums[i] = nums[i], nums[gt]
gt -= 1
# 注意：不能 i += 1，换来的元素未经检查
else:
i += 1
# 分区结束后：
# nums[low..lt-1] < pivot，共 lt - low 个
# nums[lt..gt] == pivot，共 gt - lt + 1 个
# nums[gt+1..high] > pivot
# 第1小的元素，按照升序排列，索引应该为0；因此k-1表示我们想要的元素在已经排好的序列中的索引
if k-1 <= lt-1:
# 第 k 小在小于区
return select(low, lt - 1, k)
elif k-1 >= gt + 1:
# 第 k 小在大于区
return select(gt + 1, high, k)
else:
# 第 k 小恰好在等于区，直接返回 pivot
return pivot
return select(0, len(nums) - 1, k)
# 如果想要找第K大，
# 则 return select(0, n - 1, n - k + 1)
# 第 k 大 = 第 (n-k+1) 小
# 测试
nums = [3, 2, 1, 5, 6, 4]
print(quick_select(nums, 2)) # 输出 2，第 2 小
print(quick_select(nums, 5)) # 输出 5，第 5 小
import random
def quick_select(nums, k):
"""
返回 nums 中第 k 小的元素（k 从 1 开始）
例如 k=1 返回最小值，k=len(nums) 返回最大值
"""
def select(low, high, k):
# 区间只有一个元素，直接返回
if low == high:
return nums[low]
# 随机选取 pivot，避免最坏情况
pivot_index = random.randint(low, high)
nums[low], nums[pivot_index] = nums[pivot_index], nums[low]
# 三路分区，与三路快排完全相同
pivot = nums[low]
lt = low # 小于区右边界
gt = high # 大于区左边界
i = low + 1 # 当前扫描指针
while i <= gt:
if nums[i] < pivot:
nums[lt], nums[i] = nums[i], nums[lt]
lt += 1
i += 1
elif nums[i] > pivot:
nums[gt], nums[i] = nums[i], nums[gt]
gt -= 1
# 注意：不能 i += 1，换来的元素未经检查
else:
i += 1
# 分区结束后：
# nums[low..lt-1] < pivot，共 lt - low 个
# nums[lt..gt] == pivot，共 gt - lt + 1 个
# nums[gt+1..high] > pivot
# 第1小的元素，按照升序排列，索引应该为0；因此k-1表示我们想要的元素在已经排好的序列中的索引
if k-1 <= lt-1:
# 第 k 小在小于区
return select(low, lt - 1, k)
elif k-1 >= gt + 1:
# 第 k 小在大于区
return select(gt + 1, high, k)
else:
# 第 k 小恰好在等于区，直接返回 pivot
return pivot
return select(0, len(nums) - 1, k)
# 如果想要找第K大，
# 则 return select(0, n - 1, n - k + 1)
# 第 k 大 = 第 (n-k+1) 小
# 测试
nums = [3, 2, 1, 5, 6, 4]
print(quick_select(nums, 2)) # 输出 2，第 2 小
print(quick_select(nums, 5)) # 输出 5，第 5 小
2 5
面试题 17.14. 最小K个数
设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
In [ ]:
Copied!
import random
from typing import List
class Solution:
def smallestK(self, nums: List[int], k: int) -> List[int]:
if k == 0:
return []
if k >= len(nums):
return nums[:]
def select(low, high):
if low >= high:
return
# 随机基准并交换到左端，保持三路划分的初始不变式
pivot_index = random.randint(low, high)
nums[low], nums[pivot_index] = nums[pivot_index], nums[low]
pivot = nums[low]
lt, gt, i = low, high, low + 1
while i <= gt:
if nums[i] < pivot:
nums[lt], nums[i] = nums[i], nums[lt]
lt += 1
i += 1
elif nums[i] > pivot:
nums[gt], nums[i] = nums[i], nums[gt]
gt -= 1
else:
i += 1
# 区间此时三分为：[low, lt-1] < pivot, [lt, gt] == pivot, [gt+1, high] > pivot
if k - 1 < lt-1:
select(low, lt - 1)
elif k - 1 > gt:
select(gt + 1, high)
# 若 lt-1 <= k-1 <= gt，前 k 个位置已是最小 k 个元素，无需再递归
select(0, len(nums) - 1)
return nums[:k]
nums = [3, 2, 1, 5, 6, 4]
k = 5
print(Solution().smallestK(nums, k))
import random
from typing import List
class Solution:
def smallestK(self, nums: List[int], k: int) -> List[int]:
if k == 0:
return []
if k >= len(nums):
return nums[:]
def select(low, high):
if low >= high:
return
# 随机基准并交换到左端，保持三路划分的初始不变式
pivot_index = random.randint(low, high)
nums[low], nums[pivot_index] = nums[pivot_index], nums[low]
pivot = nums[low]
lt, gt, i = low, high, low + 1
while i <= gt:
if nums[i] < pivot:
nums[lt], nums[i] = nums[i], nums[lt]
lt += 1
i += 1
elif nums[i] > pivot:
nums[gt], nums[i] = nums[i], nums[gt]
gt -= 1
else:
i += 1
# 区间此时三分为：[low, lt-1] < pivot, [lt, gt] == pivot, [gt+1, high] > pivot
if k - 1 < lt-1:
select(low, lt - 1)
elif k - 1 > gt:
select(gt + 1, high)
# 若 lt-1 <= k-1 <= gt，前 k 个位置已是最小 k 个元素，无需再递归
select(0, len(nums) - 1)
return nums[:k]
nums = [3, 2, 1, 5, 6, 4]
k = 5
print(Solution().smallestK(nums, k))
[1, 2, 3, 4, 5]
链表排序 vs 数组排序：存储结构决定算法选择¶
一、核心结论¶
| 存储结构 | 首选排序算法 | 核心操作 |
|---|---|---|
| 数组（顺序存储） | 快速排序 | Partition（分区） |
| 链表（链式存储） | 归并排序 | Merge（合并） |
一句话本质：随机访问 → 擅长分区；顺序访问 → 擅长合并。
二、为什么存储结构决定了算法选择¶
排序算法的效率，本质上取决于底层数据结构对关键操作的支持程度：
| 操作 | 数组 | 链表 |
|---|---|---|
| 随机访问第 i 个元素 | O(1)，直接下标 | O(n)，必须从头遍历 |
| 交换两个元素的值 | O(1)，nums[i], nums[j] = nums[j], nums[i] |
需要找到前驱节点，操作复杂 |
| 找到中点 | O(1)，mid = (lo + hi) // 2 |
O(n)，快慢指针 |
| 分割为两半 | 需要 copy 子数组或用下标标记范围 | O(1)，断开 next 指针即可 |
| 合并两个有序序列 | O(n) 额外空间，需要临时数组 | O(1) 额外空间，只改指针 |
由此推导出两个关键结论：
快排依赖「随机访问 + swap」：Partition 过程需要用下标定位元素并高效交换，数组天然支持，链表做不到高效 partition。
归并依赖「分割 + 合并」：链表断链 O(1)、合并只改指针不需额外空间，天然适合归并；反而数组归并需要 O(n) 辅助空间，这是数组归并排序的主要代价。
三、同为分治，「分」和「治」的侧重完全相反¶
快排和归并都是分治算法，但工作量的分布恰好相反：
| 维度 | 数组快排（Partition-based） | 链表归并（Merge-based） |
|---|---|---|
| 核心操作 | Partition（分区） | Merge（合并） |
| 「分」的过程 | 重：partition 是主要工作，遍历整个区间，把元素放到正确的一侧 | 轻：快慢指针找中点 + 断链，不关心元素大小 |
| 「治」的过程 | 轻：分完之后，左 < pivot < 右，递归子问题即可 | 重：merge 是主要工作，将两个有序链表合并为一个 |
| 有序性建立时机 | 分区时就建立了（pivot 归位） | 合并时才建立（逐个比较拼接） |
| 递归方向 | 自顶向下：先处理当前层（partition），再递归子问题 | 自底向上：先递归到单个节点，再逐层合并上来 |
用一个类比：
- 快排像分拣邮件：先按地区分好堆（partition），分好了自然就有序了
- 归并像合并牌堆：先把牌拆成一张一张，再两两合并成有序的牌堆（merge）
四、Merge——链表世界的核心基石¶
在数组排序的世界里，Partition 是万能钥匙：
- 快速排序 = Partition + 两侧递归
- 快速选择 = Partition + 单侧递归 → 平均 O(n) 找第 k 大
在链表排序的世界里，Merge（合并两个有序链表） 扮演同样的基石角色：
| 题目 | 做法 | Merge 的角色 |
|---|---|---|
| LC21 合并两个有序链表 | 双指针拉链法 | Merge 本身 |
| LC148 排序链表 | 快慢指针分割 + 递归 + 合并 | 归并排序的子过程 |
| LC23 合并 K 个升序链表 | 分治两两合并 | 每一轮的基础操作 |
三题递进关系：
LC21（合并两个有序链表）
↓ 作为子过程
LC148（排序链表）= 分割 + 递归 + LC21
↓ 扩展到 K 个
LC23（合并K个升序链表）= 分治两两调用 LC21
掌握了 merge 两个有序链表，就掌握了链表排序问题的基础。这和掌握了 partition 就掌握了数组排序 + 快速选择是同一个道理。
五、链表归并排序的空间优势¶
一个容易忽略的重要事实：同样是归并排序，在链表上比在数组上更省空间。
数组归并排序的 merge 步骤需要一个临时数组来暂存合并结果，因此空间复杂度为 O(n)。但链表的 merge 只需要修改 next 指针，不需要任何额外存储。
| 算法 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|
| 数组快排（三路） | O(n log n) | O(log n) 递归栈 | 数组排序首选，原地排序 |
| 数组归并排序 | O(n log n) | O(n) 辅助数组 | 稳定但费空间 |
| 链表归并排序 | O(n log n) | O(log n) 递归栈 | 链表排序首选，合并无额外空间 |
| 链表快排 | O(n log n) | O(log n) | 可行但 partition 效率低，不推荐 |
关键洞察：归并排序在数组上的最大劣势（O(n) 额外空间）在链表上被完全消除了，因为链表合并只是改指针。这就是为什么归并排序在数组世界中输给快排，但在链表世界中成为首选。
六、综合对比总结¶
| 维度 | 数组排序 | 链表排序 |
|---|---|---|
| 首选算法 | 快速排序（三路快排） | 归并排序 |
| 核心操作 | Partition（分区） | Merge（合并） |
| 适合原因 | 随机访问 O(1)，swap 高效 | 断链 O(1)，合并不需额外空间 |
| 不适合的算法 | 归并排序（需 O(n) 额外空间） | 快速排序（无法高效 partition） |
| 分治侧重 | 分重治轻（partition 建立有序性） | 分轻治重（merge 建立有序性） |
| 核心操作复用 | partition → 快排、快速选择 | merge → 排序链表、合并 K 个链表 |
| 最优时间复杂度 | O(n log n) | O(n log n) |
| 最优空间复杂度 | O(log n)（原地快排） | O(log n)（递归栈，合并本身 O(1)） |
链表归并排序代码实现（LC148 排序链表）¶
链表归并排序分三步，与数组归并排序对应但操作方式完全不同：
| 步骤 | 数组归并排序 | 链表归并排序 |
|---|---|---|
| 分割 | mid = (lo+hi)//2，O(1) 算出下标 |
快慢指针找中点 + 断链，O(n) |
| 递归 | 递归排序左右子数组 | 递归排序左右子链表 |
| 合并 | 需要 O(n) 辅助数组 | 只改指针，O(1) 额外空间 |
In [ ]:
Copied!
from typing import Optional
class ListNode:
def __init__(self, val: int = 0, next: 'ListNode | None' = None):
self.val = val
self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 递归终止：空链表或单节点，已经有序
if not head or not head.next:
return head
# --- 1. 分割：快慢指针找中点，断链 ---
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next # 右半部分的头
slow.next = None # 断开链表
# --- 2. 递归：分别排序左右两半 ---
sorted_left = self.sortList(head)
sorted_right = self.sortList(mid)
# --- 3. 合并：将两个有序链表合并 ---
return self._merge(sorted_left, sorted_right)
def _merge(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# 合并两个有序链表（LC21），链表排序的核心基石
cur = dummy = ListNode(0)
while l1 and l2:
if l1.val <= l2.val: # <= 保证稳定性
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next
# --- 测试 ---
head = ListNode(4, ListNode(2, ListNode(1, ListNode(3))))
solver = Solution()
sorted_head = solver.sortList(head)
# 遍历打印
node = sorted_head
vals = []
while node:
vals.append(str(node.val))
node = node.next
print(" -> ".join(vals)) # 1 -> 2 -> 3 -> 4
from typing import Optional
class ListNode:
def __init__(self, val: int = 0, next: 'ListNode | None' = None):
self.val = val
self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 递归终止：空链表或单节点，已经有序
if not head or not head.next:
return head
# --- 1. 分割：快慢指针找中点，断链 ---
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next # 右半部分的头
slow.next = None # 断开链表
# --- 2. 递归：分别排序左右两半 ---
sorted_left = self.sortList(head)
sorted_right = self.sortList(mid)
# --- 3. 合并：将两个有序链表合并 ---
return self._merge(sorted_left, sorted_right)
def _merge(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# 合并两个有序链表（LC21），链表排序的核心基石
cur = dummy = ListNode(0)
while l1 and l2:
if l1.val <= l2.val: # <= 保证稳定性
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next
# --- 测试 ---
head = ListNode(4, ListNode(2, ListNode(1, ListNode(3))))
solver = Solution()
sorted_head = solver.sortList(head)
# 遍历打印
node = sorted_head
vals = []
while node:
vals.append(str(node.val))
node = node.next
print(" -> ".join(vals)) # 1 -> 2 -> 3 -> 4
链表归并排序复杂度分析¶
一、时间复杂度：O(n log n)¶
与数组归并排序相同，使用递归树分层模型分析：
每层的工作量：O(n)
每一层递归做两件事：
- 找中点：快慢指针遍历链表，O(n)
- 合并：两个有序链表合并，O(n)
合计单层代价为 O(n)。
递归树的层数：O(log n)
每次将链表从中点断开，长度减半，递归树共 O(log n) 层。
第 1 层：[4, 2, 1, 3] → 找中点 + 合并，处理 4 个节点
第 2 层：[4, 2] [1, 3] → 合计处理 4 个节点
第 3 层：[4] [2] [1] [3] → 合计处理 4 个节点（单节点直接返回）
每层处理的节点总数始终为 n，共 log n 层：
$$T(n) = O(n) \times O(\log n) = O(n \log n)$$
二、空间复杂度：O(log n)¶
这是链表归并排序相比数组归并排序的核心优势。
数组归并排序的空间代价：
- merge 步骤需要临时数组存放合并结果 → O(n) 额外空间
- 递归栈 → O(log n)
- 总计：O(n)
链表归并排序的空间代价：
- merge 步骤只修改
next指针 → O(1) 额外空间 - 递归栈 → O(log n)
- 总计：O(log n)
空间对比：
数组归并：O(n) 辅助数组 + O(log n) 递归栈 = O(n)
链表归并：O(1) 指针操作 + O(log n) 递归栈 = O(log n) ✓ 链表胜出
归并排序在数组上的最大劣势（O(n) 额外空间）在链表上被完全消除了。这正是链表排序首选归并、而非快排的核心原因。
三、关键细节解析¶
为什么快慢指针初始化为 slow, fast = head, head.next？
这保证了对于偶数长度链表，slow 停在左半部分的最后一个节点，从而均匀切分：
链表：1 → 2 → 3 → 4
↑
slow（停在 2）
mid = slow.next = 3
左半：1 → 2 右半：3 → 4 ✓ 均匀
如果 fast = head（而非 head.next）：
链表：1 → 2 → 3 → 4
↑
slow（停在 3）
左半：1 → 2 → 3 右半：4 ✗ 不均匀
不均匀切分不会导致错误，但会降低效率（类似快排选到极端 pivot），最坏情况递归深度退化为 O(n)。
为什么 merge 中用 <= 而非 <？
<= 保证稳定性：当 l1 和 l2 有相等元素时，优先取左半部分的节点，保持它们在原链表中的相对顺序。稳定性是归并排序相对于快排的天然优势，不应该丢掉。
四、汇总¶
| 指标 | 链表归并排序 | 数组归并排序 | 数组快排（三路） |
|---|---|---|---|
| 时间复杂度 | O(n log n) | O(n log n) | O(n log n) 平均 |
| 空间复杂度 | O(log n) | O(n) | O(log n) |
| 稳定性 | 是 | 是 | 否 |
| 核心操作 | Merge | Merge | Partition |
| 适用场景 | 链表排序首选 | 需要稳定排序时 | 数组排序首选 |