基础算法学习——排序算法概述

fallening

原帖由 kon3155 于 2009-2-27 10:21 发表



    　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，...}这个序列的证明。

liangbch

本站较注重知识产权。如转载请注明出处。
如果我没弄错的话，2楼的插入排序应该来自维基百科-插入排序。

kon3155

原帖由 liangbch 于 2009-2-27 12:56 发表
本站较注重知识产权。如转载请注明出处。
如果我没弄错的话，2楼的插入排序应该来自维基百科-插入排序。

本帖所有的内容均来自维基百科，我现在已经不能修改主题贴了，版主帮我改一下吧！

无心人

bogo sort类似扔纸牌，一把扔下去
排好了算结束
没排好，接着扔

o(n * n!)的复杂度

wayne

太强了，收藏了