快速排序 Python 程序

Question

我想弄清楚为什么我的程序没有对 arr 进行完全排序，这是下面的代码，输出：[7, 9, 6, 1, 5, 10, 15, 7, 2]。可能是我的分区函数有误

def quickSort(arr, lower_bound, upper_bound):

    if lower_bound >= upper_bound:
        return

    if lower_bound < upper_bound:
        loc = partition(arr, lower_bound, upper_bound)
        quickSort(arr, lower_bound, loc-1)
        quickSort(arr, loc+1, upper_bound)

def partition(arr, lower_bound, upper_bound):
    pivot = arr[lower_bound]
    start = lower_bound
    end = upper_bound

    while start < end:
        while start <= end and arr[start] <= pivot:
            start += 1
        while start <= end and arr[end] >= pivot:
            end -= 1

        if start < end:
            arr[start], arr[end] = arr[end], arr[start]
        else:
            break

    arr[start], arr[end] = arr[end], arr[start]

    return end

arr = [7, 6, 10, 5, 9, 2, 1, 15, 7]
quickSort(arr, 0, len(arr)-1)

print(arr)

Answer 1

错误在行 while 循环之后：

arr[start], arr[end] = arr[end], arr[start]

当执行到这条语句时，start和end是相等的，所以这什么也做不了。 while 循环结束后，仍然位于 lower_bound 的枢轴值应移动到 start 和 end 相交的位置。所以正确为：

arr[lower_bound], arr[end] = arr[end], pivot

现在 return end 正在做它应该做的事情：return 枢轴元素所在的索引，将不大于的值（左）与不小于的值（右）分开).

快速排序 Python 程序

Quick Sort Python Program

python

algorithm

quicksort

data-structures