快速排序與插入排序Python不工作

Question

我一直試圖運行quicksort切換到插入排序時，子數組大小小於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函數中有一個錯誤的錯誤。迭代range(first, last+1)，它會正確排序。