python算法与数据结构-插入排序算法

Bertha 。 2023-10-06 12:28 70阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70][]

插入排序分析

开始的默认的第一个元素93为有序系列，其余的元素为无序系列，如下所示:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 1][]

54和93比，54比93小，所以把54放在前面，如下所示:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 3][]

代码如下所示:

# coding:utf-8
    def insert_sort(alist):
        """插入排序"""
        n = len(alist)
        #从右边的无序序列中取出多少个元素执行这样的过程
        for j in range(1,n):
            # j = [1,2,3,n-1]
            #i 代表内层循环起始值
            i = j
            #执行从右边的无序序列中取出第一个元素，即i位置的元素，然后将其插入到前面的正确位置中
            while i>0: #i = [1,2,3,4,5,6] 内层循环i的范围就是i从1到n-1
                if alist[i] < alist[i-1]:
                    alist[i],alist[i-1] = alist[i-1],alist[i]
                    i-=1
                else: #最优时间复杂度就是已经排好序的情况，也就是O(n)
                    break
    if __name__ == "__main__":
        li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
        print(li)
        insert_sort(li)
        print(li)
    
    
    """
    [54, 26, 93, 17, 77, 31, 44, 55, 20]
    [17, 20, 26, 31, 44, 54, 55, 77, 93]
    """

`另外一种写法如下所示:`

def insert_sort(alist):
        # 获取需要排序数据的个数
        n = len(alist)
        # 插入排序的第一次插入从第二个数字开始选择，所以下标从1开始
        for j in range(1,n):
            # 从选择插入的数据，一次和它前一个比较，主要比前面的小就交换
            for i in range(j,0,-1):
                # 实际是这样的，range(10, 0, -1)
                # 意思是从列表的下标为10的元素开始，倒序取到下标为0的元素（但是不包括下标为0元素），也就是说list[10] - list[1], 转化成range就是相当于range(1, 11)
                # 的倒序, 最后得到的结果是[10，9，8，7，6，5，4，3，2，1]
                if alist[i]<alist[i-1]:
                    temp = alist[i]
                    alist[i] = alist[i-1]
                    alist[i-1] = temp
    if __name__ == "__main__":
            li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
            print(li)
            insert_sort(li)
            print(li)

`参考资料:网上的教程`

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200705172917312.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200705172947572.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200705173024491.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020070517304131.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70