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

g99

辛苦

无心人

缺少分组排序和一步到位排序两个O(n)算法

gxqcn

对 shell_sort 算法复杂度有点疑问。

查中文网站，
有说 O(n^1.2) 的，有说 O(n^1.5) 的，楼主说 O(n^1.25)

检索外文网站：
http://www.iti.fh-flensburg.de/l ... n/shell/shellen.htm
里面则分了多种情况讨论，其中在 n=2^p3^q 序列中，复杂度为 O(n·log(n)²)

kon3155

缺少的还有很多呢，还少了Bucket sort ,external sorting，Counting sort，Binary tree sort，Topological sort，Cocktail sort，Comb sort，Bogosort ，等等
有兴趣的兄弟们帮忙完善一下吧，管理员可以修改我的帖子！
论坛修改帖子的时间限制有些太短了，只有12小时，最好72小时（大部分论坛是这样的）！

无心人

外部排序已经不重要了

kon3155

原帖由 gxqcn 于 2009-2-27 08:03 发表
对 shell_sort 算法复杂度有点疑问。

查中文网站，
有说 O(n1.2) 的，有说 O(n1.5) 的，楼主说 O(n1.25)

检索外文网站：
http://www.iti.fh-flensburg.de/l ... en/shell/shellen.ht ...

    　Shell排序的执行时间依赖于增量序列。
    　好的增量序列的共同特征：
　　① 最后一个增量必须为1；
　　② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
    　有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在n^1.25到1.6n^1.25之间

kon3155

推荐快速排序，因为
"Quicksort is a sorting algorithm whose worst-case running time is Θ(n²) 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

(这也是为什么快排占了两层楼的原因,呵呵 )

无心人

呵呵

快速排序和周建钦的超快速排序比较过么
（基于概率分布的排序数据信息和快速排序综合的一个算法）

kon3155

原帖由 无心人 于 2009-2-27 10:52 发表
呵呵

快速排序和周建钦的超快速排序比较过么
（基于概率分布的排序数据信息和快速排序综合的一个算法）

学习了，大家一起学习一下吧！

liangbch

在
大数据量排序算法 - 编程擂台 给出3篇排序算法的论文。他们是：
分段快速排序的改进
无符号整数按位快速排序算法
一种非比较分段排序算法的研究

  另外，这里贴出我收集的其他几篇关于排序算法的论文

一种改进后的基数排序算法.PDF
分档混合排序算法.PDF
基于数组的桶排序算法.PDF
三种排序法的优劣.PDF
任意分布数据的基数分配链接排序算法.PDF
按字节桶分配链接排序法.PDF
一种新的分“档”统计插入排序算法.PDF