插入排序

直接插入排序

具体算法：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；

定义

线性表（Linear List）是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用n表示，n>=0。当n=0时，表示线性表是一个
空表。设序列中第i个元素为a₁（1 ≤ i ≤ n），则线性表的一般表示为：

(a₁,a₂,a₃,…,a_i,…,a_n)

特性

• 元素在位置上是有序的
• 长度是可变的

回溯法（Back Tracking Method）（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，
而满足回溯条件的某个状态的点称为“回溯点”。

1
2
3
4
5
6
7
8
9
10

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

参考

定义

红黑树是一种自平衡二叉查找树，它可以在 O($\log(n)$ ) 时间内完成查找、插入和删除，这里的n是树中元素的数目。

红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

1. 节点是红色或黑色。
2. 根节点是黑色。