製作「插入排序」算法更高效 - 的Python 3.5.2

Question

我已經嘗試在Python編碼插入排序算法 -

def insertion(list): 
    checked = 2 
    while (checked <= len(list)): 
     for i in range(checked-1): 
      if list[checked-1] < list[i]: 
       list.insert(i, list[checked-1]) 
       del list[checked] 
     checked+=1 
    return list 

我測量它採取執行1000項排序的時間 - 106.08099999999997第二

1000分之

我發現這是相當緩慢的，因爲 -

def bubbleSort(alist,n): 
    for j in range(1,n): 
     nextnum = alist[j] 
     i = j - 1 
     while i>=0 and alist[i]>nextnum: 
      alist[i + 1] = alist[i] 
      i = i - 1  
     alist[i + 1] = nextnum 

僅僅用了 - 83.71800000000007千分之一一秒

有沒有什麼辦法可以讓我的代碼更有效率/我會不得不使用不同的代碼？如果是這樣，哪種插入排序實現在python中最快？我知道插入排序通常不是最好的算法。這只是爲了我的學校工作，以便我能更好地理解我們學習的算法。

Answer 1

插入和從列表中刪除比交換位置內容更昂貴。這比冒泡排序更快：

def insertion(M): 
    for i in range(1,len(M)): 
     for j in range(i): 
      if M[i] < M[j]: 
       M[j],M[j+1:i+1] = M[i],M[j:i] 
       break 

注意這裏使用了a,b = b,a「交換」語法，交換的檢查值插入位置，領先交換的剩餘值列表中的一個。而且，一旦交換完成，從內部循環中斷開。無需繼續檢查插入位置。您還可以檢查要交換的值是否已經大於或等於先前排序的值，並且如果爲true，則跳過內部循環：

def insertion(M): 
    for i in range(1,len(M)): 
     if M[i] >= M[i-1]: 
      continue 
     for j in range(i): 
      if M[i] < M[j]: 
       M[j],M[j+1:i+1] = M[i],M[j:i] 
       break