Python入门必练小项目-插入排序详解

三、算法特点

• 比较性：排序时元素之间需要比较，所以为比较排序
• 稳定性：从代码我们可以看出只有比较元素大于当前元素，比较元素才会往后移动，所以相同元素是不会改变相对顺序
• 时间复杂度：插入排序同样需要两次循坏一个一个比较，故时间复杂度也为O(n^2)
• 空间复杂度：只需要常数个辅助单元，所以空间复杂度也为O(1)
• 记忆方法：想象成在书架中插书：先找到相应位置，将后面的书往后推，再将书插入

四、代码实现

# _*_ coding:utf-8 _*_

# 插入排序
def insert_sort(list):

    n = len(list)
    print(f"列表的总长度为：{n}")

    for i in range(1, n):

        print('-' * 40)
        print(f"当前i为：{i}")
        key = list[i]
        print(f"当前key为：{key}")
        j = i - 1
        print(f"当前j为：{j}")

        while j >= 0:

            if list[j] > key:
                print(f"因为list[j]:{list[j]}>key:{key},所以执行这一步")
                print(f"list[{j+1}]={list[j+1]},list[{j}]={list[j]}")
                # list[j + 1], list[j] = list[j], key

                list[j+1] = list[j]
                list[j] = key

                print(f"list[{j}]:{list[j]},key:{key}")

            j -= 1
            print(f"当前j为：{j}")
            print(f"当前list为：{list}")

        # # return list

if __name__ == '__main__':
    list = [56, 12, 1, 8, 254, 456, 10, 100, 34, 56, 7, 23, 234, -57]
    print(f"原列表为：{list}")
    insert_sort(list)
    print(f"新列表为：{list}")

最终结果为：

新列表为：[-57, 1, 7, 8, 10, 12, 23, 34, 56, 56, 100, 234, 254, 456]

到这里插入排序就讲完了，接下来我会一天整理一个小项目分享给大家，有兴趣的可以关注下~大家一起进步，另外，想要更多已经整理好的项目资料的可以加下下方的名片，可以免费分享给大家。