希尔排序就是这么容易

welcome rodert
一希尔排序（Shell's Sort）

最近在看一些基础的排序算法，虽是老生常谈，但有些文章也是说的不清不楚、晦涩难懂，今天就用最通俗易懂的描述一下这个算法，这篇聊一下希尔排序，希尔排序是十大基础排序算法中的一种，它是插入排序的一种优化。

相关阅读：插入排序就是这么容易

一介绍
【百度百科】：希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

实质：

        先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

读到这里还不是太明白，没关系，下面会详细分解整个过程

一实现

算法描述：

基本思想：（这个很重要）

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。

我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

图片来源网络(认真分析这张图)

希尔排序流程图

Java代码实现

下面提供俩种实现方式

方法一

• /** * 希尔排序 针对有序序列在插入时采用交换法 * @param arr */ @Test //希尔排序 void ShellSSort(){ int[] arr = {3, 5, 2, 1, 4};

        //增量gap，并逐步缩小增量        for(int gap=arr.length/2;gap>0;gap/=2){            //从第gap个元素，逐个对其所在组进行直接插入排序操作            for(int i=gap;i<arr.length;i++){                int j = i;                while(j-gap>=0 && arr[j]<arr[j-gap]){                    //插入排序采用交换法                    swap(arr,j,j-gap);                    j-=gap;                }            }        }        System.out.println(Arrays.toString(arr));    }    /**     * 交换数组元素     * @param arr     * @param a     * @param b     */    public static void swap(int []arr,int a,int b){        arr[a] = arr[a]+arr[b];        arr[b] = arr[a]-arr[b];        arr[a] = arr[a]-arr[b];    }

方法二

   /**     * 希尔排序 针对有序序列在插入时采用移动法。     * @param arr     */    @Test        //希尔排序    void ShellSSort2(){        int[] arr = {3, 5, 2, 1, 4};
        //增量gap，并逐步缩小增量        for(int gap=arr.length/2;gap>0;gap/=2){            //从第gap个元素，逐个对其所在组进行直接插入排序操作            for(int i=gap;i<arr.length;i++){                int j = i;                int temp = arr[j];                if(arr[j]<arr[j-gap]){                    while(j-gap>=0 && temp<arr[j-gap]){                        //移动法                        arr[j] = arr[j-gap];                        j-=gap;                    }                    arr[j] = temp;                }            }        }        System.out.println(Arrays.toString(arr));    }