在shell排序中,建议使用插入排序对列表进行h排序3h+1
计算//1, 4, 13, 40, ...
起始值的最佳公式是h
的三分之一,如下所示,
int h = 1;
while(h < listSize/3){ // why N/3?
h = 3*h + 1
}
while(h >= 1){
//h-sort the array
// perform insertionSort
h = h/3;
}
问题:
要执行外壳排序,如何从数学上证明
listsize
(最大值)应小于h
? 最佳答案
如果在条件h
之后继续增加(h < listSize/3)
,h
变得大于listSize
,并且h排序没有意义-我们无法比较项A[i]
和A[i+h]
,因为第二个索引超出了列表范围。
关于c - 在Shell排序中进行h排序,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/41708290/