Python快速排序算法：原理、实现与常见问题修正-Python教程-PHP中文网

Python快速排序算法：原理、实现与常见问题修正

霞舞

发布： 2025-10-27 15:11:01

原创

899人浏览过

Python快速排序算法：原理、实现与常见问题修正

本文深入探讨了python快速排序算法的实现细节，并针对一个常见的未完全排序问题提供了详细的调试和修正方案。通过优化支点（pivot）选择、指针移动逻辑以及递归调用，确保快速排序算法能够正确、高效地对数组进行排序。

快速排序算法概述

快速排序（Quick Sort）是一种高效的、基于比较的排序算法，其核心思想是“分而治之”。它通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

快速排序的基本步骤如下：

选择基准（Pivot）： 从数组中选择一个元素作为基准。常见的选择有第一个元素、最后一个元素或中间元素。
分区（Partition）： 重新排列数组，将所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准后面。等于基准值的元素可以放到任何一边。在这个分区结束之后，该基准就处于其最终的排序位置上。
递归排序： 递归地对基准值左边和右边的子数组进行快速排序。

原始代码分析与问题诊断

在实现快速排序时，一些细节处理不当可能导致排序结果不正确。以下是一个常见的、存在问题的Python快速排序实现示例：

先见AI

数据为基，先见未见

查看详情

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

登录后复制

以上就是Python快速排序算法：原理、实现与常见问题修正的详细内容，更多请关注php中文网其它相关文章！