插入排序，希尔排序

插入排序，希尔排序

插入排序

插入排序是一种比较排序算法

核心思想

在每次遍历序列过程中，从序列中取出一个元素插入到有序序列中，形成新的有序序列，重复该过程，直到遍历完成，形成新的有序序列。

特点：

时间复杂度分析：O(N^2)，如果序列在排序前已经是有序序列，则为O(N)空间复杂度分析：O(1)数据量较少时效率高。插入排序适合数据量少的情况算法的实际运行效率优于选择排序和冒泡排序。稳定排序 — 插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

/** * 插入排序 O(N^2) * @param a */ public static void insertSort(int[] a) { int j; //外层循环控制需要排序的趟数 -- a.length - 1 for(int p = 1;p0 && tmp

希尔排序

希尔排序是插入排序的修改版，根据步长由长到短分组，分组进行插入排序，直到步长为1为止，属于插入排序的一种。

核心思想

希尔排序为了加快速度，改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。希尔排序的思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。

特点：

希尔排序的时间复杂度较直接插入排序低，它的时间是所取“增量”（步长gap）序列的函数。最好时间复杂度： O(n) – 有序情况下平均时间复杂度： O(1.2^n ~ 1.5^n) – Hibbard最坏时间复杂度： O(n^2) — 希尔增量空间复杂度：O(1)非稳定排序 — 希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小， 插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。

/** * 优化 -- 插入排序 * 希尔排序 -- 希尔增量 O(N^2) * -- Hibbard增量O(N^3/2) * @param a */ public static void shellSort(int[] a) { int j; //最外层循环控制步长 -- 减少插入排序的数据量 for(int gap = a.length/2;gap>0;gap/=2 ) { //内层嵌套for循环是插入排序 for(int p = gap;p=gap && tmp

测试

public static void main(String[] args) { // TODO Auto-generated method stub int[] a = {1,3,2,8,9,2,4,5,10,20,12}; insertSort(a); int[] b = {1,3,4,2,1,9,8,10,5,4,3,2,1,20}; shellSort(b); for(int i = 0;i

结果：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。