快速排序与插入排序Python不工作
问题描述:
我一直试图运行quicksort切换到插入排序时,子数组大小小于10.所以事实证明,我没有得到一个排序列表。快速排序与插入排序Python不工作
我哪里错了?
import random
import time
m = 0
def quicksort(numList, first, last):
if first<last:
sizeArr = last - first + 1
if(sizeArr < m):
insert_sort(numList, first, last)
else:
mid = partition(numList, first, last)
quicksort(numList, first, mid-1)
quicksort(numList, mid + 1, last)
def partition(numList, first, last):
piv = numList[last]
i = first-1
for j in range(first,last):
if numList[j] < piv:
i += 1
temp = numList[i]
numList[i] = numList[j]
numList[j] = temp
tempo = numList[i+1]
numList[i+1] = numList[last]
numList[last] = tempo
return i+1
def insert_sort(numList, first, last):
for x in range(first, last):
key = numList[x]
y = x-1
while y > -1 and numList[y]> key:
numList[y+1] = numList[y]
y = y-1
numList[y+1] = key
if __name__ == '__main__':
start = time.time()
numList = random.sample(range(5000), 100)
m = 10
quicksort(numList, 0, len(numList) - 1)
print numList
print "Time taken: " + str(time.time() - start)
输入是一些大小在100 - 1000000之间的随机数组。我使用随机生成器,如您所见。
请帮帮我。
答
您在insert_sort
函数中有一个错误的错误。迭代range(first, last+1)
,它会正确排序。
无时无刻的错误:(谢谢指出! –