带插入排序的快速排序Python不起作用

Question

当子数组大小小于10时，我一直试图运行快速排序切换到插入排序。结果是，我得到的不是一个有序的列表

我哪里错了?

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之间的随机数组。如你所见，我使用的是随机生成器。

请帮帮我。

Answer 1

您在insert_sort函数中有一个偏离1的错误。迭代range(first, last+1)，它将正确排序。