索引超出范围 - Python 中的快速排序

Question

我正在尝试实现快速排序算法，但我总是得到列表索引超出范围。

quicksort(array, left, Pi) 到底是什么超出了范围 vot-1)?

def partition(array,left,right):
    #If pivot is not on leftmost, swap to make it leftmost
    Pivot = array[0]
    i = left+1
    for j in range(i,right):
        if array[j] < Pivot:
            #Swap array[j] and array[i]
            array[j], array[i] = array[i], array[j]
            i += 1;
    #Swap pivot and A[i-1]        
    array[Pivot], array[i-1] = array[i-1], array[Pivot]
    return Pivot

def quicksort(array,left,right):
    # Base case
    if len(array) <= 1:
        return array
    #Choose pivot
    Pivot = partition(array,left,right);
    #Partition array around a pivot
    #Recursive call
    quicksort(array, left, Pivot-1)
    quicksort(array, Pivot + 1, right)

print quicksort([1,5,3,4,9,10],0,5)

错误信息：

File "quicksort.py", line 25, in <module>
print quicksort([1,5,3,4,9,10],0,5)

File "quicksort.py", line 22, in quicksort
quicksort(array, left, Pivot-1)

File "quicksort.py", line 22, in quicksort
quicksort(array, left, Pivot-1)

File "quicksort.py", line 19, in quicksort
Pivot = partition(array,left,right);

File "quicksort.py", line 11, in partition
array[Pivot], array[i-1] = array[i-1], array[Pivot]

IndexError: list index out of range

Answer 1

在partition(),

Pivot = array[0]

这里 Pivot 看起来像枢轴元素的值。然而，

#Swap pivot and A[i-1]        
array[Pivot], array[i-1] = array[i-1], array[Pivot]

这里你用它作为数组的索引。因此它很可能超出合法的数组索引范围。

Answer 2

第三次迭代时pivot和array的值如下

[10, 1, 3, 4, 9, 5] 10

你在其中尝试获得 array[Pivot]

由于只有六个元素，所以只有index out of range error is thrown

Answer 3

也许这会有所帮助。

def partition(array, begin, end):
    pivot = begin
    for i in xrange(begin+1, end+1):
        if array[i] <= array[begin]:
            pivot += 1
            array[i], array[pivot] = array[pivot], array[i]
    array[pivot], array[begin] = array[begin], array[pivot]
    return pivot


def quicksort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    if begin >= end:
        return
    pivot = partition(array, begin, end)
    quicksort(array, begin, pivot-1)
    quicksort(array, pivot+1, end)

索引超出范围 - Python 中的快速排序

Index out of range - Quicksort in Python

python

sorting

quicksort

python-2.7