【Python面试通关手记】3.6 数据结构与算法：排序算法全解

排序是计算机科学中最基础、最核心的算法之一。在面试中，排序算法几乎是必考内容，不仅要求能手写实现，还需要深入理解每种算法的原理、复杂度、稳定性以及适用场景。本章将带你系统性地掌握 8 种经典排序算法，并深入剖析 Python 内置排序机制 Timsort 的设计精髓。

1. 排序算法总览

在进入具体算法之前，先建立整体认知。排序算法可以从以下几个维度进行分类。

按时间复杂度分类：

按稳定性分类：

• 稳定排序：相等元素的相对顺序在排序后保持不变。包括：冒泡排序、插入排序、归并排序、计数排序、基数排序。
• 不稳定排序：不保证相等元素相对顺序。包括：选择排序、希尔排序、快速排序、堆排序。

按排序方式分类：

• 比较排序：通过元素间的比较决定顺序。任何比较排序在最坏情况下至少需要 Ω(n log n) 次比较。
• 非比较排序：不通过比较，而是利用元素本身的特殊性质。如计数排序、基数排序、桶排序。

2. 冒泡排序 (Bubble Sort)

2.1 基本原理

冒泡排序的核心思想是反复遍历序列，依次比较相邻两个元素，如果顺序错误就交换它们。每一轮遍历都会把当前未排序部分中的"最大元素"像气泡一样"冒"到序列末尾。

2.2 算法步骤

2.3 Python 实现

