看图说话排序算法之希尔排序
希尔排序是最早突破O(n2)时间界限的一种排序算法，希尔排序算法是在插入排序算法的基础上进行改进的排序算法，上文描述了插入排序的基本实现过程，本文在上文基础上介绍希尔排序的基本原理。
一丶希尔排序算法基本原理
希尔排序又称为增量排序，该算法依据增量将待排序数组划分成不同子数组，并对每个子数组运用插入排序，最后对各个排序后的子数组进行一次插入排序，从而完成排序操作。希尔排序算法的实现流程如图所示:
图1 算法实现流程
下面通过一个例子，来描述希尔排序算法的具体实现过程，假设待排序数组满足int [] A = new int[]{4,5,7,3,2,8,9,16,13}。
-
数组长度N=9，所以初始增量delta = N/2 = 4,依据增量delta可以将数组划分成如下子数组(长度为1的子数组不画，没有排序的必要)
图2 delta=4时子数组划分情况
-
依据增量划分子数组之后，对每个子数组进行直接插入排序，排序结果如下图所示:
图3 delta=4时子数组排序情况
从上图可以看到，对各个子数组进行插入排序，实质上也是对待排序数组一次顺序调整。
-
经过上述两步之后，待排序数组由{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的增量排序做铺垫。
-
经过步骤（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的排序后，待排序数组已经基本有序了。由于插入排序在基本有序的前提下，时间消耗接近线性，所以这趟排序所用时间消耗比较小，可以说前面的所有的增量排序，都是为了优化最后这一次插入排序。
总结： -
复杂度分析无从下手，没有插入排序那么直观。事实上希尔排序的时间复杂度分析是一件困难的事情。
-
我的自身水平也有限，我也没有能力证明希尔排序的时间复杂度。只能描述希尔排序算法的一般实现过程
-
可以推断希尔排序的效率依赖于delta增量，delta增量选取合适的话，可以优化不小的效率，对delta增量计算的方式有很多种，对此不做深入介绍，本文中描述的delta增量计算的方式称为希尔增量计算法。
-
希尔排序算法优于时间复杂度是O（n2）的算法，但没有达到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] 原文博客链接
