本文深入探讨了python快速排序算法的正确实现，重点分析了在分区（partitioning）过程中常见的逻辑错误，如交换操作的缩进问题、支点（pivot）的最终位置确定以及递归调用边界的设置。通过详细的代码示例和修正，旨在帮助开发者理解并构建一个健壮、高效的快速排序算法。
快速排序算法概述
快速排序（Quick Sort）是一种高效的、基于分治策略的排序算法。其核心思想是：
- 选择支点（Pivot）：从待排序数组中选择一个元素作为“支点”（pivot）。
- 分区（Partition）：将数组中所有小于支点的元素移到支点左边，所有大于支点的元素移到支点右边。这个操作完成后，支点就处于其最终的有序位置。
- 递归排序：对支点左右两边的子数组分别递归地执行快速排序。
当子数组只有一个元素或为空时，递归停止。
常见的快速排序实现陷阱与修正
在实现快速排序时，尤其是在分区逻辑部分，开发者常常会遇到一些细微但关键的错误，导致排序结果不正确。下面我们将结合一个常见的错误示例，分析并给出正确的实现。
原始代码中的问题分析
立即学习“Python免费学习笔记（深入）”；
考虑以下一个尝试实现快速排序的Python代码片段：
class QuickSort:
def quickSort(self, list, low, high):
if (low >= high):
return
else:
leftPointer = low
rightPointer = high
pivot = list[high]
while (leftPointer < rightPointer):
while (leftPointer < rightPointer and list[leftPointer] < pivot):
leftPointer += 1
while (leftPointer < rightPointer and list[rightPointer] > pivot):
rightPointer -= 1
list[leftPointer], list[rightPointer] = list[rightPointer], list[leftPointer] # 问题1：缩进错误
list[high], list[leftPointer] = list[leftPointer], list[high] # 问题2：支点放置逻辑错误
self.quickSort(list, low, rightPointer - 1) # 问题3：递归边界错误
self.quickSort(list, rightPointer + 1, high) # 问题3：递归边界错误
return list这段代码存在以下几个主要问题：
- 交换操作的缩进错误：list[leftPointer], list[rightPointer] = list[rightPointer], list[leftPointer] 这行代码的缩进不正确，它应该在 while (leftPointer < rightPointer) 循环内部执行，以在每次找到需要交换的元素时进行交换。而原始代码将其放在循环外部，导致在整个分区过程中只执行一次交换。
- 支点放置逻辑错误：list[high], list[leftPointer] = list[leftPointer], list[high] 这行旨在将支点放到其最终位置。然而，当 leftPointer 最终指向的元素小于支点时，这个交换会导致支点被错误放置。正确的逻辑需要确保支点最终位于所有小于它的元素之后、所有大于它的元素之前。
- 递归调用边界错误：在分区完成后，rightPointer 并不总是支点最终的位置。正确的递归调用应该以支点最终的位置为界限，将数组分成两个子部分。在正确的实现中，leftPointer 最终会指向支点的新位置。
正确的快速排序实现
为了解决上述问题，我们需要对分区逻辑和支点放置策略进行调整。下面是修正后的Python快速排序实现：
class QuickSort:
def quickSort(self, input_list, low, high):
# 1. 基本情况：如果子数组只有一个元素或为空，则已排序
if low >= high:
return
# 优化：处理两个元素的子数组且已排序的情况
# 实际操作中，这个优化可以合并到low >= high的判断中，或者直接依赖后续逻辑
# if high - low == 1 and input_list[low] <= input_list[high]:
# return
# 2. 选择支点：这里选择最后一个元素作为支点
pivot = input_list[high]
# 初始化左右指针
# leftPointer从low开始寻找大于pivot的元素
# rightPointer从high-1开始寻找小于pivot的元素（不包括pivot本身）
leftPointer = low
rightPointer = high - 1
# 3. 分区过程
# 当leftPointer小于等于rightPointer时，继续进行分区
while leftPointer <= rightPointer:
# 找到第一个大于或等于pivot的元素
while leftPointer <= rightPointer and input_list[leftPointer] < pivot:
leftPointer += 1
# 找到第一个小于或等于pivot的元素
while leftPointer <= rightPointer and input_list[rightPointer] > pivot:
rightPointer -= 1
# 如果指针尚未交叉，则交换元素
if leftPointer <= rightPointer:
input_list[leftPointer], input_list[rightPointer] = input_list[rightPointer], input_list[leftPointer]
# 交换后，移动指针继续寻找
leftPointer += 1
rightPointer -= 1
# 4. 将支点放到其最终位置
# 循环结束后，leftPointer指向第一个大于等于pivot的元素的位置
# 将pivot（原位于high）与leftPointer指向的元素交换
# 这样，pivot就位于所有小于它的元素之后，所有大于它的元素之前
input_list[leftPointer], input_list[high] = input_list[high], input_list[leftPointer]
# 5. 递归排序左右子数组
# 支点现在位于leftPointer位置，所以递归范围是(low, leftPointer-1) 和 (leftPointer+1, high)
self.quickSort(input_list, low, leftPointer - 1)
self.quickSort(input_list, leftPointer + 1, high)
return input_list
修正后的关键点解释：
- 支点选择与指针初始化：我们仍然选择 input_list[high] 作为支点。leftPointer 从 low 开始，rightPointer 从 high - 1 开始，这是因为 high 位置是支点，不需要参与初始的比较交换。
-
分区循环 (while leftPointer <= rightPointer)：
- 内部的 while 循环分别寻找左侧第一个大于等于支点的元素和右侧第一个小于等于支点的元素。
- 当找到这样的两个元素且 leftPointer <= rightPointer 时，进行交换。
- 交换后，leftPointer 和 rightPointer 都向前或向后移动一位，继续寻找。
- 支点最终放置：在主 while 循环结束后，leftPointer 会指向支点最终应该放置的位置（即所有小于支点的元素都在其左侧，所有大于支点的元素都在其右侧）。我们将原支点 (input_list[high]) 与 input_list[leftPointer] 进行交换，从而将支点放置到其最终的有序位置。
- 递归调用边界：由于支点已经放置在 leftPointer 位置，并且它已经处于最终的有序状态，因此在递归调用时，我们将数组分为 (low, leftPointer - 1) 和 (leftPointer + 1, high) 两个子数组，不包括支点本身。
示例代码与测试
为了验证修正后的快速排序算法的正确性，我们可以使用不同的测试用例：
# 实例化快速排序类
quick = QuickSort()
# 测试用例1：普通乱序数组
list1 = [50, 49, 19, 4, 9]
print(f"原始数组: {list1}, 排序后: {quick.quickSort(list1, 0, len(list1) - 1)}") # 预期: [4, 9, 19, 49, 50]
# 测试用例2：已排序数组
list2 = [1, 2, 3, 4, 5]
print(f"原始数组: {list2}, 排序后: {quick.quickSort(list2, 0, len(list2) - 1)}") # 预期: [1, 2, 3, 4, 5]
# 测试用例3：逆序数组
list3 = [4, 3, 2, 1]
print(f"原始数组: {list3}, 排序后: {quick.quickSort(list3, 0, len(list3) - 1)}") # 预期: [1, 2, 3, 4]
# 测试用例4：包含重复元素的数组
list4 = [8, 6, 7, 5, 3, 0, 9, 7, 1]
print(f"原始数组: {list4}, 排序后: {quick.quickSort(list4, 0, len(list4) - 1)}") # 预期: [0, 1, 3, 5, 6, 7, 7, 8, 9]
# 测试用例5：空数组或单元素数组
list5 = []
print(f"原始数组: {list5}, 排序后: {quick.quickSort(list5, 0, len(list5) - 1) if list5 else []}") # 预期: []
list6 = [42]
print(f"原始数组: {list6}, 排序后: {quick.quickSort(list6, 0, len(list6) - 1)}") # 预期: [42]注意事项与总结
- 支点选择：本教程中选择最后一个元素作为支点。其他策略包括选择第一个元素、中间元素或随机选择。不同的支点选择策略对算法的性能有影响，尤其是在处理特定输入（如已排序或逆序数组）时。
- 性能：快速排序在平均情况下的时间复杂度为 O(n log n)，但在最坏情况下（例如，每次都选择最大或最小元素作为支点，且数组已排序或逆序）会退化到 O(n^2)。随机化支点选择可以有效降低遇到最坏情况的概率。
- 空间复杂度：快速排序是一种原地排序算法，其空间复杂度主要取决于递归栈的深度，平均为 O(log n)，最坏情况下为 O(n)。
- 稳定性：快速排序是一种不稳定的排序算法，即相等元素的相对顺序在排序后可能会改变。
通过理解和掌握正确的快速排序分区逻辑，开发者可以避免常见的实现错误，构建出高效且可靠的排序解决方案。核心在于确保支点在每次分区后都能准确地放置在其最终位置，并且递归调用能够正确地处理左右子数组。
