插入排序
2021-02-06 20:15
标签：直接插入 lan 查找 折半插入排序 区别 默认 距离 比较 开始 默认 L(1) 有序，将 L(2) ~ L(n)依次插入到前面已经排好序的子序列中。 空间效率：O(1) ,就地排序 时间效率：比较和移动。最好情况下，有序，只需要比较不需要移动，只要 O(n)。 平均是 O (n2) 稳定性：稳定。 适用性：均可。 主要区别是减少了比较次数，因为比较过程中采用了 折半查找，一个元素折半查找是 O(log2N) ，n 个元素折半查找是 O(n log2n)。 加上移动，所以时间复杂度是 O (n2)。 稳定性：稳定。 适用性：顺序存储。 缩小增量排序，是直接插入排序的改进版本。根据布长d 分组，距离为d的记录在同一个组中，组内进行直接插入排序。 空间效率：O(1) ,常数个辅助单元 稳定性：不稳定。 适用性：顺序存储。 希尔排序的时间性能优于直接插入排序的原因： 1）刚开始希尔排序的增量比较大，组数比较多，组内元素比较少，各组内直接插入比较快。之后增量为1的时候，因为文件已经基本有序，这个时候直接插入排序比较快。 插入排序 标签：直接插入 lan 查找 折半插入排序 区别 默认 距离 比较 开始 原文地址：https://www.cnblogs.com/juanzhi/p/12781329.html插入排序
1.直接插入排序
2.折半插入排序
3.希尔排序
上一篇：java基础:数组冒泡排序