def bubble_sort(arr):
"""冒泡排序 – 带优化版本"""
n = len(arr)
for i in range(n – 1):
# 优化：如果某一轮没有交换，说明已经有序
swapped = False
for j in range(n – 1 – i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr

优化说明：

• 外层 i 表示已经排好的元素个数，每次内层循环范围缩小。
• swapped 标志位：如果某轮没有任何交换，说明数组已经有序，可以直接终止外层循环。
• 这是最常见的优化版本，能够在数组已经有序的情况下达到 O(n) 的最佳时间复杂度。

2.4 复杂度与稳定性

2.5 何时使用

• 几乎不用在实际生产环境中，因为效率太低。
• 适合教学演示排序的基本概念。
• 适合数据量非常小（n < 50）且代码简洁性优先的场景。

2.6 面试官追问

问：如果数组已经有序，冒泡排序的时间复杂度是多少？

答：如果使用带标志位的优化版本，最好情况下数组已经有序，第一遍遍历没有任何交换触发，标志位 swapped 在遍历结束后为 False，外层循环直接 break。此时只需一次遍历，时间复杂度为 O(n)。如果没有优化标志位，即使有序也会执行 n-1 轮遍历，仍然是 O(n²)。

3. 选择排序 (Selection Sort)

3.1 基本原理

选择排序的思路非常直观：每次从未排序部分中找到最小元素，放到已排序部分的末尾。它将序列分为已排序区（前面）和未排序区（后面），不断从未排序区挑选最小值延伸到已排序区。

3.2 算法步骤

3.3 Python 实现

def selection_sort(arr):
"""选择排序"""
n = len(arr)
for i in range(n – 1):
# 找到未排序部分的最小值索引
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# 将最小值放到已排序部分的末尾
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr

3.4 复杂度与稳定性

为什么不稳定？ 举个例子：[5a, 8, 5b, 2]，第一轮找到最小值 2，与 5a 交换，得到 [2, 8, 5b, 5a]。原本在前的 5a 被换到了后面，5b 反而在前，所以 5a 和 5b 的相对顺序被破坏。

3.5 何时使用

• 适合数据量很小且交换操作成本很低的场景。
• 当交换次数是性能瓶颈时，选择排序有优势（最多 n-1 次交换，而冒泡排序最坏需要 n²/2 次）。
• 不适合大规模数据。

3.6 面试官追问

问：为什么选择排序比冒泡排序更差？

答：不一定更差。选择排序的交换次数是 O(n)，而冒泡排序的交换次数是 O(n²)。如果交换元素的开销远大于比较开销（比如排序大对象），选择排序可能比冒泡排序更快。但两者在比较次数上都是 O(n²)。平均而言，插入排序比这两者都要好。

4. 插入排序 (Insertion Sort)

4.1 基本原理

插入排序的工作方式就像整理手中的扑克牌。将序列分为已排序区和未排序区，每次从未排序区取出第一个元素，插入到已排序区的正确位置。

4.2 算法步骤

4.3 Python 实现

def insertion_sort(arr):
"""插入排序"""
n = len(arr)
for i in range(1, n):
key = arr[i] # 当前要插入的元素
j = i – 1 # 已排序部分的最后一个索引
# 从后向前查找插入位置，同时将元素后移
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key # 插入到正确位置
return arr

4.4 复杂度与稳定性

4.5 插入排序的优势

虽然插入排序的平均时间复杂度也是 O(n²)，但它有几个独特的优势：

这些特性使插入排序成为许多高级排序算法中重要的子例程。Timsort 和 快速排序的优化版本会在子数组很小时切换到插入排序。

4.6 面试官追问

问：插入排序和冒泡排序有何异同？

答：两者都是 O(n²) 的稳定排序，且对有序数据都有 O(n) 的最佳表现。区别在于：插入排序通过"后移腾位"来插入元素，比较次数更少；冒泡排序通过"两两交换"来冒泡元素，交换次数更多。在实际测试中，插入排序通常比冒泡排序快 2-3 倍。

5. 希尔排序 (Shell Sort)

5.1 基本原理

希尔排序是插入排序的改进版本，也被称为"缩小增量排序"。它通过将序列分成若干子序列分别进行插入排序，让元素快速接近其最终位置，从而减少插入排序中的大量移动操作。

核心思想：先宏观调整，再微观精细排序。

5.2 算法步骤

5.3 Python 实现

def shell_sort(arr):
"""希尔排序 – 使用希尔增量 (gap = n//2, n//4, …, 1)"""
n = len(arr)
gap = n // 2 # 初始增量

while gap > 0:
# 对每个子序列进行插入排序
for i in range(gap, n):
temp = arr[i]
j = i
# 在子序列中进行插入排序
while j >= gap and arr[j – gap] > temp:
arr[j] = arr[j – gap]
j -= gap
arr[j] = temp
gap //= 2 # 缩小增量

return arr

5.4 增量序列的选择

增量序列的选择对希尔排序的性能至关重要：

使用 Hibbard 或 Sedgewick 增量的希尔排序性能显著优于简单的 n/2 递减。

5.5 复杂度与稳定性

为什么希尔排序不稳定？ 因为在不同的子序列中，相等的元素可能被分配到不同组，导致相对位置改变。例如，两个相等的 5 在不同组，后面的 5 可能会通过分组插入跑到前面。

5.6 何时使用

• 中等规模数据（n < 5000）且对空间要求严格的场景。
• 嵌入式系统或内存受限的环境。
• 学习理解"宏观调整 + 微观精细"的分治思想。

5.7 面试官追问

问：为什么希尔排序比插入排序快？

答：插入排序每次只能将元素移动一位，效率低下。希尔排序通过较大增量允许元素"跳跃式移动"，大幅减少了移动次数。假设数组长度为 1000，一个在末尾的最小元素，插入排序需要移动 999 次，而希尔排序第一次（gap=500）只需移动 2 次就能将其放到前半部分。

6. 归并排序 (Merge Sort)

6.1 基本原理

归并排序是分治策略的经典应用。它将数组不断分成两半，分别排序后再合并，利用"合并两个有序数组"这一基础操作来完成全局排序。

核心思想：分而治之，合而为一。

6.2 算法步骤

6.3 Python 实现

def merge_sort(arr):
"""归并排序 – 递归版本，返回新数组"""
if len(arr) <= 1:
return arr

mid = len(arr) // 2
left = merge_sort(arr[:mid]) # 递归排序左半
right = merge_sort(arr[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

原地归并排序（节省空间）：

def merge_sort_inplace(arr, left=0, right=None):
"""归并排序 – 原地版本"""
if right is None:
right = len(arr)

if right – left <= 1:
return

mid = (left + right) // 2
merge_sort_inplace(arr, left, mid)
merge_sort_inplace(arr, mid, right)
merge_inplace(arr, left, mid, right)

def merge_inplace(arr, left, mid, right):
"""原地合并两个有序区间 [left, mid) 和 [mid, right)"""
left_part = arr[left:mid] # 需要 O(n) 辅助空间
right_part = arr[mid:right]

i = j = 0
k = left
while i < len(left_part) and j < len(right_part):
if left_part[i] <= right_part[j]:
arr[k] = left_part[i]
i += 1
else:
arr[k] = right_part[j]
j += 1
k += 1

# 复制剩余元素
while i < len(left_part):
arr[k] = left_part[i]
i += 1
k += 1
while j < len(right_part):
arr[k] = right_part[j]
j += 1
k += 1

注意：虽然称为"原地"版本，但 Python 中切片创建了新列表，仍然需要 O(n) 辅助空间。真正的原地归并排序非常复杂，面试中不常见。

6.4 复杂度与稳定性

6.5 何时使用

• 需要稳定排序的场景。
• 对数据的有序程度没有先验知识，要求最坏情况下也能保证 O(n log n)。
• 外部排序（数据量太大无法全部加载到内存），归并排序的 IO 模式非常友好。
• 链表排序（无需额外空间，因为链表不需要随机访问，归并排序对链表非常高效）。

6.6 链表上的归并排序

def merge_sort_linked(head):
"""链表归并排序（面试高频）"""
if not head or not head.next:
return head

# 快慢指针找中点
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next

# 断开链表
mid = slow.next
slow.next = None

left = merge_sort_linked(head)
right = merge_sort_linked(mid)
return merge_linked(left, right)

def merge_linked(l1, l2):
"""合并两个有序链表"""
dummy = ListNode(0)
cur = dummy
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 or l2
return dummy.next

6.7 面试官追问

问：归并排序的空间复杂度能否优化到 O(1)？

答：理论上存在 O(1) 空间的归并排序，通过"原地归并"技术（如手摇算法 – rotation algorithm），但其实现非常复杂，常数因子很大，实际用途有限。还有一个折中方案是"自底向上的迭代归并"，虽然也是 O(n) 空间，但避免了递归的栈开销。

7. 快速排序 (Quick Sort)

7.1 基本原理

快速排序是实践中最快的比较排序算法，也是面试中的"必考王者"。它同样基于分治策略，但不同于归并排序的"先分后合"，快排是"先分后治"——它先选一个基准元素（pivot），将数组分为小于 pivot 和大于 pivot 的两部分，再递归排序左右两边。

7.2 算法步骤

7.3 Python 实现

def quick_sort(arr, low=0, high=None):
"""快速排序 – Lomuto 分区方案"""
if high is None:
high = len(arr) – 1

if low < high:
# 分区，返回 pivot 的最终位置
pi = partition_lomuto(arr, low, high)
quick_sort(arr, low, pi – 1) # 递归排序左半
quick_sort(arr, pi + 1, high) # 递归排序右半
return arr

def partition_lomuto(arr, low, high):
"""Lomuto 分区方案 – 选最后一个元素为 pivot"""
pivot = arr[high]
i = low – 1 # i 指向小于 pivot 的区域的末尾

for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]

# 将 pivot 放到正确位置
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1

更高效的 Hoare 分区方案：

def quick_sort_hoare(arr, low=0, high=None):
"""快速排序 – Hoare 分区方案（更高效，更常用）"""
if high is None:
high = len(arr) – 1

if low < high:
pi = partition_hoare(arr, low, high)
# 注意：Hoare 分区返回的 pivot_index 是分界点
# 左右都包含 pivot_index
quick_sort_hoare(arr, low, pi)
quick_sort_hoare(arr, pi + 1, high)
return arr

def partition_hoare(arr, low, high):
"""Hoare 分区方案 – 选第一个元素为 pivot"""
pivot = arr[low]
i = low – 1
j = high + 1

while True:
# 从左向右找第一个大于等于 pivot 的元素
i += 1
while arr[i] < pivot:
i += 1
# 从右向左找第一个小于等于 pivot 的元素
j -= 1
while arr[j] > pivot:
j -= 1
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]

7.4 基准（pivot）选择策略

基准选择对快排的性能影响巨大，以下是几种常见策略：

三数取中实现：

def median_of_three(arr, low, high):
"""三数取中：将 arr[low], arr[mid], arr[high] 的中位数放到 high-1 位置"""
mid = (low + high) // 2
# 先确保 arr[low] <= arr[mid]
if arr[low] > arr[mid]:
arr[low], arr[mid] = arr[mid], arr[low]
# 确保 arr[low] <= arr[high]
if arr[low] > arr[high]:
arr[low], arr[high] = arr[high], arr[low]
# 确保 arr[mid] <= arr[high]
if arr[mid] > arr[high]:
arr[mid], arr[high] = arr[high], arr[mid]
# 此时 arr[mid] 是三个数的中位数
# 将其放到 high-1 位置，方便分区
arr[mid], arr[high – 1] = arr[high – 1], arr[mid]
return arr[high – 1]

7.5 复杂度与稳定性

7.6 优化技巧

def quick_sort_optimized(arr, low=0, high=None):
"""优化版快速排序"""
if high is None:
high = len(arr) – 1

# 优化1：小数组使用插入排序
if high – low < 10:
insertion_sort_range(arr, low, high)
return

# 优化2：三数取中选择 pivot
mid = (low + high) // 2
# 将三个候选排序
if arr[low] > arr[mid]:
arr[low], arr[mid] = arr[mid], arr[low]
if arr[low] > arr[high]:
arr[low], arr[high] = arr[high], arr[low]
if arr[mid] > arr[high]:
arr[mid], arr[high] = arr[high], arr[mid]
# 将中位数放到 high-1 作为 pivot
arr[mid], arr[high – 1] = arr[high – 1], arr[mid]

pi = partition_hoare(arr, low, high)

# 优化3：先递归小的子数组，再处理大的
# 这样递归栈深度最多 O(log n)
if pi – low < high – pi:
quick_sort_optimized(arr, low, pi)
low = pi + 1
else:
quick_sort_optimized(arr, pi + 1, high)
high = pi

def insertion_sort_range(arr, low, high):
"""对 arr[low..high] 进行插入排序"""
for i in range(low + 1, high + 1):
key = arr[i]
j = i – 1
while j >= low and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key

7.7 快速选择算法（Quick Select）

快速排序的分区思想还有一个非常重要的应用——快速选择算法，用于在 O(n) 平均时间内找到数组中第 k 大的元素。

def quick_select(arr, k):
"""快速选择 – 找第 k 小的元素（k 从 0 开始）"""
low, high = 0, len(arr) – 1

while low <= high:
pi = partition_lomuto(arr, low, high)
if pi == k:
return arr[pi]
elif pi < k:
low = pi + 1
else:
high = pi – 1
return –1

# 使用快速选择找中位数
def find_median(arr):
n = len(arr)
mid = n // 2
if n % 2 == 1:
return quick_select(arr, mid)
else:
# 偶数长度，返回中间两个的平均值
left = quick_select(arr, mid – 1)
right = quick_select(arr, mid)
return (left + right) / 2

7.8 面试官追问

问：快排在最坏情况下是 O(n²)，为什么它被称为"快速"排序？

答：在随机数据上，快排的期望时间复杂度是 O(n log n)，且常数因子非常小（约为归并排序的 1/2 到 1/3），数据在内存中的访问模式对缓存友好。加上随机化 pivot 或三数取中策略后，最坏情况几乎不可能发生。实践中，快排是通用场景下最快的比较排序算法。

问：Lomuto 分区和 Hoare 分区有什么不同？

答：Lomuto 分区实现简单直观，但当数组中有大量重复元素时性能下降严重（每次交换操作包括 pivot 本身）。Hoare 分区从两端向中间扫描，交换次数更少，通常比 Lomuto 快 2-3 倍。但 Hoare 分区的边界条件更复杂，返回的索引不一定是 pivot 的最终位置。

8. 堆排序 (Heap Sort)

8.1 基本原理

堆排序利用二叉堆这种数据结构来完成排序。它首先将数组构建成一个最大堆，然后反复将堆顶元素（最大值）与末尾元素交换，并调整堆结构，逐步得到有序序列。

8.2 关键概念

• 完全二叉树：堆是一种完全二叉树，可以用数组高效表示。
• 最大堆：每个节点的值都大于等于其子节点的值，堆顶是最大值。
• 父子关系：对于数组索引 i（从 0 开始），left_child = 2*i + 1，right_child = 2*i + 2，parent = (i-1)//2。

8.3 算法步骤

8.4 Python 实现

def heapify(arr, n, i):
"""
下沉操作：将以 i 为根的子树调整为最大堆
n 是堆的大小（数组有效长度）
"""
largest = i # 初始时假设根节点是最大值
left = 2 * i + 1 # 左子节点
right = 2 * i + 2 # 右子节点

# 如果左子节点存在且大于根节点
if left < n and arr[left] > arr[largest]:
largest = left
# 如果右子节点存在且大于当前最大值
if right < n and arr[right] > arr[largest]:
largest = right

# 如果最大值不是根节点，交换并继续下沉
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)

