数据结构之排序的性能比较

一、前言
本文总结排序中的内部排序。内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。
二、正文
对于内排序来说，排序算法的性能主要是受3个方面影响：
1．时间性能

排序是数据处理中经常执行的一种操作，往往属于系统的核心部分，因此排序算法的时间开销是衡量其好坏的最重要的标志。在内排序中，主要进行两种操作：比较和移动。比较指关键字之间的比较，这是要做排序最起码的操作。移动指记录从一个位置移动到另一个位置，事实上，移动可以通过改为记录的存储方式来予以避免（这个我们在讲解具体的算法时再谈）。总之，高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。

2．辅助空间

评价排序算法的另一个主要标准是执行算法所需要的辅助存储空间。辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间。

3．算法的复杂性

注意这里指的是算法本身的复杂度，而不是指算法的时间复杂度。显然算法过于复杂也会影响排序的性能。

根据排序过程中借助的主要操作，我们把内排序分为：插入排序、交换排序、选择排序和归并排序。可以说，这些都是比较成熟的排序技术，已经被广泛地应用于许许多多的程序语言或数据库当中，甚至它们都已经封装了关于排序算法的实现代码。因此，我们学习这些排序算法的目的更多并不是为了去在现实中编程排序算法，而是通过学习来提高我们编写算法的能力，以便于去解决更多复杂和灵活的应用性问题。
三、性能比较

四、应用与讨论总结
1、若n较小（n<=50），则可以采用直接插入排序或者简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多，因而当记录本身信息量较大时，用简单选择排序较好。

2、若文件的初始状态已按关键字基本有序，则选择直接插入或者冒泡排序为宜。

3、若n较大，则应采用时间复杂度为O（nlogn）的排序方法：快速排序、堆排序或归并排序。快排被认为目前基于比较的内部排序法中最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短。

堆排序所需的辅助空间少于快排，并且不会出现快排可能出现的最坏情况，这两种排序都是不稳定的。若要求排序稳定且时间复杂度为O（nlogn），则可以选择归排序。

4、若n很大，记录的关键字位数较少且可以分解时，采用基数排序较好。

5、当记录本身信息量较大时，为避免耗费大量的时间移动记录。可用链表作为存储结构。