算法 - 插入排序算法之直接插入排序
算法描述
直接插入排序算法描述如下:设线性序列是 {a0,a1,…ai-1,ai,…,an-1}。
- 第
i (1 <= i < n)
趟,设前 i 个元素构成的 {a0,a1,…,ai-1} 子序列是排序的,将元素 ai 插入 {a0,a1,…,ai-1} 的适当位置,使插入后的子序仍然是排序的,ai 的插入位置由关键字比较大小确定的。 - 重复执行 1,n 个元素共需进行
n - 1
趟排序,每趟将一个元素 ai 插入前面的子序列。区别两个关键字相同元素,其中 {} 表示已排序子列。
时间复杂度 平均情况:O(n^2)
最坏情况:O(n^2)
, 该情况出现在原序列为逆序情况
最好情况:O(n)
,出现在已经为升序排列的情况,每次之比较一次即可,共 n - 1 次循环,故为 n - 1
稳定性:稳定
算法实现
1 | /** |