def heap_sort(arr):
"""堆排序"""
n = len(arr)

# 1. 建堆：从最后一个非叶子节点开始，自下而上构建最大堆
for i in range(n // 2 – 1, –1, –1):
heapify(arr, n, i)

# 2. 排序：逐个将堆顶元素（最大值）放到末尾
for i in range(n – 1, 0, –1):
arr[0], arr[i] = arr[i], arr[0] # 将堆顶放到末尾
heapify(arr, i, 0) # 对前 i 个元素调整堆

return arr

8.5 建堆过程详解

建堆的 for i in range(n // 2 – 1, -1, -1) 这段代码是关键。为什么从 n//2 – 1 开始？

• 在完全二叉树中，最后一个非叶子节点的索引是 n//2 – 1。
• 从该节点开始向前遍历，确保每个子树在调整前其左右子树已经满足堆性质。
• 这样建堆的时间复杂度是 O(n)，而不是 O(n log n)。

8.6 复杂度与稳定性

为什么堆排序不稳定？ 举例：[5a, 5b, 3] 建堆后 5a 和 5b 分别在堆顶和堆底，排序过程中 5a 被换到数组末尾后，堆调整时可能将 5b 换到 5a 之前，破坏相对顺序。

8.7 堆排序 vs 快速排序

面试常问：虽然堆排序的时间复杂度看起来更优（最坏也是 O(n log n)），但实际运行速度通常比快排慢，原因是堆排序对内存的访问模式不连续（每次 heapify 需要访问 2i+1 和 2i+2，造成大量 cache miss），且建堆和排序过程中比较次数也更多。

8.8 面试官追问

问：堆排序和优先队列有什么关系？

答：堆是优先队列最经典的实现方式。堆排序本质上就是"不断地从优先队列中取出最大元素"的过程。当我们需要动态维护数据流中的最大/最小元素时（如实时 Top K），应该使用堆结构的优先队列，而不是每次排序。在 Python 中，heapq 模块提供了最小堆的实现。

问：如何用堆解决 Top K 问题？

答：维护一个大小为 K 的最小堆，遍历数据时，如果当前元素大于堆顶，则弹出堆顶并压入当前元素。遍历结束后，堆中的 K 个元素就是最大的 K 个。时间复杂度为 O(n log K)，非常适合处理海量数据。

9. 计数排序 (Counting Sort)

9.1 基本原理

计数排序是一种非比较排序，它通过统计每个元素出现的次数，然后根据计数信息将元素放到正确位置。它不是通过比较来决定元素顺序，而是利用元素值的范围有限这一特性。

9.2 算法步骤

9.3 Python 实现

def counting_sort(arr):
"""计数排序 – 稳定版本"""
if not arr:
return arr

# 1. 找出最大最小值，确定范围
max_val = max(arr)
min_val = min(arr)
range_of_elements = max_val – min_val + 1

# 2. 统计频率
count = [0] * range_of_elements
for num in arr:
count[num – min_val] += 1

# 3. 累加计数 -> 每个元素在输出数组中的位置
for i in range(1, len(count)):
count[i] += count[i – 1]

# 4. 反向遍历原数组，构建有序结果
output = [0] * len(arr)
for num in reversed(arr):
idx = num – min_val
count[idx] -= 1
output[count[idx]] = num

return output

简化版（非稳定，但更易读）：

def counting_sort_simple(arr):
"""计数排序 – 简化版"""
if not arr:
return arr

max_val = max(arr)
count = [0] * (max_val + 1)

# 统计频率
for num in arr:
count[num] += 1

# 根据计数直接展开
result = []
for val in range(len(count)):
result.extend([val] * count[val])

return result

9.4 复杂度与稳定性

9.5 何时使用

• 元素取值范围 k 远小于数据量 n 时非常高效。例如，对 10 万个 0-100 之间的整数排序。
• 时间复杂度为 O(n + k)，当 n 和 k 同数量级时相当于 O(n)。
• 不适合：元素范围很大（如浮点数、取值范围巨大的整数）。

9.6 基数排序

基数排序是计数排序的扩展，它依次按个位、十位、百位等数字位进行排序，通常使用计数排序作为子过程。

def radix_sort(arr):
"""基数排序 – LSD（最低位优先）"""
if not arr:
return arr

# 确定最大位数
max_val = max(arr)
exp = 1 # 当前处理的位：1->个位, 10->十位, …

while max_val // exp > 0:
counting_sort_by_digit(arr, exp)
exp *= 10

return arr

def counting_sort_by_digit(arr, exp):
"""按指定位数进行计数排序"""
n = len(arr)
output = [0] * n
count = [0] * 10 # 十进制，0-9

# 统计当前位上的数字出现次数
for num in arr:
digit = (num // exp) % 10
count[digit] += 1

# 累加计数
for i in range(1, 10):
count[i] += count[i – 1]

# 反向填充
for num in reversed(arr):
digit = (num // exp) % 10
count[digit] -= 1
output[count[digit]] = num

# 复制回原数组
for i in range(n):
arr[i] = output[i]

基数排序的复杂度：

10. 算法对比总表

注：冒泡排序的最佳 O(n) 需要优化版本（带 swapped 标志位）。

11. 经典面试题精讲

11.1 Top K 问题

问题：从 N 个元素中找出最大的 K 个元素。

解法一：全局排序（粗暴但简单）

def top_k_sort(nums, k):
"""排序后取前 K 个，O(n log n)"""
return sorted(nums, reverse=True)[:k]

解法二：最小堆（最优解，适合海量数据）

import heapq

def top_k_heap(nums, k):
"""最小堆解法，O(n log k)"""
if k <= 0:
return []
# 维护一个大小为 k 的最小堆
min_heap = []
for num in nums:
if len(min_heap) < k:
heapq.heappush(min_heap, num)
elif num > min_heap[0]:
heapq.heapreplace(min_heap, num)
return min_heap # 堆中的 K 个元素即为最大 K 个

解法三：快速选择（O(n) 平均时间）

def top_k_quick_select(nums, k):
"""快速选择，O(n) 平均时间"""
if k <= 0:
return []

def partition(l, r):
pivot = nums[r]
i = l – 1
for j in range(l, r):
if nums[j] >= pivot: # 找大的，降序
i += 1
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1], nums[r] = nums[r], nums[i + 1]
return i + 1

l, r = 0, len(nums) – 1
while l <= r:
p = partition(l, r)
if p == k – 1:
return nums[:k]
elif p < k – 1:
l = p + 1
else:
r = p – 1
return nums[:k]

11.2 寻找中位数

问题：找出一个未排序数组的中位数。

def find_median_quick(nums):
"""使用快速选择找中位数 – O(n) 平均时间"""
n = len(nums)
mid = n // 2

# 复制数组，避免修改原数组
arr = nums.copy()

if n % 2 == 1:
return quick_select(arr, mid)
else:
left = quick_select(arr, mid – 1)
right = quick_select(arr, mid)
return (left + right) / 2

进阶版：数据流中的中位数（实时插入）

class MedianFinder:
"""数据流中位数 – 双堆法"""

def __init__(self):
self.small = [] # 最大堆（存较小的半部分，用负数模拟）
self.large = [] # 最小堆（存较大的半部分）

def addNum(self, num: int) –> None:
# 先插入 small（最大堆）
heapq.heappush(self.small, –num)
# 确保 small 中的所有元素都 <= large 中的元素
if self.small and self.large and (–self.small[0]) > self.large[0]:
val = –heapq.heappop(self.small)
heapq.heappush(self.large, val)
# 平衡两个堆的大小
if len(self.small) > len(self.large) + 1:
val = –heapq.heappop(self.small)
heapq.heappush(self.large, val)
elif len(self.large) > len(self.small):
val = heapq.heappop(self.large)
heapq.heappush(self.small, –val)

def findMedian(self) –> float:
if len(self.small) > len(self.large):
return –self.small[0]
return (–self.small[0] + self.large[0]) / 2.0

11.3 颜色分类（荷兰国旗问题）

问题：给定一个包含红色（0）、白色（1）和蓝色（2）的数组，将其按红-白-蓝顺序排序。要求原地排序，一次遍历。

def sort_colors(nums):
"""
荷兰国旗问题 – 三指针法
[0, 0, …, 0, 1, 1, …, 1, 2, 2, …, 2]
^ ^ ^ ^
| | | |
left cur right len-1

left: 0 区域的右边界（下个 0 应该放的位置）
cur: 当前扫描指针
right: 2 区域的左边界
"""
left = 0 # 0 的插入位置
cur = 0 # 当前扫描位置
right = len(nums) – 1 # 2 的插入位置

while cur <= right:
if nums[cur] == 0:
# 遇到 0，交换到 left 位置
nums[left], nums[cur] = nums[cur], nums[left]
left += 1
cur += 1 # left 位置的元素不可能是 2，所以可以前进
elif nums[cur] == 2:
# 遇到 2，交换到 right 位置
nums[right], nums[cur] = nums[cur], nums[right]
right -= 1
# cur 不自增，因为交换过来的元素需要重新判断
else: # nums[cur] == 1
cur += 1

return nums

11.4 合并 K 个有序数组

问题：给定 K 个有序数组，将它们合并成一个有序数组。

解法一：两两合并（分治归并）

def merge_k_sorted_divide(lists):
"""分治合并 – O(N log K)，N 为总元素数"""
if not lists:
return []
if len(lists) == 1:
return lists[0]

mid = len(lists) // 2
left = merge_k_sorted_divide(lists[:mid])
right = merge_k_sorted_divide(lists[mid:])
return merge(left, right) # 使用前面定义的 merge 函数

解法二：最小堆（最优）

def merge_k_sorted_heap(lists):
"""最小堆合并 K 个有序数组 – O(N log K)"""
import heapq

# 优先队列中存入 (值, 数组索引, 元素索引)
heap = []
for i, arr in enumerate(lists):
if arr: # 非空数组
heapq.heappush(heap, (arr[0], i, 0))

result = []
while heap:
val, arr_idx, elem_idx = heapq.heappop(heap)
result.append(val)
# 如果该数组还有下一个元素，压入堆
if elem_idx + 1 < len(lists[arr_idx]):
next_val = lists[arr_idx][elem_idx + 1]
heapq.heappush(heap, (next_val, arr_idx, elem_idx + 1))

return result

12. Python 的 Timsort —— list.sort() 和 sorted()

12.1 Timsort 是什么

Timsort 是 Python 内置的排序算法，由 Tim Peters 在 2001 年设计，用于 Python 的 list.sort() 和 sorted() 函数。它是归并排序和插入排序的混合体，经过高度优化，被广泛认为是当前最好的通用排序算法之一。

注：Java 的 Arrays.sort()、Android SDK、GNU Octave 等也使用了 Timsort 或其变体。

12.2 核心设计理念

Timsort 的设计基于一个关键的观察：现实世界中的数据往往包含有序的子序列（称为 run）。Timsort 充分利用了这一点。

12.3 工作机制详解

Phase 1: 识别和扩展 run

# 伪代码描述 Timsort 的核心逻辑
MIN_MERGE = 32 # 或 64，随 Python 版本略有不同

def timsort(arr):
n = len(arr)

# 小数组直接用插入排序
if n < MIN_MERGE:
insertion_sort(arr)
return arr

# 找出所有自然 run
runs = []
i = 0
while i < n:
run_start = i
# 判断是升序还是降序
if i + 1 < n and arr[i] > arr[i + 1]:
# 降序 run，先收集再反转
while i + 1 < n and arr[i] >= arr[i + 1]:
i += 1
# 反转成升序
reverse(arr, run_start, i)
else:
# 升序 run
while i + 1 < n and arr[i] <= arr[i + 1]:
i += 1
run_end = i

# 如果 run 太短，用插入排序扩展到 min_run 长度
if run_end – run_start + 1 < MIN_MERGE:
extend_bound = min(run_start + MIN_MERGE – 1, n – 1)
insertion_sort_range(arr, run_start, extend_bound)
i = extend_bound

runs.append((run_start, i))
i += 1

# Phase 2: 合并 run（使用栈来管理合并顺序）
# …

平衡合并策略：Timsort 维护一个运行栈，确保栈顶三个 run 的长度满足：

len(stack[-3]) > len(stack[-2]) + len(stack[-1])
len(stack[-2]) > len(stack[-1])

这个条件保证了合并的平衡性，使整体复杂度保持在 O(n log n)。

合并优化 – Galloping（飞奔模式）

当合并两个 run 时，如果一个 run 中连续多个元素都大于另一个 run 的当前元素，Timsort 会切换到"飞奔模式"：使用二分查找一次性找到一批元素的位置，而不是逐个比较。这能显著提升对有序或近似有序数据的处理速度。

12.4 Timsort 的复杂度与特点

12.5 为什么 Timsort 这么好

12.6 面试官追问

问：Python 中 list.sort() 和 sorted() 的区别是什么？

答：两者都使用 Timsort。list.sort() 是 in-place 排序，直接修改原列表，返回 None。sorted() 是内置函数，接受任何可迭代对象，返回一个新的排序列表，不修改原输入。

问：Python 的 sort 是稳定的吗？

答：是的，Python 的 list.sort() 和 sorted() 都保证稳定排序。这在按多个条件排序时非常有用，例如先按年龄排序，再按姓名排序，可以级联排序实现多级排序。

问：你能手写一个简化的 Timsort 吗？

答：面试中能写出核心概念即可：识别自然 run，使用插入排序扩展小 run，然后用归并的思想合并 run。完整实现需要几百行代码，面试不会要求，但理解其设计思想（利用自然有序性、插入排序+归并排序的混合、galloping 模式）非常重要。

13. 总结与复习要点

面试前必须掌握的

常见考点

熟练度自检清单

• 能快速手写 5 种以上排序算法
• 能推导出每种算法的时间复杂度
• 能区分稳定和不稳定算法并解释原因
• 能回答"什么时候该用哪种排序"
• 能讲清楚 Timsort 的设计原理
• 能解决 Top K、荷兰国旗、中位数等经典问题

本章涵盖了面试中所有常见的排序算法。熟练掌握这些基础算法不仅是为了应对面试，更是理解高级数据结构与算法的基础。排序的思想——分治、比较、交换、插入——贯穿了整个计算机科学。