修复Python快速排序实现：确保正确排序数组

本文旨在帮助开发者理解和修复Python中快速排序算法的实现问题。通过分析常见的错误原因，提供修正后的代码示例，并详细解释代码逻辑和关键步骤，确保快速排序算法能够正确地对数组进行排序。文章还包含测试用例，帮助读者验证代码的正确性，并提供了一些注意事项，以避免在实际应用中出现类似的问题。

快速排序是一种高效的排序算法，它采用分而治之的策略来对数组进行排序。然而，在实现快速排序时，容易出现一些错误，导致排序结果不正确。本文将分析一个常见的快速排序实现问题，并提供修正后的代码，以及详细的解释和测试用例。

问题分析

原始代码中存在几个关键问题，导致排序结果不正确：

立即学习“Python免费学习笔记（深入）”；

1. 指针移动逻辑错误：while 循环中，当 leftPointer 和 rightPointer 相遇时，没有正确处理 pivot 的位置。这会导致 pivot 没有被放置到正确的位置上。
2. 递归调用范围错误：递归调用 quickSort 时，范围的指定可能存在问题，导致某些元素没有被正确排序。
3. 缺少对特殊情况的处理：对于长度为2且已经有序的数组，没有进行特殊处理。

修正后的代码

简篇AI排版

AI排版工具，上传图文素材，秒出专业效果！

554

查看详情

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))

代码解释

1. quickSort(input_list, low, high) 函数：
   • input_list：待排序的数组。
   • low：排序范围的起始索引。
   • high：排序范围的结束索引。
2. 处理特殊情况：
   • if high - low == 1 and input_list[low] <= input_list[high]: return：如果数组长度为2且已经有序，则直接返回。
3. 递归终止条件：
   • if (low >= high): return：当 low 大于等于 high 时，表示排序范围为空或只有一个元素，递归结束。
4. 选择 pivot：
   • pivot = input_list[high]：选择最后一个元素作为 pivot。
5. 分区过程：
   • 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 指向的元素。
6. 放置 pivot：
   • if input_list[leftPointer] > input_list[high]: input_list[leftPointer], input_list[high] = input_list[high], input_list[leftPointer]：将 pivot 放置到正确的位置，即 leftPointer 指向的位置。
7. 递归调用：
   • self.quickSort(input_list, low, leftPointer)：对 pivot 左边的子数组进行递归排序。
   • self.quickSort(input_list, leftPointer+1, high)：对 pivot 右边的子数组进行递归排序。

注意事项

• pivot 的选择会影响快速排序的性能。在最坏情况下，如果每次选择的 pivot 都是最小或最大的元素，快速排序的时间复杂度会退化为 O(n^2)。为了避免这种情况，可以采用随机选择 pivot 的方法。
• 快速排序是一种原地排序算法，它不需要额外的存储空间。但是，由于递归调用，它需要一定的栈空间。在最坏情况下，栈空间的大小为 O(n)。

总结

本文详细分析了快速排序实现中常见的错误，并提供了修正后的代码。通过理解代码逻辑和关键步骤，以及测试用例的验证，可以确保快速排序算法能够正确地对数组进行排序。在实际应用中，需要注意 pivot 的选择和栈空间的使用，以获得更好的性能。

以上就是修复Python快速排序实现：确保正确排序数组的详细内容，更多请关注php中文网其它相关文章！