Archive for 2014年12月

Shellsort

十二月 6, 2014

Shell是人名,不是bash这种shell。

事先确定一个单调递减且以1为终点的步长序列,以每个步长做一次插入排序。

计算量小于n^2,大概为n^{4/3}n^{6/5},与步长序列有关。

至今仍不知道最优步长选择是什么样的。