排序算法小结

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

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

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

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

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

（3）O(n1+￡)阶排序
    　￡是介于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的空间。