一个网站的百度反链多好还是少好,h5美食制作网站模板下载,衡水手机网站建设,wordpress实现聊天功能前言这次我们介绍插入类排序中的 直接插入排序 和 希尔排序 。对于直接插入排序#xff0c;虽然它的时间复杂度也是 O(n^2) #xff0c;但是在元素 有序或近乎有序 的情况下#xff0c;时间复杂度可以降为 O(n) #xff0c;效率比 O(nlogn) 的算法还要高。然而对于大规模的…前言这次我们介绍插入类排序中的 直接插入排序 和 希尔排序 。对于直接插入排序虽然它的时间复杂度也是 O(n^2) 但是在元素 有序或近乎有序 的情况下时间复杂度可以降为 O(n) 效率比 O(nlogn) 的算法还要高。然而对于大规模的乱序数组使用直接插入排序的效率是非常低的。此时我们需要使用希尔排序希尔排序在直接插入排序的基础上弥补了直接插入排序只能比较相邻元素的不足使得可以按照指定步长比较元素充分发挥了直接插入排序对于小规模有序数组排序的优势。下面我们分别介绍 直接插入排序 和 希尔排序 两类插入排序。直接插入排序有如下数组我们需要对它从小到大排序利用直接插入排序步骤如下将第二个元素和第一个元素比较小于第一个元素的话交换位置这样第二个元素作为最小的元素排在了最前面大于的话不交换。然后将第三个元素和第二个元素比较小于第二个元素的话交换位置然后再和第一个元素比较小于第一个元素的话再次交换位置这样第三个元素作为最小的元素排在了最前面大于的话不交换。以此类推直到最后一个元素插入到合适位置。下图展示了整个排序的过程直接插入排序的代码public static void sort(Comparable[] arr) { int n arr.length; // 0位置不需要比从1到最后一个位置n-1 for (int i 1; i n - 1; i) { for( int j i; j 0 arr[j].compareTo(arr[j-1]) 0 ; j--) { swap(arr, j, j-1); } }}private static void swap(Object[] arr, int i, int j) { Object t arr[i]; arr[i] arr[j]; arr[j] t;}优化优化的思路就是将内循环中每次 swap 交换操作修改为 让较大的元素后移最后再进行一次交换 这样一来访问数组的次数就减少了(交换需要三行赋值只需要一行)。优化步骤如下每次先保存当前插入的元素。将当前保存的元素(第二个元素)和第一个元素比较小于第一个元素的话将第一个元素移动到第二个元素位置然后当前保存的元素移动到第一个元素位置这样第二个元素作为最小的元素排在了最前面。将当前保存的元素(第三个元素)和第二个元素比较小于第二个元素的话将第二个元素移动到第三个元素位置然后当前保存的元素移动到第二个元素位置接着小于第一个元素的话再次执行以上操作这样第三个元素作为最小的元素排在了最前面。以此类推直到最后一个元素插入到合适位置。下图展示了优化思路的过程优化的直接插入排序代码public static void sort(Comparable[] arr) { int n arr.length; // 0位置不需要比从1到最后一个位置n-1 for (int i 1; i n - 1; i) { // 保存当前插入的元素 Comparable e arr[i]; int j; for (j i; j 0 arr[j - 1].compareTo(e) 0; j--) { arr[j] arr[j - 1]; } arr[j] e; }}希尔排序上面我们介绍了直接插入排序它对于大规模乱序数组的排序效率比较低因为只能交换相邻的元素所以元素只能一点一点地从数组的一端移动到另一端。此外如果最小的元素在数组的末尾那么将它插入到正确位置需要移动 N-1 次。希尔排序的出现解决了上述问题。它能够交换不相邻的元素以对数组的局部进行排序并最终用直接插入排序将局部有序的数组排序。希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组也叫作 h 有序数组 。我们不研究 h 是如何得来的这里直接使用了《算法》书中的 h 步长序列。h 3*h1 根据 h 的取值分别为1、4、13 ...实际上只需要把直接插入排序代码中移动元素的距离由 1 改为 h 即可。这样希尔排序就转换为了一个类似于直接插入排序但使用不同增量的过程。下图展示了希尔排序的过程如果你仔细观察会发现在 h1 时相比直接插入排序比较的次数大大减少了这是因为希尔排序使得部分子数组有序而直接插入排序对于近乎有序的数组效率是非常高的。希尔排序代码public static void sort(Comparable[] arr) { int n arr.length; // 步长序列: 1, 4, 13... int h 1; while (h n / 3) { h 3 * h 1; } while (h 1) { for (int i h; i n; i) { // 将 arr[i] 插入到 arr[i-h], arr[i-2*h], arr[i-3*h]... 中 Comparable e arr[i]; int j; // 优化的插入排序 for (j i; j h e.compareTo(arr[j - h]) 0; j - h) { arr[j] arr[j - h]; } arr[j] e; } h / 3; }}
