Python 列表 insert 方法：在指定位置插入元素

应该在谁之前插入？例如 5 应该插在 6 之前。6 的索引是多少呢？

nl.index(6)

6 的索引是 2。在第 2 个列表项之前插入。

执行插入

print(nl)
nl.insert(2, 5)
print(nl)

效果合适，插入后的列表依然有序。

append、insert 与 extend 的区别

观察区别：

插入与排序算法

可以利用插入来排序吗？这就是插入排序。把列表中的每个列表项都按顺序插入空列表，就得到了排好序的新列表。

list.sort 用的就是插入排序。

Timsort 算法来源

找到 binary sort 相关源码：https://github.com/python/cpython/blob/main/Objects/listobject.c

这是排序算法的核心，二叉树的搜索。

通过二叉树找到位置，然后把新元素插入。每次插入只需要 log(n) 次比较。总共 n 个位置，每个都要找到合适的值。所以外层循环次数 * 内层循环次数 = n * log(n)。

Big O Notation

各种排序算法的对比：

Timsort 是谁写的？回到 1998 年，Guido 还在荷兰孤军奋战，Tim 通过电子邮件把代码发给了 Guido。

插入排序提交记录：https://github.com/python/cpython/commit/82e6a8f80deaecc7ba3a1bd66dda7c1988c72dbf

Tim 写下了插入排序的方法。这个函数一度被叫做 timsort，可见 Guido 对于 Tim 认可和推举。

def timsort(the_array):
    runs, sorted_runs = [], []
    length = len(the_array)
    new_run = [the_array[0]]
    for i in range(1, length):
        if i == length - 1:
            new_run.append(the_array[i])
            runs.append(new_run)
            break
        if the_array[i] < the_array[i-1]:
            if not new_run:
                runs.append([the_array[i]])
                new_run.append(the_array[i])
            else:
                runs.append(new_run)
                new_run = []
        else:
            new_run.append(the_array[i])
    for item in runs:
        sorted_runs.append(insertion_sort(item))
    sorted_array = []
    for run in sorted_runs:
        sorted_array = merge(sorted_array, run)
    print(sorted_array)

timsort([2, 3, 1, 5, 6, 7])

总结

定点插入 insert 相对原来的追加 append。排好序之后，想要保持有序，需要 insert 定点插入。

两者相互成就，排序支撑插入，插入延续排序。