希尔排序算法
原博主：https://www.jianshu.com/p/d730ae586cf3
1,希尔排序概述
希尔排序(shell Sort) 是插入排序的一种算法，是对直接插入排序的几个优化，也称缩小增量排序。
注意：1，希尔排序是非稳定性排序算法；
2，为了方便记忆算法，我习惯将其记作 “三层for循环+if” ——** for（for（for（if）））**）；
2，比较直接插入排序算法：
希尔排序是基于直接插入排序的以下两点性质而提出的改进方法：
1，插入排序在对几乎已经排好序的数据操作时，效率高，即可达到线性排序的效率。
2，插入排序一般是低效的，因为插入排序每次只能将数据移动一位。
3，希尔排序的思想
希尔排序是将待排序的数组元素 按下标的一定增量分组，分成多个子序列，然后对多个子序列进行直接插入排序算法排序；
然后依次缩减增量在进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。
理解过程：
**增量d 的范围： **1<= d < 待排序数组的长度 （d 需为 int 值）
**增量的取值： **一般的初次取序列（数组）的一半为增量，以后每次减半，直到增量为1。
第一个增量=数组的长度/2,
第二个增量= 第一个增量/2,
第三个增量=第二个增量/2,
以此类推，最后一个增量=1。
好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
三、原理过程图解
四、时间复杂度
**希尔排序的执行时间依赖于增量序列。 **
希尔排序耗时的操作有：比较 + 后移赋值。
时间复杂度情况如下：（n指待排序序列长度）
1) 最好情况：序列是正序排列，在这种情况下，需要进行的比较操作需（n-1）次。后移赋值操作为0次。即O(n)
2) 最坏情况：O(nlog2n)。
3) 渐进时间复杂度（平均时间复杂度）：O(nlog2n)
白话理解：
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n²)好一些。
希尔算法的性能与所选取的增量（分组长度）序列有很大关系。只对特定的待排序记录序列，可以准确地估算比较次数和移动次数。想要弄清比较次数和记录移动次数与增量选择之间的关系，并给出完整的数学分析，至今仍然是数学难题。希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。希尔排序没有快速排序算法快，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。
（注：专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法。）
五,稳定性分析：
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱
所以希尔排序是不稳定的。
六，核心代码（升序排序为例）。
（注：为方便记忆算法，我习惯将其记作“三层for循环+if ” ——for（for（for（if））））
//希尔排序 升序 for (int d = arr.length / 2;d>0;d /= 2){ //d：增量 7 3 1 for (int i = d; i < arr.length; i++){ //【插入排序 可以提取出来】 //i:代表即将插入的元素角标，作为每一组比较数据的最后一个元素角标 //j:代表与i同一组的数组元素角标(前一个元素角标) for (int j = i-d; j>=0; j-=d){ //在此处-d 为了避免下面数组角标越界 j=j-d if (arr[j] > arr[j + d]) {// j+d 代表即将插入的元素所在的角标 //符合条件，插入元素（交换位置） int temp = arr[j]; arr[j] = arr[j + d]; arr[j + d] = temp; } } //==================================== } } return arr; }
测试所有源码：
public class ShellSorts { public static void main(String[] args) { // 声明一个数组 int[] arr = new int[] { 3, 2, 5, 4, 1 }; System.out.println("原数组：" + Arrays.toString(arr)); System.out.println("排序后" + Arrays.toString(insertionSort(arr))); } /** * 希尔排序思路 * 1，先判断数组为空或者只有一个元素的情况 * 2，确定截取增量长度=数组长度/2(循环) 直到增量为1 * 3，对每一个增量进行排序【一般采用直接插入排序】 * 4，接着遍历下一层增量，直到增量为1，排序完成 * @param arr * @return */ // 简化希尔排序 public static int[] insertionSort(int[] arr) { // 数组长度小于等于1的情况 if (arr == null || arr.length <= 1) { return arr; } // 希尔排序 升序 for (int d = arr.length / 2; d > 0; d /= 2) { // d：增量 7 3 1 for (int i = d; i < arr.length; i++) { // 【插入排序 可以提取出来】 // i:代表即将插入的元素角标，作为每一组比较数据的最后一个元素角标 // j:代表与i同一组的数组元素角标(前一个元素角标) for (int j = i - d; j >= 0; j -= d) { // 在此处-d 为了避免下面数组角标越界 // j=j-d if (arr[j] > arr[j + d]) {// j+d 代表即将插入的元素所在的角标 // 符合条件，插入元素（交换位置） int temp = arr[j]; arr[j] = arr[j + d]; arr[j + d] = temp; } } } } return arr; } // 算法提炼 两元素位置交换方法 public static void swap(int[] arr, int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } // 对于java自带的Arrays.toString()方法的实现 public static void printArray(int[] arr) { System.out.print("["); for (int x = 0; x < arr.length; x++) { if (x != arr.length - 1) { System.out.print(arr[x] + ", "); } else { System.out.println(arr[x] + "]"); } } } }