排序算法-直接插入排序

1. 算法描述

1. 第i(1<=i<n)趟，数据序列为{a0,a1,a2...an-1},其前i个元素构成的子序列a{a0,a1...ai-1}是排序的，将元素ai插入到{a0,a1...ai-1}的适当位置，使得插入后的子序列仍然是排序的，a的插入位置由关键字比较决定。
2. 重复上述操作，n个元素工序n-1趟扫描，每次讲一个元素插入到他前面的子序列中。

直接插入排序过程

2. 代码

3. 时间复杂度

• 最好情况：序列是已排序序列。O(n)
• 最坏情况：序列是反向序列。O(n^2)
• 平均情况: 序列是随机序列。O（n^2）

4. 空间复杂度

• O（1）

5. 稳定性

• 稳定