本文深入探讨了python快速排序算法的实现细节，并针对一个常见的未完全排序问题提供了详细的调试和修正方案。通过优化支点（pivot）选择、指针移动逻辑以及递归调用，确保快速排序算法能够正确、高效地对数组进行排序。
快速排序算法概述
快速排序（Quick sort）是一种高效的、基于比较的排序算法，其核心思想是“分而治之”。它通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
快速排序的基本步骤如下：
- 选择基准（Pivot）： 从数组中选择一个元素作为基准。常见的选择有第一个元素、最后一个元素或中间元素。
- 分区（Partition）： 重新排列数组，将所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准后面。等于基准值的元素可以放到任何一边。在这个分区结束之后，该基准就处于其最终的排序位置上。
- 递归排序： 递归地对基准值左边和右边的子数组进行快速排序。
原始代码分析与问题诊断
在实现快速排序时，一些细节处理不当可能导致排序结果不正确。以下是一个常见的、存在问题的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) # 错误4：递归边界可能不正确 return list list = [50, 49, 19, 4, 9] quick = QuickSort() print(quick.quickSort(list, 0, len(list) - 1))
上述代码存在以下几个主要问题，导致数组无法正确排序：
立即学习“Python免费学习笔记（深入）”；
- 分区逻辑不完整： 在 while (leftPointer < rightPointer) 循环结束后，leftPointer 和 rightPointer 可能指向同一个元素，或者 leftPointer 已经越过 rightPointer。此时，list[leftPointer], list[rightPointer] = list[rightPointer], list[leftPointer] 这一行代码的交换逻辑可能不正确，它没有正确地将 leftPointer 或 rightPointer 指向的元素与基准元素进行最终的交换。
- 基准元素归位错误： list[high], list[leftPointer] = list[leftPointer], list[high] 这行代码试图将基准元素（list[high]）放到正确的位置。然而，在 leftPointer 和 rightPointer 移动后，leftPointer 指向的元素不一定就应该与基准元素交换。尤其是在 list[leftPointer] 已经小于或等于 pivot 的情况下，进行交换会打乱分区。
- 递归调用边界不准确： 原始代码中的 self.quickSort(list, low, rightPointer – 1) 和 self.quickSort(list, rightPointer + 1, high) 递归调用，其边界是基于 rightPointer 的位置。但 rightPointer 在循环结束后，可能不是基准元素最终的位置，这会导致某些元素被遗漏或重复处理。
修正后的快速排序实现
为了解决上述问题，我们需要调整分区逻辑，确保基准元素能正确归位，并修正递归调用的边界。以下是修正后的Python快速排序实现：
class QuickSort: def quickSort(self, input_list, low, high): # 优化：处理只有两个元素且已排序的情况，避免不必要的递归 if high - low == 1 and input_list[low] <= input_list[high]: return # 基本情况：如果子数组只有一个或零个元素，则无需排序 if low >= high: return else: leftPointer = low rightPointer = high - 1 # 修正1：rightPointer 初始化为 high - 1，因为 high 位置存放的是基准元素 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 # 如果左右指针仍未相遇，则交换它们指向的元素 if leftPointer < rightPointer: # 修正2：确保在交换前指针未相遇 input_list[leftPointer], input_list[rightPointer] = input_list[rightPointer], input_list[leftPointer] # 循环结束后，leftPointer (或 rightPointer) 指向的位置是第一个大于等于基准的元素 # 将基准元素放到正确的位置 if input