排序算法
1 插入排序
1.1 描述
插入排序从无序序列中取一个元素，并插入到有序序列中，直到无序序列为空，此时插入排序完成。排序开始时，待排序序列中第1个元素为有序序列，第2个元素及后面的所有元素组成的序列为无序序列，插入排序把无序序列中的元素依次插入到前面的有序序列即可。
1.2 复杂度分析
1.2.1 时间复杂度
***Note:***假设无序序列需要升序排列。
最好的情况：待排序序列为升序序列，此时只需要进行n-1次比较，而不需要进行元素的移动，时间复杂度为*O(n)*。
最坏的情况：待排序序列为降序序列，此时需要需要与前面有序序列的所有元素进行比较并移动，时间复杂度为*O($n+n^2$)*。
1.2.2 空间复杂度
由插入排序的原理可知，其只需要额外保存一个待排序的元素，因此空间复杂度为常数复杂度*O(1)*。
1.3 代码实现
1 | TBC. |