Python快速排序代码运行结果异常，请求排查错误

我帮你排查出了代码里的几个关键问题，咱们一步步拆解来看：

问题1：左右指针初始化完全搞反了 #

在你的partition函数里，你把负责从左往右找元素的leftmark初始成了数组最右端的last，把负责从右往左找元素的rightmark初始成了左数第二个位置的first+1——这完全颠倒了快速排序的指针移动逻辑，直接导致后续的元素查找和交换全乱了。

正确的初始化应该是：

• leftmark从左侧（first + 1）出发，专门找比基准值大的元素
• rightmark从右侧（last）出发，专门找比基准值小的元素

问题2：指针移动的逻辑因初始值错误完全失效 #

因为指针初始位置颠倒，你写的两个循环根本不会按预期执行：第一个循环一开始leftmark就大于rightmark，直接跳过；第二个循环同样因为指针位置交叉，也不会执行。最后直接交换基准值和rightmark的位置，等于没做任何有效分割，排序自然出错。

修正后的完整代码 #

把指针初始化的问题修复后，代码就能正常工作了：

def quicksort(alist, first, last):
    if first < last:
        split = partition(alist, first, last)
        quicksort(alist, first, split - 1)
        quicksort(alist, split + 1, last)

def partition(arr, first, last):
    pivot_val = arr[first]
    # 修正指针初始化
    leftmark = first + 1
    rightmark = last
    done = False

    while not done:
        # 左指针右移，直到找到大于基准值的元素
        while leftmark <= rightmark and arr[leftmark] <= pivot_val:
            leftmark += 1
        # 右指针左移，直到找到小于基准值的元素
        while arr[rightmark] >= pivot_val and rightmark >= leftmark:
            rightmark -= 1

        if rightmark < leftmark:
            done = True
        else:
            # 交换左右指针指向的元素
            tmp = arr[leftmark]
            arr[leftmark] = arr[rightmark]
            arr[rightmark] = tmp

    # 将基准值放到正确的分割位置
    tmp = arr[rightmark]
    arr[rightmark] = arr[first]
    arr[first] = tmp
    return rightmark

lst = [22,54,33,11,87,76,1,3]
quicksort(lst,0,len(lst)-1)
print(lst)  # 输出：[1, 3, 11, 22, 33, 54, 76, 87]

验证结果 #

运行修正后的代码，就能得到完全正确的排序结果了。核心问题就是指针初始化的颠倒，导致整个分割逻辑失效，只要把这部分改对，快速排序就能正常工作。

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