原帖由 kon3155 于 2009-2-27 10:21 发表 http://bbs.emath.ac.cn/images/common/back.gif
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验， ...
原帖中这句：
已知的最好序列是{1, 4, 10, 23, 57, 132, 301, 701, 1750，...}。
的出处是哪里？
对于增量序列$\frac{3^k - 1}{2}$ TACP vol. 3 5.2.1中给出的是$O(N^{1.5})$，同时我也找到"对于$N<6000$，复杂度近似于$O(N^{1.25})$"这样的描述，但是都是对$\frac{3^k - 1}{2}$这个序列来说的，没有看到{1, 4, 10, 23, 57, 132, 301, 701, 1750，...}这个序列的证明。
本站较注重知识产权。如转载请注明出处。
如果我没弄错的话，2楼的插入排序应该来自维基百科-插入排序。
原帖由 liangbch 于 2009-2-27 12:56 发表 http://bbs.emath.ac.cn/images/common/back.gif
本站较注重知识产权。如转载请注明出处。
如果我没弄错的话，2楼的插入排序应该来自维基百科-插入排序。
本帖所有的内容均来自维基百科，我现在已经不能修改主题贴了，版主帮我改一下吧！
bogo sort类似扔纸牌，一把扔下去
排好了算结束
没排好，接着扔
o(n * n!)的复杂度
太强了，收藏了