我正在尝试实现快速排序算法,但我总是得到列表索引超出范围。
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
最佳答案
在partition()
中,
Pivot = array[0]
这里的 Pivot
看起来像 pivot 元素的值。然而,
#Swap pivot and A[i-1]
array[Pivot], array[i-1] = array[i-1], array[Pivot]
这里你用它作为数组的索引。因此它很可能超出合法的数组索引范围。
关于python - 索引超出范围 - Python 中的快速排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31399021/