# 快速排序实战：用Python手写算法并优化性能（附完整代码） 如果你已经写过几行Python代码，大概率用过`sorted()`函数或者列表的`.sort()`方法。它们背后用的就是Timsort，一种混合了归并和插入排序的算法。但今天我们不聊这些现成的轮子，而是回到算法学习的本源——**快速排序**。为什么在众多排序算法中，快速排序依然被无数工程师和面试官青睐？因为它不仅仅是一个算法，更是一种**分治思想的经典体现**，其核心的“挖坑填数”或“双指针”技巧，在处理实际问题时有着惊人的通用性。 对于Python开发者而言，理解快速排序的深层逻辑，远不止是为了通过技术面试。它能帮你建立对递归、时间复杂度分析、算法优化策略的直觉。更重要的是，当你面对一个需要自定义排序逻辑的复杂数据结构，或者需要在内存受限环境下处理海量数据时，手写一个高效、可控的排序算法会成为你的秘密武器。这篇文章就是为你准备的，无论你是想夯实算法基础，还是想在项目中实现一个特定场景下的高性能排序模块，我们都会从最朴素的实现开始，一步步拆解、优化，直到写出一个能在生产环境中经得起考验的快速排序版本。 ## 1. 从零开始：理解快速排序的核心思想 快速排序的精髓，用一句话概括就是：**挑一个“裁判”（基准数），让小的站左边，大的站右边，然后递归处理左右两队**。这个“分而治之”的策略听起来简单，但实现起来却有几个关键细节决定了算法的效率和正确性。 我们先抛开代码，想象一个生动的场景：你有一叠杂乱无章的员工工牌，需要按工号从小到大排好。快速排序的做法是，随机抽出一张工牌（比如工号50），然后以它为基准，把所有工号小于50的放到左边桌子，大于50的放到右边桌子。接下来，你对左边那堆和右边那堆分别重复同样的操作——每堆里再随机抽一张，再分两小堆。直到每一堆都只剩下一张或零张工牌时，整个序列自然就有序了。 这个过程揭示了快速排序的三个核心步骤： 1. **分区（Partition）**：这是算法的引擎。选定一个基准值后，重新排列数组，使得基准值左边的元素都不大于它，右边的元素都不小于它。此时，基准值就位于它最终排序后应该处在的位置。 2. **递归（Recursion）**：对基准值左右两侧新形成的子数组，独立地递归调用快速排序函数。 3. **基准选择（Pivot Selection）**：选择哪个元素作为基准值，会极大地影响递归的深度和效率，这是我们后续性能优化的重点。 一个常见的误解是认为快速排序不稳定。是的，标准的快速排序实现是**不稳定排序**。这意味着如果有两个工号相同的员工（比如都是50），在排序后他们的相对位置可能会发生变化。这在某些需要保持原始顺序的场景下需要注意。 ## 2. 手把手实现第一个Python版本 理论说再多，不如动手写一行代码。我们先实现一个最直观、最容易理解的版本——Lomuto分区方案。这个方案逻辑清晰，虽然在某些情况下效率不是最高，但对于理解算法流程是完美的起点。 ```python def quick_sort_basic(arr): """快速排序基础版（Lomuto分区法）""" if len(arr) <= 1: return arr pivot = arr[-1] # 简单选择最后一个元素作为基准 left = [x for x in arr[:-1] if x <= pivot] right = [x for x in arr[:-1] if x > pivot] return quick_sort_basic(left) + [pivot] + quick_sort_basic(right) # 测试一下 if __name__ == "__main__": test_array = [30, 40, 60, 10, 20, 50] sorted_array = quick_sort_basic(test_array) print(f"原始数组: {test_array}") print(f"排序结果: {sorted_array}") ``` 这个版本非常“Pythonic”，利用了列表推导式，可读性极高。它清晰地展示了分治的过程：创建两个新列表`left`和`right`，然后递归拼接。但是，它有几个明显的性能问题： * **空间消耗大**：每一层递归都创建了新的列表，空间复杂度是O(n log n)到O(n)，不是原地排序。 * **基准选择固定**：总是选最后一个元素，如果数组已经有序或逆序，会导致最坏情况。 > 注意：这个版本适合教学和理解，但在处理大规模数据或追求极致性能时，我们需要更优的实现。 接下来，我们实现经典的**原地排序、双指针遍历的Hoare分区法**。这是大多数算法教材中介绍的版本，也是性能优化的基础。 ```python def quick_sort_inplace(arr, low=0, high=None): """快速排序原地排序版（Hoare分区法）""" if high is None: high = len(arr) - 1 if low >= high: return # 分区操作，返回基准值的最终位置 pi = partition(arr, low, high) # 递归排序左右两部分 quick_sort_inplace(arr, low, pi - 1) quick_sort_inplace(arr, pi + 1, high) def partition(arr, low, high): """ 分区函数。 选择arr[high]作为基准(pivot)，重新排列数组， 使得小于等于基准的元素在左，大于基准的在右。 返回基准值的最终索引。 """ pivot = arr[high] # 选择最后一个元素为基准 i = low - 1 # 指向小于基准区域的最后一个元素 for j in range(low, high): # 如果当前元素小于等于基准 if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] # 交换 # 将基准值放到正确位置 arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1 ``` 这个`partition`函数是算法的核心。变量`i`维护着一个“边界”：索引`i`及其左边的所有元素都小于等于基准值。指针`j`从左向右扫描，每当找到一个小于等于基准值的元素，就把它交换到`i`的右边，然后`i`向右移动一位。循环结束后，`i+1`的位置就是基准值应该插入的地方。 让我们用一个小数组来手动模拟一下，假设`arr = [30, 40, 60, 10, 20, 50]`，`pivot=50`（最后一个元素）： 1. 初始：`i = -1`, `j`从0开始。 2. `j=0`: `arr[0]=30 <= 50`，`i`变为0，交换`arr[0]`和`arr[0]`（自身），数组不变。 3. `j=1`: `40 <= 50`，`i=1`，交换`arr[1]`和`arr[1]`，不变。 4. `j=2`: `60 > 50`，不做交换。 5. `j=3`: `10 <= 50`，`i=2`，交换`arr[2]`(60)和`arr[3]`(10)，数组变为`[30, 40, 10, 60, 20, 50]`。 6. `j=4`: `20 <= 50`，`i=3`，交换`arr[3]`(60)和`arr[4]`(20)，数组变为`[30, 40, 10, 20, 60, 50]`。 7. 循环结束，交换`arr[i+1]`(即`arr[4]`=60)和`arr[high]`(50)，得到`[30, 40, 10, 20, 50, 60]`。此时，`pivot=50`位于索引4，左边元素都小于等于它，右边元素都大于它。 ## 3. 性能瓶颈分析与优化策略 一个朴素的快速排序实现，在面对某些“恶意”数据时，性能会急剧下降。理解这些瓶颈，是进行优化的前提。 **最坏情况时间复杂度O(n²)是怎么发生的？** 当每次分区操作选取的基准值都是当前子数组的最大值或最小值时，快速排序就退化成了冒泡排序。例如，对一个已经升序排列的数组`[1,2,3,4,5]`，如果总是选择最后一个元素作为基准，那么每次分区只能将数组规模减少1（基准值被放到最右边），递归树会退化成一条深度为n的链。 | 递归调用 | 待排序子数组 | 选择的基准 | 分区结果（左 | 基准 | 右） | 问题 | | :--- | :--- | :--- | :--- | :--- | | 第1层 | `[1,2,3,4,5]` | 5 | `[1,2,3,4]` | `5` | `[]` | 右子树为空 | | 第2层 | `[1,2,3,4]` | 4 | `[1,2,3]` | `4` | `[]` | 右子树为空 | | ... | ... | ... | ... | ... | ... | ... | 递归深度达到n，每层分区需要O(n)时间，总时间就是O(n²)。除了已排序数组，逆序数组、所有元素都相同的数组也会导致类似问题。 **递归深度过深与栈溢出** Python默认的递归深度限制（通常为1000层）对于排序百万级别的数据是不够的。即使没有达到限制，过深的递归调用也会带来不小的函数调用开销。 **针对小数组的效率问题** 当子数组规模变得很小时（比如少于10个元素），快速排序的递归和分区开销就显得不那么划算了。此时，像**插入排序**这样简单且对小数组高效的算法，反而更有优势。 基于以上分析，我们的优化工具箱里应该有以下几件利器： 1. **随机化基准选择**：打破输入数据的特定模式，将最坏情况概率降到极低。 2. **三数取中法**：一种更稳定的基准选择策略，避免随机数的偶然性。 3. **尾递归优化与迭代**：减少递归深度，防止栈溢出。 4. **混合排序策略**：对于小数组，切换到插入排序。 5. **三路快速排序**：高效处理大量重复元素的数组。 ## 4. 实战优化：打造高性能快速排序 现在，让我们把上述优化策略整合起来，写一个工业级的快速排序函数。 ### 4.1 优化基准选择：随机化与三数取中 单纯的随机化已经能极大改善平均性能。我们结合“三数取中”法，即取子数组首、尾、中间三个元素的中位数作为基准，这通常能选出一个非常好的分割点。 ```python import random def choose_pivot(arr, low, high): """选择基准值：使用三数取中法""" mid = (low + high) // 2 # 对arr[low], arr[mid], arr[high]进行排序，取中间值 candidates = [(arr[low], low), (arr[mid], mid), (arr[high], high)] candidates.sort(key=lambda x: x[0]) return candidates[1][1] # 返回中位数的索引 def partition_optimized(arr, low, high): """优化的分区函数，使用三数取中法选择基准""" pivot_idx = choose_pivot(arr, low, high) # 将选中的基准交换到末尾，方便后续分区逻辑（兼容之前的partition写法） arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx] pivot = arr[high] i = low - 1 for j in range(low, high): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] return i + 1 ``` ### 4.2 应对重复元素：三路快速排序 当数组中存在大量重复元素时，标准快速排序仍会对其进行不必要的递归分割。三路快速排序将数组分为三部分：小于基准、等于基准、大于基准。这样，一次分区后，所有等于基准的元素都已就位，只需递归处理小于和大于的部分。 ```python def quick_sort_3way(arr, low=0, high=None): """三路快速排序，高效处理重复元素""" if high is None: high = len(arr) - 1 if low >= high: return # 随机选择基准并交换到开头 rand_idx = random.randint(low, high) arr[low], arr[rand_idx] = arr[rand_idx], arr[low] pivot = arr[low] lt = low # arr[low+1..lt] < pivot gt = high # arr[gt+1..high] > pivot i = low + 1 # arr[lt+1..i-1] == pivot while i <= gt: if arr[i] < pivot: arr[lt], arr[i] = arr[i], arr[lt] lt += 1 i += 1 elif arr[i] > pivot: arr[i], arr[gt] = arr[gt], arr[i] gt -= 1 else: # arr[i] == pivot i += 1 # 现在 arr[low..lt-1] < pivot, arr[lt..gt] == pivot, arr[gt+1..high] > pivot quick_sort_3way(arr, low, lt - 1) quick_sort_3way(arr, gt + 1, high) ``` ### 4.3 混合策略：递归转迭代与插入排序 对于小数组，我们使用插入排序。同时，为了避免递归过深，我们可以用**栈来模拟递归过程**，实现迭代版的快速排序。 ```python def insertion_sort(arr, low, high): """对arr[low:high+1]进行插入排序""" 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 def quick_sort_final(arr): """最终优化版：迭代+三数取中+小数组插入排序""" if len(arr) <= 1: return arr # 使用栈模拟递归调用 stack = [(0, len(arr) - 1)] while stack: low, high = stack.pop() # 小数组使用插入排序 if high - low < 16: # 阈值可调整，通常15-20 insertion_sort(arr, low, high) continue # 三数取中选择基准 pivot_idx = choose_pivot(arr, low, high) arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx] pivot = arr[high] # 标准分区操作 i = low - 1 for j in range(low, high): if arr[j] <= pivot: i += 1 arr[i], arr[j] = arr[j], arr[i] arr[i + 1], arr[high] = arr[high], arr[i + 1] pi = i + 1 # 将需要处理的子数组范围压入栈，先处理较小的子数组有助于降低栈深度 left_size = pi - 1 - low right_size = high - (pi + 1) # 总是先处理较小的部分 if left_size < right_size: if low < pi - 1: stack.append((low, pi - 1)) if pi + 1 < high: stack.append((pi + 1, high)) else: if pi + 1 < high: stack.append((pi + 1, high)) if low < pi - 1: stack.append((low, pi - 1)) ``` 这个`quick_sort_final`版本集成了我们讨论的大部分优化： * **迭代替代递归**：使用显式栈，完全避免了递归深度限制。 * **小数组优化**：当子数组长度小于16时，切换为插入排序。 * **智能基准选择**：使用`choose_pivot`函数进行三数取中。 * **栈深度优化**：总是优先处理较小的子数组，这能保证栈的最大深度保持在O(log n)。 ## 5. 性能对比与场景选择 我们写了这么多版本，到底哪个更快？这严重依赖于输入数据的特点。下面这个简单的性能对比表格，可以帮你根据实际情况做出选择： | 排序版本 | 时间复杂度（平均） | 时间复杂度（最坏） | 空间复杂度 | 适用场景 | 不适用场景 | | :--- | :--- | :--- | :--- | :--- | :--- | | **基础列表推导版** | O(n log n) | O(n²) | O(n log 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(log n) | **生产环境通用**、大数据量、递归深度可能成问题时 | 对稳定性有严格要求 | > 提示：在实际项目中，Python内置的`sorted`和`list.sort()`（Timsort）在绝大多数情况下都是最优选择。它们经过高度优化，是稳定的，并且对多种数据模式（部分有序、包含重复项）都有很好的适应性。手写快速排序的价值在于**学习算法思想**、**应对特殊需求**（如自定义复杂对象的排序键、非比较排序、外部排序等），或者在**算法竞赛/面试**中展示你的功底。 为了更直观地感受优化效果，我们可以用`timeit`模块做一个简单的性能测试（以排序10万个随机整数为例）： ```python import timeit import random setup_code = """ import random from __main__ import quick_sort_inplace, quick_sort_3way, quick_sort_final arr = [random.randint(0, 10000) for _ in range(100000)] arr1 = arr.copy() arr2 = arr.copy() arr3 = arr.copy() """ print("原地排序版耗时:", timeit.timeit('quick_sort_inplace(arr1)', setup=setup_code, number=1)) print("三路快排版耗时:", timeit.timeit('quick_sort_3way(arr2)', setup=setup_code, number=1)) print("最终优化版耗时:", timeit.timeit('quick_sort_final(arr3)', setup=setup_code, number=1)) ``` 在我的测试环境中，对于包含大量重复元素的随机数组，三路快排和最终优化版通常会显示出优势。而对于完全随机的数据，它们的差异可能不大，但最终优化版因其迭代特性和小数组优化，通常更加稳健。 最后，别忘了边界测试。尝试用这些函数排序一个已经有序的万级列表，你会发现未优化基准选择的`quick_sort_inplace`会慢得惊人，而采用了随机化或三数取中的版本则依然迅速。这正体现了算法优化中“抵御最坏情况”的重要性。