辛苦:lol
缺少分组排序和一步到位排序两个O(n)算法
对 shell_sort 算法复杂度有点疑问。
查中文网站，
有说 O(n1.2) 的，有说 O(n1.5) 的，楼主说 O(n1.25) :Q:
检索外文网站：
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm
里面则分了多种情况讨论，其中在 n=2p3q 序列中，复杂度为 O(n·log(n)2)
缺少的还有很多呢，还少了Bucket sort ,external sorting，Counting sort，Binary tree sort，Topological sort，Cocktail sort，Comb sort，Bogosort ，等等
有兴趣的兄弟们帮忙完善一下吧，管理员可以修改我的帖子！
论坛修改帖子的时间限制有些太短了，只有12小时，最好72小时（大部分论坛是这样的）！
外部排序已经不重要了
原帖由 gxqcn 于 2009-2-27 08:03 发表 http://bbs.emath.ac.cn/images/common/back.gif
对 shell_sort 算法复杂度有点疑问。
查中文网站，
有说 O(n1.2) 的，有说 O(n1.5) 的，楼主说 O(n1.25) :Q:
检索外文网站：
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.ht ...
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在n1.25到1.6n1.25之间
推荐快速排序，因为
"Quicksort is a sorting algorithm whose worst-case running time is Θ(n2) on an input array of n numbers. In spite of this slow worst-case running time, quicksort is often the best practical choice for sorting because it is remarkably efficient on the average: its expected running time is Θ(n lg n), and the constant factors hidden in the Θ(n lg n) notation are quite small. It also has the advantage of sorting in place (see page 16), and it works well even in virtual memory environments.”
------------- Introduction.to.Algorithms,.Second
(这也是为什么快排占了两层楼的原因,呵呵:) )
呵呵
快速排序和周建钦的超快速排序比较过么
（基于概率分布的排序数据信息和快速排序综合的一个算法）
原帖由 无心人 于 2009-2-27 10:52 发表 http://bbs.emath.ac.cn/images/common/back.gif
呵呵
快速排序和周建钦的超快速排序比较过么
（基于概率分布的排序数据信息和快速排序综合的一个算法）
学习了，大家一起学习一下吧！
在
大数据量排序算法 - 编程擂台 给出3篇排序算法的论文。他们是：
分段快速排序的改进
无符号整数按位快速排序算法
一种非比较分段排序算法的研究
另外，这里贴出我收集的其他几篇关于排序算法的论文
一种改进后的基数排序算法.PDF
分档混合排序算法.PDF
基于数组的桶排序算法.PDF
三种排序法的优劣.PDF
任意分布数据的基数分配链接排序算法.PDF
按字节桶分配链接排序法.PDF
一种新的分“档”统计插入排序算法.PDF