关于希尔排序
来源：2-7 更多关于O(n^2)排序算法的思考
SD_Kaden
2018-07-08
int h = n/3;
while( h < n/3 )//取区间的三分之一为增量
h = 3 * h + 1;//获得最大的三分之一增量
老师这段代码用 int h=n/3; 代替也能正确排序，为什么要加个while循环呢
写回答
1回答
-
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
加油！：）
012018-07-08
相似问题