Python数据结构与算法之插入算法

插入排序

      插入排序（Insertion sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，位最新元素提供插入空间。

插入排序分析

实现

方式一：

def insert_sort(aList):
    n = len(aList)
    for j in range(1,n):
        i = j
        while i>0:
            if aList[i] < aList[i-1]:
                aList[i],aList[i-1] = aList[i-1],aList[i]
                i -= 1
            else:
                break
    return aList

方式二：

def insert_sort(aList):
    n = len(aList)
    for j in range(1,n):
        for i in range(j,0,-1):
            if aList[i] < aList[i-1]:
                aList[i],aList[i-1] = aList[i-1],aList[i]
            else:
                break
    return aList

测试：

if __name__ == "__main__":
    aList = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(aList)
    print(insert_sort(aList))

结果：

时间复杂度

• 最优时间复杂度：O(n)（升序排列，序列已处于升序状态）
• 最坏时间复杂度：O(n)
• 稳定性：稳定

最后

以上就是震动玉米为你收集整理的Python数据结构与算法之插入算法的全部内容，希望文章能够帮你解决Python数据结构与算法之插入算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。