插入排序

在左边建立排好的部分，每次加入一个值。新值先被取出，再向左移，直到遇到比它小的值。

• 最佳 Ω(n)
• 平均 Θ(n²)
• 最差 O(n²)
• 内存 O(1)
• 稳定
• 无需额外内存

这些是什么意思？

• 最佳：输入对这个算法最容易时，时间随列表大小 n 增长的方式。
• 平均：时间随 n 的一般增长。n² 表示值的个数翻倍时耗时约为四倍；n log n 增长得慢得多。
• 最差：最难的输入下的增长。适合速度绝不能下降的场合。
• 内存：除列表外还需要多少额外内存。1 表示几个变量，n 表示一份列表副本。
• 稳定：两个相等的值保持原来的顺序。按记录的某个字段排序时很重要。
• 无需额外内存：直接在列表内部排序，不用第二个列表。