插入排序

难度：⭐⭐⭐

1. 题目描述

题目描述

插入排序（Insertion sort）是一种简单直观的排序算法

1. 从第一个元素开始，认为它是排好的序列；然后下一个元素加入进来，从后往前找到合适的位置
2. 每次得到一个排好的序列，重复剩下的每一个元素，将其从后往前插入到合适的位置

2. 关键点

• 认为第一个已经排好序
• 与打扑克类似，将一个新元素插入到已排好的序列中

3. 代码实现

点击显示代码

import random


def sort_insertion(lst):
    """插入排序"""
    lst_len = len(lst)
    for i in range(lst_len):
        index = i-1
        current = lst[i]
        while index >= 0 and lst[index] > current:
            lst[index+1] = lst[index]
            index -= 1
        lst[index+1] = current
        print(i, lst[:i+1])


lst = [random.randint(0, 10) for i in range(10)]
print(lst)
sort_insertion(lst)
print(lst)

4. 运行示例

[7, 5, 1, 8, 0, 2, 9, 8, 3, 4]
0 [7]
1 [5, 7]
2 [1, 5, 7]
3 [1, 5, 7, 8]
4 [0, 1, 5, 7, 8]
5 [0, 1, 2, 5, 7, 8]
6 [0, 1, 2, 5, 7, 8, 9]
7 [0, 1, 2, 5, 7, 8, 8, 9]
8 [0, 1, 2, 3, 5, 7, 8, 8, 9]
9 [0, 1, 2, 3, 4, 5, 7, 8, 8, 9]
[0, 1, 2, 3, 4, 5, 7, 8, 8, 9]

5. 进阶思考

1. 优化示例代码