查看原文
其他

漫画:什么是希尔排序?

CSDN云计算 2019-10-30

以下文章来源于程序员小灰 ,作者小灰

戳蓝字“CSDN云计算”关注我们哦!



—————  第二天  —————





————————————




让我们先来回顾一下插入排序


插入排序顾名思义,就是在排序的过程中,把数组的每一个元素按照大小关系,插入到前面有序区的对应位置。


比如下面数组中的元素3,按照大小关系,需要插入到前面有序区三个元素之前,而前面三个元素则相应向后挪动:






以此类推,插入排序一共会进行(数组长度-1)轮,每一轮的结果如下:



插入排序的平均时间复杂度是O(n^2)。这个排序算法并不复杂,但显然并不是一个高效的排序算法。

那么,怎样可以对插入排序算法做出优化呢?我们不妨从插入排序的两个特点入手:

1.在大多数元素已经有序的情况下,插入排序的工作量较小
这个结论很明显,如果一个数组大部分元素都有序,那么数组中的元素自然不需要频繁地进行比较和交换。

2.在元素数量较少的情况下,插入排序的工作量较小
这个结论更加显而易见,插入排序的工作量和n的平方成正比,如果n比较小,那么排序的工作量自然要小得多。



如何对原始数组进行预处理呢?聪明的科学家想到了一种分组排序的方法,以此对数组进行一定的“粗略调整”。


所谓分组,就是让元素两两一组,同组两个元素之间的跨度,都是数组总长度的一半,也就是跨度为4。



如图所示,元素5和元素9一组,元素8和元素2一组,元素6和元素1一组,元素3和元素7一组,一共4组。


接下来,我们让每组元素进行独立排序,排序方式用直接插入排序即可。由于每一组的元素数量很少,只有两个,所以插入排序的工作量很少。每组排序完成后的数组如下:


这样一来,仅仅经过几次简单的交换,数组整体的有序程度得到了显著提高,使得后续再进行直接插入排序的工作量大大减少。这种做法,可以理解为对原始数组的“粗略调整”。


但是这样还不算完,我们可以进一步缩小分组跨度,重复上述工作。把跨度缩小为原先的一半,也就是跨度为2,重新对元素进行分组:



如图所示,元素5,1,9,6一组,元素2,3,8,7一组,一共两组。

接下来,我们继续让每组元素进行独立排序,排序方式用直接插入排序即可。每组排序完成后的数组如下:



此时,数组的有序程度进一步提高,为后续将要进行的排序铺平了道路。

最后,我们把分组跨度进一步减小,让跨度为1,也就等同于做直接插入排序。经过之前的一系列粗略调整,直接插入排序的工作量减少了很多,排序结果如下:



让我们重新梳理一下分组排序的整个过程:





像这样逐步分组进行粗调,再进行直接插入排序的思想,就是希尔排序,根据该算法的发明者,计算机科学家Donald Shell的名字所命名。


上面示例中所使用的分组跨度(4,2,1),被称为希尔排序的增量,增量的选择可以有很多种,我们在示例中所用的逐步折半的增量方法,是Donald Shell在发明希尔排序时提出的一种朴素方法,被称为希尔增量




  1. public static void sort(int [] array){



  2. //希尔排序的增量



  3. int d=array.length;



  4. while(d>1) {



  5. //使用希尔增量的方式,即每次折半



  6. d=d/2;



  7. for(int x=0;x<d;x++) {



  8. for(int i=x+d;i<array.length;i=i+d) {



  9. int temp=array[i];



  10. int j;



  11. for(j=i-d;j>=0&&array[j]>temp;j=j-d) {



  12. array[j+d]=array[j];



  13. }



  14. array[j+d]=temp;



  15. }



  16. }



  17. }



  18. }




  19. public static void main(String [] args)



  20. {



  21. int[] array = {5,3,9,12,6,1,7,2,4,11,8,10};



  22. sort(array);



  23. System.out.println(Arrays.toString(array));



  24. }







看看上面这个数组,如果我们照搬之前的分组思路,无论是以4为增量,还是以2为增量,每组内部的元素都没有任何交换。一直到我们把增量缩减为1,数组才会按照直接插入排序的方式进行调整。

对于这样的数组,希尔排序不但没有减少直接插入排序的工作量,反而白白增加了分组操作的成本。



如何为希尔排序选择更有效的增量方式呢?


为了保证分组粗调没有盲区,每一轮的增量需要彼此“互质”,也就是没有除1之外的公约数。


于是,人们相继提出了很多种增量方式,其中最具代表性的是Hibbard增量Sedgewick增量


Hibbard的增量序列如下:
1,3,7,15......
通项公式 2^k-1
利用此种增量方式的希尔排序,最坏时间复杂度是O(n^(3/2))


Sedgewick的增量序列如下:
1, 5, 19, 41, 109......
通项公式 9*4^k - 9*2^k + 1 或者 4^k - 3*2^k + 1
利用此种增量方式的希尔排序,最坏时间复杂度是O(n^(4/3))

关于这两种增量方式的时间复杂度,有些需要很复杂的数学证明,有些是人们的大致猜想,大家暂时不用纠结。


上面数组当中,有两个元素5,绿色的5在前,橙色的5在后。


假如我们按照希尔增量分组,第一轮粗调(增量为4)之后,绿色的元素5会跟元素4交换,换到橙色的5后面:



第二轮粗调(增量为2)之后:



最终排序结果:



相同的元素5,在排序之后改变了次序,由此可见希尔排序是一个不稳定排序。






福利
扫描添加小编微信,备注“姓名+公司职位”,入驻【CSDN博客】,加入【云计算学习交流群】,和志同道合的朋友们共同打卡学习!



推荐阅读:
真香,朕在看了!

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存