排序之希尔排序(shell sort)

506629361

　　前言
　　　　本篇博客是在伍迷兄的博客基础上进行的，其博客地址点击就可以进去，里面好博客很多，我的排序算法都来自于此；一些数据结构方面的概念我就不多阐述了，伍迷兄的博客中都有详细讲解，而我写这些博客只是记录自己学习过程，加入了一些自己的理解，同时也希望给别人提供帮助。
　　前提故事
　　　 　骚年在上次与博主进行了直接插入排序的讨论后，找到了博主，说：“博主，对于直接插入排序，我有重大的发现”，博主想了想，就问：“什么发现？”，骚年：“我发现了如下两点”
　　　　　　1）当序列的个数比较少时，直接插入排序效率高；这个好理解，个数比较少，那么插入的次数也就少了，博主就说：“恩，这个发现不难，却也需要细心”。
　　　　　　2）如果序列本身就是基本有序，那么直接插入排序效率高；博主：“嗯？”，骚年解释道：“你看直接插入排序的核心代码：”
　　



　　　　 for(int i=1; i<len; i++){                           
for(int j=i-1; j>=0&&arr[j]>arr[j+1]; j--){        
swap(arr,j,j+1);
}
}
　　骚年接着道：“如果序列有序，那么j>=0&&arr[j]>arr[j+1]条件就是不满足的，插入操作就不会执行，效率自然就高了。”
　　博主：“然后了？”。
　　骚年：“那么我们是不是可以在这两点上做点事，来提高直接插入排序在普通序列上的效率了？”。
　　上述两个条件过于苛刻，现实中记录少或者基本有序都属于特殊情，有条件当然是好，条件不存在，我们创造条件，也是可以去做的；骚年与博主进行了研究与讨论，我们可以对序列进行分组，分割成若干个子序列，然后对每个子序列分别进行直接插入排序，当整个序列都基本有序时，注意只是基本有序时，再对全体记录进行一次直接插入排序。
　　此时一定有人开始疑惑了。这不对呀，比如我们现在有序列是{5,3,7,9,1,6,4,8,2}，现在将它分成三组，{5,3,7}， {9,1,6}，{4,8,2}，哪怕将它们各自排序排好了，变成{3,5,7}，{1,6,9}，{2,4,8}，再合并它们成 {3,5,7,1,6,9,2,4,8}，此时，这个序列还是杂乱无序，谈不上基本有序，要排序还是重来一遍直接插入有序，这样做有用吗？需要强调一下， 所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间，像{2,1,3,6,4,7,5,8,9}这样可以称为基本有序了。 但像{3,5,7,1,6,9,2,4,8}这样的7在第三位，2在倒数第三位就谈不上基本有序。
        那么问题就来了，我们分割待排序记录的目的是减少待排序记录的个数，并使整个序列向基本有序发展。而如上面这样分完组后，就各自排序的方法达不到我们的要求。因此，我们需要采取跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。
　　基本思想
　　　　将整个序列按照相距某个“增量”进行拆分，然后逐个对子序列进行直接插入排序，使得得到的结果基本有序，最后对基本有序的序列进行一次直接插入排序，使得整个序列有序
　　代码实现
　　　　java实现





       /**
* 希尔排序
* @param arr 目标序列
*/
public static void shellSort(int[] arr){
int len = arr.length;
for(int gap=len/2; gap>=1; gap=gap/2){                    //拆分整个序列，元素间距为gap(也就是增量)
//对子序列进行直接插入排序
for(int i=gap+1; i<len; i++){
for(int j=i-gap; j>=0&&arr[j]>arr[j+gap]; j=j-gap){        
swap(arr,j,j+gap);
}
}
}
}   
View Code　　执行过程模拟
　　　　1）程序开始执行，初始序列为{5,3,7,9,1,6,4,8,2}，如下图：
　　　　2）初始gap=len/2=4
　　　　　　2.1）i=gap=4，初始j=0；比较arr[j]与arr[j+gap],即arr[0]与arr[4],如下图：
　　
　　　　　　　　j=j-gap=-4，跳出，i++，i=5
　　　　　　2.2）i=5，j=i-gap=1，arr[1]=3 < arr[5]=6,不交换数据，如下图：
　　　　　　
　　　　　　　　j=j-gap=-3,跳出，i++,i=6
　　　　　　2.3)同理，当i=6，7时，序列如下图：
　　

　　2.4）当i=8时，序列如下：

　　那么gap=4时，最终序列为

　　3）gap=gap/2=2
　　3.1)i=gap=2,j=i-gap=0,arr[0]=1 < arr[2]=4不交换，j=j-gap=-2，i++，此时序列为：

　　3.2）i=3，j=i-gap=1，arr[1]=3 < arr[3]=8,不交换，j=j-gap=-1，i++,此时序列为：

　　3.3）同理，i=4时：

　　3.4）i=5时：

　　3.5）i=6时：

　　3.6）i=7时：

　　3.7）i=8时：

　　4）gap=gap/2=1，此时



　　　　for(int gap=len/2; gap>=1; gap=gap/2){                    //拆分整个序列，元素间距为gap(也就是增量)
//对子序列进行直接插入排序
for(int i=gap; i<len; i++){
for(int j=i-gap; j>=0&&arr[j]>arr[j+gap]; j=j-gap){        
swap(arr,j,j+gap);
}
}

　　就是



            //对子序列进行直接插入排序
for(int i=1; i<len; i++){
for(int j=i-1; j>=0&&arr[j]>arr[j+1]; j=j-1){        
swap(arr,j,j+1);
}
}
　　相信大家都发现了，上面代码就是我们的直接插入排序，那么具体的模拟过程我也就不再赘述了，不懂的可以去看排序之直接插入排序
　　至此，整个序列就有序了。
　　难以理解之处
　　　 通过这段代码的剖析，相信大家有些明白，希尔排序的关键并不是随便的分组后各自排序，而是将相隔某个“增量”的记录组成一个子序列，实现跳跃式的移动，使得排序的效率提高。这里“增量”的选取就非常关键了，本例中是以gap=gap/2的方式选取增量的，可究竟应该选取什么样的 增量才是最好，目前还是一个数学难题，迄今为止还没有人找到一种最好的增量序列。不过大量的研究表明，当增量序列为dlta[k]=2t-k+1-1（0≤k≤t≤&lfloor;log2(n+1)&rfloor;）时，可以获得不错的效率。需要注意的是，增量序列的最后一个增量值必须等于1才行。