关于希尔排序

Question

    

int h = n/3;

    while( h < n/3 )//取区间的三分之一为增量

        h = 3 * h + 1;//获得最大的三分之一增量

老师这段代码用 int h=n/3; 代替也能正确排序，为什么要加个while循环呢 

Answer 1

liuyubobobo 2018-07-08 17:48:15

h的初始值是希尔排序划分每个子区间中的元素个数。在希尔排序的过程中，这个h值将按照某个规则（或者说是某个序列）逐渐减为1；这个序列，称为增量序列。

这段while循环，是让我们的h形成一个特殊的序列：1, 4, 13, 40, 121, 364, 1093...  可以参见课程代码第13行注释：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/02-Sorting-Basic/Course%20Code%20(C%2B%2B)/Optional-03-Shell-Sort/main.cpp

这个增量序列，是生成方式简单（代码简单），同时统计意义上，让希尔排序效率较高的一个增量序列：）

关于希尔排序的增量序列的更多探讨，可以参考这个问答中我给出的文献：）

https://coding.imooc.com/learn/questiondetail/33160.html

加油！：）

• 提问者 SD_Kaden #1

  谢谢老师。