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

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

# 实例化快速排序类
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]