算法导论-排序

        排序被认为是算法研究中最基础的问题。常说的排序算法有插入排序、归并排序、堆排序、快速排序、计数排序、基数排序和桶排序。

        其中插入排序、归并排序、堆排序和快速排序都是通过比较完成排序的。我们称这类排序为比较排序。算法导论中给出了相关证明：比较排序的最坏情况都要讲过nlgn次比较。因此归并排序和堆排序是渐进最优的，并且已知的比较排序最多就是在常数因子上超过了它们。

        其中计数排序、基数排序和桶排序都属于线性时间排序，这类排序不是通过比较来进行排序的。因此下界nlgn不适用于它们。

1.插入排序

   最坏情况下时间复杂度为n2，由于插入排序的内层循环紧凑，因此对于小规模的输入是一种非常快的原址排序方法。

（如果输入数组中仅有常数个元素要在排序中存储在数组之外，则称算法为原址的。我的理解：这是基于Cache命中给出的简易解释。）

2.归并排序

具体算法在《算法导论-分治法》中有介绍。归并排序较插入排序有更好的渐进运行时间nlgn，但是由于Merger过程不是原址的

3.堆排序

堆排序的时间复杂度是nlgn，但与归并排序不同，堆排序属于原址排序。“堆”是一种数据结构，这一词就是源于堆排序，但是目前被很多地方使用，且意思也发生了变化。

（1）“堆”是什么：

        在堆排序算法中，通常使用最大堆，而最小堆主要用于构造优先队列。

（2）堆排序

4.快速排序

与归并排序一样，快速排序利用了分治的思想。下列是对一个数组A[p,r]进行快速排序的三步分治过程：

举例子说明如下：

5.计数排序

6.基数排序

7.桶排序