Python 中的快速排序

Question

L = [7, 12, 1, -2, 0, 15, 4, 11, 9]


def quicksort(L, low, high):
    if low < high:
        pivot_location = Partition(L, low, high)
        quicksort(L,low, pivot_location)
        quicksort(L,pivot_location + 1, high)
    return L

def Partition(L, low, high):
    pivot = L[low]
    leftwall = low
    for i in range(low + 1, high, 1):
        if L[i] < pivot:
            temp = L[i]
            L[i] = L[leftwall]
            L[leftwall] = temp
            leftwall += 1
    temp = pivot
    pivot = L[leftwall]
    L[leftwall] = temp
    return leftwall

print(quicksort(L, 0, len(L) - 1))

当我运行代码时，它会产生以下结果：[-2, 0, 1, 4, 7, 11, 12, 15, 9]。一个元素位于错误的位置。谁能告诉我问题出在哪里？

Answer 1

我刚刚更改了这行代码并且运行良好：

quicksort(L, 0, len(L))

而不是

quicksort(L, 0, len(L) - 1)

Answer 2

在这里，我只是向您展示另一种在Python中实现Q_Sort的简单方法：

def q_sort(lst):
    return [] if not lst else q_sort([e for e in lst[1:] if e <= lst[0]]) + [lst[0]] + q_sort([e for e in lst[1:] if e > lst[0]])


L = [7, 12, 1, -2, 0, 15, 4, 11, 9]

print q_sort(L)

我们得到：

[-2, 0, 1, 4, 7, 9, 11, 12, 15]

Python 中的快速排序

Quicksort in Python

python

quicksort