在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/

10-11 22:44
查看更多