内部排序方法比较

前面章节学习的多种排序算法都属于内部排序算法，参与排序的数据都存储在内存中。分析排序算法的性能，一般从算法的时间复杂度、空间复杂度和稳定性三方面着手。为了方便对比分析，在表1中列出了多种算法的在时间、空间以及稳定性方面的性能。

表1 内部排序性能表

表1中根据排序算法的特点将排序算法划分为交换排序、插入排序、选择排序和其它排序方法。

根据算法的平均时间性能，又可以将算法分为三类：

（1）平方阶算法，平均时间性能为O(n2)。这种算法一般又称为简单排序算法，如冒泡排序、直接插入排序，是典型的简单排序算法。这种算法对空间的要求不高，但是时间性能不稳定，其时间性能取决于原始序列与最终求解序列的差别。当原始序列基本有序时，这两种算法的时间性能达到最高。

（2）线性对数阶的算法，平均时间性能为O(nlog2n)。这种算法是较复杂的排序算法，如快速排序、堆排序和归并排序。从表1中可以看出，这几种排序算法的时间性能比较稳定，除了快速排序，其它两种算法的最好和最坏情况有相同的时间复杂度。这几种排序算法对空间的要求也不同，其中堆排序所需辅助空间最少，快速排序所需辅助空间最多。

（3）线性阶的算法，平均时间性能为O(n)。当参与排序的数据其位数d和基数r为常量时，基数排序就是一种线性阶的算法。

在排序算法中，冒泡排序是最早出现的排序算法，这个算法通过多轮比较，逐步调整数据在序列中的位置，在每一轮调整中除了能使本轮的最值到达合适的位置，还能使其它数据在序列中逐渐有序。简单选择排序算法也是一种初级算法，同样要经过多轮比较，相比与冒泡排序，这个算法减少了数据交换，但是每一轮排序只对本轮的最值进行操作，对其它数据没有影响。这两种算法都是平方阶算法，时间性能都比较差。

直接插入排序算法是对冒泡排序算法的改进，这个排序算法将待排序序列中的数据逐个插入有序序列中，插入新数据后的有序序列仍保持有序。它比冒泡排序快，但是提升并不明显，仍然是一个平方阶算法。通常也不将这个算法使用在数据量较大的场合。

希尔排序通过将原始序列分组，对每个组进行直接插入排序。它的时间性能高于直接插入排序，通常认为其平均时间性能为O(n1.3)。希尔排序算法是第一个使排序算法时间效率突破平方阶的算法。

快速排序是交换排序的一种，它是对冒泡排序的改进，快速排序再次使排序算法的时间性能有所突破。但是快速排序算法提高了对空间的要求，算法实现中使用递归思想，不适合处理超大量数据。

归并排序采用分治法思想，先将序列逐层分解成小的序列，再对不可再分的小序列进行排序，之后将有序的小序列合并，完成对序列的排序。但是这个算法需要的内存空间比较多，并且算法中涉及递归，同样不适合处理超大量数据。

堆排序首先将所有数据构建称一个堆，将数据中的最值放置在堆顶，然后将堆顶输出，将最后一个叶子结点放在堆顶，再调用调整算法使当前的堆重新成为一个大顶堆或小顶堆，再次输出堆顶，通过不断地循环调整与输出来为所有数据排序。堆排序是最高效的选择排序算法，它的时间性能非常稳定，并且对空间要求也很低，所以堆排序非常适合处理超大量的数据。

基数排序是表1中唯一一个时间复杂度为线性阶的排序算法，其中的d为记录中关键字的位数，r为每一位关键字的最大范围。只是若要使用基数排序，首先要先分析数据的存储格式，所以一般只用它处理整数或者其它数据格式明显的数据。

除去时间性能和空间性能，有些应用场景还对算法的稳定性有所要求，此时算法的性能还要取决于实际应用场景对算法各种性能的要求。

没有绝对好用的排序算法，在选择排序算法时，应结合实际情境，选择合适的排序算法。