排序算法小结

计算机科学的一个基本结论是：一个基于比较的排序算法不可能得到比O(nlogn)更快的性能。

排序算法按平均时间将排序分为四类：前三类也被称之为比较排序，前三类中其中 合并排序 和 堆排序是 渐进最优的，因为在 最坏情况下 达到了(O(nlgn))，而 快速排序在 平均情况下达到了(O(nlgn))！（来自算法导论 第八章 开始,1 实验证明 平均性能好  2 原地排序）

思考：快速排序的优势，有两点（CLRS第七章开始部分）
（1）平方阶(O(n2))排序， 一般称为简单排序，他们的  最好O(n)
    　例如直接插入、直接选择和冒泡排序；
（2）线性对数阶(O(nlgn))排序
    　如快速、堆和归并排序；

快速排序在平均情况下复杂性为O(nlogn)，最坏情况 O(n²)，最好O(nlogn)

堆排序和合并排序在最坏情况下复杂性为O(nlogn)。可见，合并排序和堆排序是比较排序算法中时间复杂度最优算法。

（3）O(n^1+￡)阶排序
    　￡是介于0和1之间的常数，即0<￡<1，如shell排序；
（4）线性阶(O(n))排序，关键字近似有序的记录
    　如桶、箱和基数排序。
桶排序：多了一个桶，每一个桶中还是用  插入排序！一般不用的，它假设 输入为 小范围，且接近均匀排序！
各种排序方法比较
     简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。

影响排序效果的因素
　　①待排序的记录数目n；
　　②记录的大小(规模)；
　　③关键字的结构及其初始状态；
　　④对稳定性的要求；
　　⑤语言工具的条件；
　　⑥存储结构；
　　⑦时间和辅助空间复杂度等。

不同条件下，排序方法的选择
(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
  当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
    　快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
    　堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
    　若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。

下面的 http://xfeng.bloghome.cn/posts/56646.html
结论:
   排序方法 平均时间 最坏时间 辅助存储
   简单排序 O(n2)  O(n2)      O(1)
   快速排序 O(nlogn) O(n2)     O(logn)
   堆排序 O(nlogn) O(nlogn)     O(1)
   归并排序 O(nlogn) O(nlogn)   O(n)= n/2+n/4+n/8+……+1,每一次递归都有一个 返回值
   基数排序 O(d(n+rd)) O(d(n+rd)) O(rd)
希尔排序（不稳定）

一、时间性能方面的例子

当待排记录序列按关键字顺序有序时
   直接插入排序和起泡排序能达到O(n)的时间复杂度;
   快速排序而言，时间性能蜕化为O(n2)，因此是应该尽量避免的情况。

简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
二、空间性能

指的是排序过程中所需的辅助空间大小。

1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O

(1)；

2. 快速排序为O(logn  )，为栈所需的辅助空间;

3. 归并排序所需辅助空间最多，其空间复杂度为O(n );

4.链式基数排序需附设队列首尾指针，则空间复杂度为O(rd  )。

三、排序方法的稳定性能

 快速排序和堆排序是不稳定的排序方法

快速排序每次将待排序数组分为两个部分，在理想状况下，每一次都将待排序数组划分成等长两个部分，则需要logn次划分。
而在最坏情况下，即数组已经有序或大致有序的情况下，每次划分只能减少一个元素，快速排序将不幸退化为冒泡排序，此时比插入排序还要差。所以快速排序时间复杂度下界为O(nlogn)，最坏情况为O(n^2)。在实际应用中，快速排序的平均时间复杂度为O(nlogn)。

快速排序在对序列的操作过程中只需花费常数级的空间。空间复杂度S(1)，这个子过程的空间可以忽略。
但需要注意递归栈上需要花费最少logn 最多n的空间。

排序法	平均时间	最差情形	稳定度	额外空间	备注
冒泡	O(n2)	O(n2)	稳定	O(1)	n小时较好
交换	O(n2)	O(n2)	不稳定	O(1)	n小时较好
选择	O(n2)	O(n2)	不稳定	O(1)	n小时较好
插入	O(n2)	O(n2)	稳定	O(1)	大部分已排序时较好
基数	O(logRB)	O(logRB)	稳定	O(n)	B是真数(0-9)， R是基数(个十百)
Shell	O(nlogn)	O(ns) 1	不稳定	O(1)	s是所选分组
快速	O(nlogn)	O(n2)	不稳定	O(nlogn)	n大时较好
归并	O(nlogn)	O(nlogn)	稳定	O(1)	n大时较好
堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n大时较好