希尔排序（Shell Sort）

  希尔排序其实是一种插入排序，也被称为缩小增量排序算法，或递减增量排序算法，是插入排序的一种更高效的增强版。
  简单插入排序是很循规蹈矩的做法，即使是升级优化一下，运用二分插入，也避免不了从头到尾都依次处理一遍。不考虑特殊情况，这种一个不落到遍历算法，在时效问题上，是确定低效。于是有个叫希尔（Donald Shell）的大神，据说在公元1959年一个风雨交加电闪雷鸣的夜晚，喝着咖啡唱着小曲儿，灵光乍现、欣然偶得。为了表达对这位先贤的敬仰和怀念，后世就直接以他的名字给这个算法命名，希尔排序。

基本思想

  在上一篇我们可以看到，插入排序在对已经接近有序的数据样本进行排序时，效率是最高的；但一般的插入算法，必定是低效的，一个个的挪，腾地方，最终一次还是只能倒腾一个数据元素。
  希尔排序直接反其道而行，采用跳跃式分组的策略：采取一个增量，将数据样本虚拟的分成若干个小组，然后对每个分组进行插入排序；随后逐步缩小增量，继续分组进行插入排序操作；直至增量变为1，最终完成整个排序。
  希尔排序这种做法的灵魂核心就是，通过增量分组排序的策略，使得数据样本在每一次操作后都达到整体上的更加有序，整体上是小的基本在前，大的基本在后；逐渐缩小增量的过程，其实都是逐渐对更加有序的数据进行操作的过程，这个自然在时效上会拔高很多。

算法描述

1：选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2：按增量序列个数k，对序列进行k 趟排序；
3：每趟排序，根据对应的增量ti，将待排序列分割成若干虚拟子序列，分别对各子序列进行插入排序。当增量为1 时，即是对整体序列进行处理，即完成排序。

动图演示

代码实现

import java.util.Arrays;

/** 
* @author    :Veiking
* @version    :2020年10月10日
* 说明        :希尔排序算法
*/
public class ShellSort {
    /**
     * 希尔排序
     * @param arrays
     * @return
     */
    public static int[] sort(int[] arrays) {
        int temp;
        // 控制增量序列（t1，t2，…，tk），当增量k为1的时候为最后一趟，排序即完成
        for (int k = arrays.length/2; k > 0; k/=2) {
            // 找到每个子序列的最后最后一个元素的位置
            int i=1;
            while(i*k =0; index-=k) {
                    if(arrays[index]>arrays[index+k]){
                        temp = arrays[index];
                        arrays[index]  = arrays[index+k];
                        arrays[index+k] = temp;
                    }
                }
            }
            // System.out.println("增量"+k+"排序操作结果："+Arrays.toString(arrays));
        }
        return arrays;
    }

    // 执行
    public static void main(String[] args) {
        int[] input = new int[]{3, 6, 9, 5, 13, 15, 4, 11, 1, 12, 16, 2, 14, 10, 7, 8};
        System.out.println("样本初始样本数据："+Arrays.toString(input));
        int[] output = ShellSort.sort(input);
        System.out.println("冒泡排序结果数据："+Arrays.toString(output));
    }
}

算法分析

  希尔排序算法的基本性能，归纳如下图：

1、 时间复杂度

  研究希尔排序的重点是增量步长，这个增量会影响希尔排序的时间复杂度。
  希尔老先生最初给的建议是，取数据样本长度的一半，即n/2，并逐次取值至为1。这样就可以得到比简单插入表现更好的算法。
  但后世有人发现研究希尔排序的最重要的核心操作不是交换，而是比较，是比较元素大小这个行为。
  于是后人总结了下，一些不同步长下，希尔排序的最差时间复杂度，如下图：

  然而，这还没有完，一位叫Sedgewick后来发现：1，5，19，41，109,… （见维基百科）这样一组步长序列，在希尔排序中，最为优秀，也是希尔排序迄今为止表现最好的步长序列。例用这样步长序列的希尔排序不但比插入排序要快，甚至在小数组中比快速排序和堆排序还要快，但在涉及超大量数据时还是比不上快速排序。
  接下来还有，还有人发现，斐波那契数列除去0和1将剩余的数以黄金分割比的两倍的幂进行运算得到的数列：1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…也能让希尔排序在大数据样本中表现优异。
  故事估计还没有完，希尔排序的这个步长因子，仍像个神奇魔石一样，充满了魔力和未知，未来可能还会有惊喜！

  上边这一咕噜，也是从维基百科划拉的时候才知道的，细究还须翻墙绕大圈，感兴趣的可以去看看，有点超纲。以前，只是是依稀记得希尔排序这个时间复杂度是比较特殊，一点点印象。

  我们一般总结希尔排序的时间复杂度的时候，最好情况，还是认为数据本身就是有序的，不需要交换，只需要比较，则最好时间复杂度为O（n）；最坏情况，是每两个数都要比较并交换一次，则最坏情况下的时间复杂度为O（n²）；在总结这个平均的时候，我们说希尔排序的平均时间复杂度为O（n^1.3）。

2、 空间复杂度

  希尔排序算法，只需要一个变量用于协助两数交换，与数据大小无关，故认为希尔排序算法的空间复杂度为：O(1)。

2、稳定性

  我们通过上边的图解和程序可以看出，在希尔排序中，在分组排序的时候，等值元素大概率会前后来回交换位置，所以希尔排序是不稳定的算法。