本文旨在帮助开发者理解和修复Python中快速排序算法的实现问题。通过分析常见的错误原因，提供修正后的代码示例，并详细解释代码逻辑和关键步骤，确保快速排序算法能够正确地对数组进行排序。文章还包含测试用例，帮助读者验证代码的正确性，并提供了一些注意事项，以避免在实际应用中出现类似的问题。
快速排序是一种高效的排序算法，它采用分而治之的策略来对数组进行排序。然而，在实现快速排序时，容易出现一些错误，导致排序结果不正确。本文将分析一个常见的快速排序实现问题，并提供修正后的代码，以及详细的解释和测试用例。
问题分析
原始代码中存在几个关键问题，导致排序结果不正确：
立即学习“Python免费学习笔记（深入）”；
- 指针移动逻辑错误：while 循环中，当 leftPointer 和 rightPointer 相遇时，没有正确处理 pivot 的位置。这会导致 pivot 没有被放置到正确的位置上。
- 递归调用范围错误：递归调用 quickSort 时，范围的指定可能存在问题，导致某些元素没有被正确排序。
- 缺少对特殊情况的处理：对于长度为2且已经有序的数组，没有进行特殊处理。
修正后的代码
class QuickSort:
def quickSort(self, input_list, low, high):
# 处理长度为2且已排序的特殊情况
if high - low == 1 and input_list[low] <= input_list[high]:
return
if (low >= high):
return
else:
leftPointer = low
rightPointer = high - 1
pivot = input_list[high]
while (leftPointer < rightPointer):
while (leftPointer < rightPointer and input_list[leftPointer] < pivot):
leftPointer += 1
while (leftPointer < rightPointer and input_list[rightPointer] > pivot):
rightPointer -= 1
input_list[leftPointer], input_list[rightPointer] = input_list[rightPointer], input_list[leftPointer]
# 确保 pivot 放置在正确的位置
if input_list[leftPointer] > input_list[high]:
input_list[leftPointer], input_list[high] = input_list[high], input_list[leftPointer]
# 递归调用，对左右子数组进行排序
self.quickSort(input_list, low, leftPointer)
self.quickSort(input_list, leftPointer+1, high)
return input_list
# 测试用例
list = [50, 49, 19, 4, 9]
quick = QuickSort()
print(quick.quickSort(list, 0, len(list) - 1))
print(quick.quickSort([1,2,3,4,5], 0, 4))
print(quick.quickSort([4, 3, 2,1], 0, 3))
print(quick.quickSort([8,6,7,5,3,0,9], 0, 6))代码解释
-
quickSort(input_list, low, high) 函数：
- input_list：待排序的数组。
- low：排序范围的起始索引。
- high：排序范围的结束索引。
-
处理特殊情况：
- if high - low == 1 and input_list[low] <= input_list[high]: return：如果数组长度为2且已经有序，则直接返回。
-
递归终止条件：
- if (low >= high): return：当 low 大于等于 high 时，表示排序范围为空或只有一个元素，递归结束。
-
选择 pivot：
- pivot = input_list[high]：选择最后一个元素作为 pivot。
-
分区过程：
- leftPointer 和 rightPointer 分别从 low 和 high - 1 开始向中间移动。
- while (leftPointer < rightPointer and input_list[leftPointer] < pivot): leftPointer += 1：leftPointer 向右移动，直到找到一个大于等于 pivot 的元素。
- while (leftPointer < rightPointer and input_list[rightPointer] > pivot): rightPointer -= 1：rightPointer 向左移动，直到找到一个小于等于 pivot 的元素。
- input_list[leftPointer], input_list[rightPointer] = input_list[rightPointer], input_list[leftPointer]：交换 leftPointer 和 rightPointer 指向的元素。
-
放置 pivot：
- if input_list[leftPointer] > input_list[high]: input_list[leftPointer], input_list[high] = input_list[high], input_list[leftPointer]：将 pivot 放置到正确的位置，即 leftPointer 指向的位置。
-
递归调用：
- self.quickSort(input_list, low, leftPointer)：对 pivot 左边的子数组进行递归排序。
- self.quickSort(input_list, leftPointer+1, high)：对 pivot 右边的子数组进行递归排序。
注意事项
- pivot 的选择会影响快速排序的性能。在最坏情况下，如果每次选择的 pivot 都是最小或最大的元素，快速排序的时间复杂度会退化为 O(n^2)。为了避免这种情况，可以采用随机选择 pivot 的方法。
- 快速排序是一种原地排序算法，它不需要额外的存储空间。但是，由于递归调用，它需要一定的栈空间。在最坏情况下，栈空间的大小为 O(n)。
总结
本文详细分析了快速排序实现中常见的错误，并提供了修正后的代码。通过理解代码逻辑和关键步骤，以及测试用例的验证，可以确保快速排序算法能够正确地对数组进行排序。在实际应用中，需要注意 pivot 的选择和栈空间的使用，以获得更好的性能。
