排序算法 归纳总结

一、直接插入排序、冒泡排序和简单选择排序是最基本的排序方法，它们主要用于元素个数n（n<10000）不是很大的情形。

它们的平均复杂度均为O(n^2)，实现也比较简单。

1、直接插入排序对于规模很小的元素序列（n<=25）非常有效。它的时间复杂度与待排序元素序列的初始排列有关。在最好情况下，直接插入排序只需要n-1次比较就可以完成，而且不需要交换操作。在平均情况下和最差情况下，直接插入排序的比较和交换操作都是O(n^2).

2、冒泡排序在最好的情况下只需要一趟排序过程就可以完成，此时只需要n-1次比较操作，不需要交换操作。

3、简单选择排序的关键字比较次数与待排序元素序列的初始排序无关，其比较次数总是O（n^2），但元素移动次数则与待排序元素序列初始排列有关，最好情况下数据不需要移动，最坏情况下元素移动次数不超过3（n-1）次。

从空间复杂度来看，这三种基本的排序方法除了一个辅助元素外，都不需要额外的空间，从稳定性来看，直接插入排序和冒泡排序是稳定的，但简单选择排序不是。

二、对于中等规模的元素序列（n<=1000）,希尔排序是一种很好的选择。

在希尔排序中，开始增量较大，分量较多，每个组内的记录数较少，因而记录的比较和移动次数较少，且移动距离较远；到后来步长越小（最后一步为1），分组越少，每个组内的记录数也越多，但同时记录次数也越来越接近有序，因而记录的比较和移动次数也都比较少。从理论上和实验上都已证明，在希尔排序中，记录的总的比较次数和总的移动次数比直接插入排序时少的多，特别是当n越大时效果越明显。而且希尔排序代码简单，基本不需要什么额外内存，但希尔排序是一种不稳定的排序算法。

三、对于元素个数n很大的情况，可以采用快排、堆排序、归并排序或基数排序，其中快速排序和堆排序都是不稳定的，而归并排序和基数排序是稳定的排序算法。

1、快速排序是最通用的高效的内排序算法，特别是它的划分思想经常在很多算法设计题中出现。平均情况下它的时间复杂度为O(nlog2N)，一般情况下所需要的额外空间也是O(log2N)。但是快速排序在有些情况下也可能退化（例如元素序列已经有序时），时间复杂度会增加到O(n^2),空间复杂度也会增加到O(n)。但是我们可以通过“三者取中”法来避免最坏情况的发生。

2、堆排序也是一种高效的内排序算法，它的时间复杂度是O(nlog2N)，而且没有什么最坏情况会导致堆排序的运行明显变慢，而且堆排序基本不需要额外的空间。但堆排序不太可能提供比快速排序更好的平均性能。

3、归并排序是一个重要的高效排序算法，它的一种重要特性是性能与输入元素序列无关，时间复杂度总是O(nlog2N)，归并排序的主要缺点是需要O(n)的额外存储空间。

基数排序是一种相对特殊的排序算法，这类算法不仅是对元素序列关键字进行比较，更重要的是它们对关键字的不同部分进行处理和比较。虽然基数排序具有线性增长的时间复杂度，但是由于在常规编程环境中基数排序的线性时间开销实际上不比快速排序的时间开销小并且由于基数排序基于的关键字抽取算法受到操作系统和排序元素的影响，其适应性远不如普通的进行比较和交换操作的排序方法。因此在实际工作中，常规的高效排序算法如快速排序的应用要比基数排序广泛得多。基数排序需要的额外存储空间包括和待排序元素规模相同的存储空间以及与基数数目相等的一系列桶（一般用队列实现）。

四、混合使用

我们还可以把不同的排序算法混合使用，这也是得到普遍应用的一种算法改进方法，例如可以将直接插入排序集成到归并算法中。这种混合算法能够充分发挥不同算法各自的优势，从而在整体上得到更好的性能。