python - 以最简单的方式正确使用 Python 进行快速排序(从 Java 翻译)

Question

我正在审查排序算法并尝试编写快速排序算法。 simplest implementation我发现它是用 Java 编写的，我已经运行它来确认它是否有效。然而，当我试图用 Python 重写它时，它似乎以某种方式关闭了。我花了几个小时试图调试它为什么不起作用，但很难调试，因为它是基于递归的算法......如果有人能告诉我下面的实现有什么问题，那将是非常有帮助。谢谢!

def partition(arr, start, end):
    piv = (start + end)//2
    pivotVal = arr[piv]

    left = start
    right = end

    while left <= right:
        if arr[left] < pivotVal:
            left += 1

        if arr[right] > pivotVal:
            right -= 1

        if left <= right:
            temp = arr[left]
            arr[left] = arr[right]
            arr[right] = temp
            left += 1
            right -= 1

    return left

def quickSort(arr, left, right):
    piv = partition(arr, left, right)

    if left < (piv - 1):
        quickSort(arr, left, piv - 1)

    if piv < right:
        quickSort(arr, piv, right)

myList = [54,26,93,17,77,31,44,55,20] # this doesn't get sorted quite right
quicksort(myList, 0, len(myList)-1)
print(myList)

Answer 1

尝试:

    while left <= right:
        while arr[left] < pivotVal:
            left += 1

        while arr[right] > pivotVal:
            right -= 1

        if left <= right:
            temp = arr[left]
            arr[left] = arr[right]
            arr[right] = temp
            left += 1
            right -= 1