参考视频实现QuickSort算法出错，请求排查代码问题

我参考了某视频中的QuickSort实现方法，写出了以下Python代码，但运行结果不符合预期，想知道代码哪里出错了：

def partition(arr, low, high):
 
    pivot = arr[low]
    i = low + 1
    j = high

    switch = True

    while (True):
        while switch == True:
            while arr[j] >= pivot and i < j:
                j -= 1
            pos = arr.index(pivot)
            arr[j] , arr[pos] = arr[pos], arr[j]
            switch = False

        while switch == False:
            while arr[i] <= pivot and i < j:
                i += 1
            pos2 = arr.index(pivot)
            arr[i] , arr[pos2] = arr[pos2], arr[i]
            switch = True

        if i >= j:
            return j
 

def quickSort(arr, low, high):

    if high - low >= 1:
        pivot = partition(arr, low, high)
        quickSort(arr, low, pivot - 1)
        quickSort(arr, pivot + 1, high)


arr = [3, 1, 5, 7, 6, 2, 4]
quickSort(arr, 0, len(arr) - 1)
print("Sorted array:")
print(arr)

运行输出结果：

Sorted array:
[1, 2, 3, 6, 4, 5, 7]

错误原因分析 #

你的代码存在三个核心问题：

1. arr.index(pivot)的误用
   list.index()会返回数组中第一个匹配pivot值的索引，但基准元素在交换过程中位置会变化，若数组存在重复值，这个方法会直接返回错误位置；即使无重复值，每次调用都要遍历数组，既低效又容易引发逻辑错误。你应该直接跟踪基准的当前位置，而非用查找方法。

2. 循环结构与终止逻辑混乱
   外层while(True)嵌套两个switch分支循环，会强制每次切换状态都执行交换，不管是否找到符合条件的元素；同时终止判断i >= j放在嵌套循环之后，会导致i >= j时仍可能执行不必要的交换，破坏分区逻辑。

3. 基准元素的最终位置错误
   分区结束时，基准元素没有被放到正确的位置，导致后续递归的区间划分错误，最终排序结果混乱。

修正后的代码 #

基于你参考的实现思路，修正后的代码如下：

def partition(arr, low, high):
    pivot = arr[low]
    i = low + 1
    j = high

    while True:
        # 从右往左找小于基准的元素
        while i <= j and arr[j] >= pivot:
            j -= 1
        # 从左往右找大于基准的元素
        while i <= j and arr[i] <= pivot:
            i += 1
        # 找到可交换的元素对则交换
        if i <= j:
            arr[i], arr[j] = arr[j], arr[i]
        else:
            # 将基准放到分区后的正确位置
            arr[low], arr[j] = arr[j], arr[low]
            return j

def quickSort(arr, low, high):
    if low < high:
        pivot_pos = partition(arr, low, high)
        quickSort(arr, low, pivot_pos - 1)
        quickSort(arr, pivot_pos + 1, high)

arr = [3, 1, 5, 7, 6, 2, 4]
quickSort(arr, 0, len(arr) - 1)
print("Sorted array:")
print(arr)

修正说明 #

• 移除冗余的switch变量，改为在同一个循环中交替查找左右两侧的目标元素，找到后交换，直到i > j时终止。
• 不再使用arr.index(pivot)，而是在分区结束时直接将基准元素与j位置的元素交换，此时j就是基准元素的最终正确位置。
• 递归条件简化为low < high，逻辑更简洁准确。

运行修正后的代码，会得到正确的排序结果：[1, 2, 3, 4, 5, 6, 7]

内容的提问来源于stack exchange，提问作者Rai