建设集团网站 技术支持中企动力,昆明网站建设加q.479185700,网站列表设计,公司网站怎么免费建文章目录 前言一、希尔排序的思想二、使用步骤总结 前言
希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序#xff0c;如果数组的最大值刚好是在第一位#xff0c;要将它挪到正确的位置就需要 n - 1 次移动。也就是说#xff0c;原数组的一个元素如果距离它… 文章目录 前言一、希尔排序的思想二、使用步骤总结 前言
希尔排序可以说是插入排序的一种变种。无论是插入排序还是冒泡排序如果数组的最大值刚好是在第一位要将它挪到正确的位置就需要 n - 1 次移动。也就是说原数组的一个元素如果距离它正确的位置很远的话则需要与相邻元素交换很多次才能到达正确的位置这样是相对比较花时间了。希尔排序就是为了加快速度简单地改进了插入排序交换不相邻的元素以对数组的局部进行排序。
一、希尔排序的思想
采用插入排序的方法先让数组中任意间隔为 h 的元素有序刚开始 h 的大小可以是 h n / 2,接着让 h n / 4让 h 一直缩小当 h 1 时也就是此时数组中任意间隔为1的元素有序此时的数组就是有序的了。 为方便理解我还准备了图片 如果还是不懂的话我还给你准备了优质的文章讲解希尔排序
二、使用步骤
public class ShellSort {public static int[] shellSort(int arr[]) {if (arr null || arr.length 2) return arr;int n arr.length;// 对每组间隔为 h的分组进行排序刚开始 h n / 2;for (int h n / 2; h 0; h / 2) {//对各个局部分组进行插入排序for (int i h; i n; i) {// 将arr[i] 插入到所在分组的正确位置上insertI(arr, h, i);}}return arr;}/*** 将arr[i]插入到所在分组的正确位置上* arr[i]] 所在的分组为 ... arr[i-2*h],arr[i-h], arr[ih] ...*/private static void insertI(int[] arr, int h, int i) {int temp arr[i];int k;for (k i - h; k 0 temp arr[k]; k - h) {arr[k h] arr[k];}arr[k h] temp;}
}总结
需要注意的是对各个分组进行插入的时候并不是先对一个组排序完了再来对另一个组排序而是轮流对每个组进行排序。
性质 1、时间复杂度O(nlogn) 2、空间复杂度O(1) 3、非稳定排序 4、原地排序
