如何修复这个用 python 实现的快速排序，以便它返回正确排序的数组？

Question

我正在尝试编写快速排序程序，但代码似乎有问题，因为输出的列表未排序，但我检查了许多实现，我的实现非常相似，所以我不知道问题所在。

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]
         list[high], list[leftPointer] = list[leftPointer], list[high]
         self.quickSort(list, low, rightPointer - 1)
         self.quickSort(list, rightPointer + 1, high)
       return list


list = [50, 49, 19, 4, 9]
quick = QuickSort()
print(quick.quickSort(list, 0, len(list) - 1))

我尝试在递归调用之前打印列表，发现列表实际上在某一点已排序，但返回的列表不正确。

Answer 1

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

# 4 49 19 50 9 
# 4 / 9 19 50 49
# 4 / 9 19 49 50
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))

变化：

• 缩进交换小于和大于基准值的数字的行
• 更改了交换枢轴编号的逻辑，以处理左指针已经小于枢轴的情况
• 在顶部添加了额外的检查来处理 len(input_list) == 2 及其已排序的情况