python中的快速排序：获取超出范围的错误列表索引

Question

a = [10,100,45,60,90]
def quickSort(a,first, last):
    if last-first<1:
        return 
    pivot = a[first]
    forward = first+1
    backward = last
    while forward < backward:
        if a[forward] < pivot:
            forward=forward+1
        if a[backward] > pivot:
            backward = backward -1
        if a[forward] >= pivot and a[backward] < pivot:
            temp = a[forward]
            a[forward]=a[backward]
            a[backward]=temp
            forward=forward+1
            backward = backward -1

    if a[backward] < pivot:
        temp = a[backward]
        a[backward]= pivot
        a[first] =temp


    quickSort(a,first,backward-1)
    quickSort(a,backward+1,last)
    return a



b=quickSort(a,0,len(a)-1) 
print b  

Answer 1

需要在forward <= backward时循环：

def quickSort(a, first, last):
    if last - first < 1:
        return
    pivot = a[first]
    forward = first + 1
    backward = last 
    # <=
    while forward <= backward:
        if a[forward] < pivot:
            forward += 1
        elif a[backward] > pivot:
            backward -= 1
        elif a[forward] >= pivot > a[backward]:
            temp = a[forward]
            a[forward] = a[backward]
            a[backward] = temp
            forward += 1
            backward -= 1

    if a[backward] < pivot:
        temp = a[backward]
        a[backward] = pivot
        a[first] = temp

    quickSort(a, first, backward - 1)
    quickSort(a, backward + 1, last)
    return a

输出：

In [10]: a = [1,33,23,12,55,24]

In [11]: b = quickSort(a, 0, len(a) - 1)

In [12]: b
Out[12]: [1, 12, 23, 24, 33, 55]