看图说话排序算法之希尔排序

    希尔排序是最早突破O(n2)时间界限的一种排序算法，希尔排序算法是在插入排序算法的基础上进行改进的排序算法，上文描述了插入排序的基本实现过程，本文在上文基础上介绍希尔排序的基本原理。

一丶希尔排序算法基本原理

希尔排序又称为增量排序，该算法依据增量将待排序数组划分成不同子数组，并对每个子数组运用插入排序，最后对各个排序后的子数组进行一次插入排序，从而完成排序操作。希尔排序算法的实现流程如图所示:

图1 算法实现流程

下面通过一个例子，来描述希尔排序算法的具体实现过程，假设待排序数组满足int [] A = new int[]{4,5,7,3,2,8,9,16,13}。

1. 数组长度N=9，所以初始增量delta = N/2 = 4,依据增量delta可以将数组划分成如下子数组(长度为1的子数组不画，没有排序的必要)

   
   图2 delta=4时子数组划分情况

2. 依据增量划分子数组之后，对每个子数组进行直接插入排序，排序结果如下图所示:

   
   图3 delta=4时子数组排序情况
   

   从上图可以看到，对各个子数组进行插入排序，实质上也是对待排序数组一次顺序调整。

3. 经过上述两步之后，待排序数组由{4,5,7,3,2,8,9,16,13}调整到了{2,5,7,3,4,8,9,16,13}的顺序，接着对数组{2,5,7,3,4,8,9,16,13}重复上述两个步骤，此时增量delta =delta/2=2。划分子数组和排序情况分别如下图所示

   
   图4 delta=2时子数组划分情况
   图5delta=2时子数组排序情况
   

   结合步骤（1）和步骤（2）的描述，对比图3，图4的变化，不难看出该次排序的过程。随着增量delta的减小，子数组的数量越多，对上述过程细心的话，可以看出，假如不经过增量delta=4的排序过程，直接进入delta=2的排序过程，各个子数组需要调整的元素会增多，从这个角度来看delta=4的增量排序是为了delta=2的增量排序做铺垫。

4. 经过步骤（3）待排序数组由{2,5,7,3,4,8,9,16,13}的顺序调整至{2,3,4,5,7,8,9,16,13}。此时delta = delta/2 = 1。重复步骤（1）和步骤（2），由于次数delta=1,相当于对整个数组进行一次插入排序，排序结果如下图所表示。

   图6delta=1时排序情况
   观察图5中的待排序数组，不难发现经过增量delta=4，和delta=2的排序后，待排序数组已经基本有序了。由于插入排序在基本有序的前提下，时间消耗接近线性，所以这趟排序所用时间消耗比较小，可以说前面的所有的增量排序，都是为了优化最后这一次插入排序。
   总结：

5. 复杂度分析无从下手，没有插入排序那么直观。事实上希尔排序的时间复杂度分析是一件困难的事情。

6. 我的自身水平也有限，我也没有能力证明希尔排序的时间复杂度。只能描述希尔排序算法的一般实现过程

7. 可以推断希尔排序的效率依赖于delta增量，delta增量选取合适的话，可以优化不小的效率，对delta增量计算的方式有很多种，对此不做深入介绍，本文中描述的delta增量计算的方式称为希尔增量计算法。

8. 希尔排序算法优于时间复杂度是O（n²）的算法，但没有达到nlog（n）的时间界，希尔排序算法在适度规模的数据下排序具有较优的性能，比较常用。

二丶java代码实现

public class ShellSort {
    public static void main(String [] args){
        int [] data = new int[]{5,4,6,2,9,1,7};
        shellSort(data);
        for(int i =0;i<data.length;i++){
            System.out.println(data[i]);
        }
    }
    public static void shellSort(int [] data){
        //shell 排序的增量循环
        for(int delta=data.length/2;delta>0;delta=delta/2){
            for(int i=0;i<data.length-delta;i++){
                 int temp =data[delta+i];
                  int index =delta+i;
                  while(index-delta>=0&&data[index-delta]>temp){
                      data[index]=data[index-delta];
                      index=index-delta;
                  }
                  data[index] =temp;
                }
            }
        }
}

Reference:
[1] 数据结构与算法 java语言描述
[2] 原文博客链接