直接插入排序

• 地位
  • 最簡單的插入排序
• 過程
  • 每趟排序將一個新元素插入到有序序列的合適位置。
  • 算法
    • 數據為D0，D1，D2，，，Dn。初始狀態，不妨將第一個元素D0看做當前有序序列的唯一一個元素。
    • 依次將D1，D2，D3插入到這個有序序列中，顯然，掃描這n-1個元素是一個外部循環。
    • 下面進行插入過程，顯然，當我去為Di尋找合適位置插入時，前i-1個元素一定有序，此時將Di與D0到Di-1進行比較，找尋插入位置，顯然，這是一個內部循環。（當然，尋找插入位置一般從后向前找，也就是從Di-1找到D0）

• 優化

  • 復雜度

    排序名稱最好情況最壞情況平均情況

    直接插入排序	O(n)	O(n^2)	O(n^2)

  • 不難看出，當數據正序時（或者說數據符合想要達到的排序結果）排序效率最高（因為每次插入前面的元素不需要后移），當數據反序時排序效率最低（每次插入前面數據都要后移）。

  • 優化思路很簡單，我要找尋的這個插入位置其實是在有序序列一一比較的，然而對有序序列而言其實有更快的方法進行查找，這就是二分查找法。

""" 本模塊實現一位數據的直接插入排序及其優化 """def insertSort(data=[0, 1, 2, 3, 4, 5]):for i in range(1, len(data)):# 從下標1開始記錄每一個待排元素temp = data[i]# 從當前元素的前一個元素開始進行合適位置查找j = i - 1while j >= 0 and temp < data[j]:# 循環直到序列第一個值或者找到一個元素比它小,循環內不斷將元素向后交換data[j+1] = data[j]j -= 1data[j+1] = tempprint(data)def binarySearch(inputData, endIndex, value):''':param inputData: 數據集:param endIndex: 查找結束位置:param value: 查找的值:return:'''left = 0right = endIndex - 1while left <= right:middle = left + (right-left) // 2if inputData[middle] >= value:right = middle - 1else:left = middle + 1return left if left < endIndex else -1def insertSortOptimized(data=[0, 1, 2, 3, 4, 5]):for i in range(1, len(data)):j = i - 1temp = data[i]insertIndex = binarySearch(data, i, data[i])if insertIndex != -1:while j >= insertIndex:data[j+1] = data[j]j -= 1data[j+1] = tempprint(data)if __name__ == '__main__':testData1 = [1, 2, 3, 5, 4, 0]insertSort(data=testData1)insertSortOptimized(testData1)

具體可以查看我的github。

總結

以上是生活随笔為你收集整理的排序算法-02直接插入（python实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。