排序算法的性能分析

贾丹+张兴

摘要：排序是计算机数据处理中的一种重要操作。在简单地讨论直接插入排序、简单选择排序、二路归并排序、堆排序、快速排序等不同排序算法的思想及具体实现过程的基础上，针对记录数据分布无规律、记录初始有序或基本有序、从n个记录中选择前k项（n值较大）等不同的数据分布形式，通过详细的实验测试，对不同的排序算法做了细致的性能分析，从而实现在不同的数据分布下，提高排序算法的效率。

关键词：时间复杂度；快速排序；归并排序；完全二叉树；深度

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2015）26-0075-03

Performance Analysis of Sort Algorithm

JIA Dan， ZHANG Xing

（School of Electronic and Information Engineering， Liaoning University of Technology， Jinzhou 121001， China）

Abstract： Sort is a important operation in computer data processing.Based on disscussing briefly the idea and implementation process of different sort algorithm about straight insertion sort，quick sort，simple selection sort，heap sort and merging sort，a detailed performance analysis is finished according to experiment test for different cases including record data distribution without regular pattern， initial record order or basic order and select k items from n records（n is large） and so on.It is achieved that how to improve sort algorithm efficiency for different data distribution.

Key words：time complexity；quick sort；merging sort；complete binary tree；depth

排序是计算机程序设计中非常重要的操作之一，在系统的开发过程中，经常会涉及对数据的排序。所谓排序，就是将记录按关键字的大小排列成一个非递减或非递增有序的序列。排序的方法有很多，常见的有插入排序、选择排序、归并排序、堆排序、快速排序、希尔排序等多种排序方法[1]。

在排序过程中，由于待排序数据的分布、表长、数据的特征以及不同的排序方法实现的过程不尽相同，所以排序方法的效率也不相同。本文针对不同的待排序记录序列，详细地阐述了不同排序算法的效率，系统地分析了如何针对不同的初始待排序列选择合适的排序算法，从而达到排序效率的最优。

1 不同排序算法的思想及具体实现

1.1 直接插入排序

直接插入排序是一种简单的排序方法，其基本思想是依次将待排序记录按照关键字的值插入到当前的有序表中。初始有序表中只含第1个记录，然后依次将第2、3…...n个记录逐个插入，经过n-1趟排序后，得到一个长度为n的有序表。在排序过程中比较次数最大值和最小值分别为（n+4）（n-1）/2和n-1，所以直接插入排序的时间复杂度为O（n2） [2]。

1.2 快速排序

快速排序是一种先进的排序方法，其基本思想是从待排记录中选择一个（通常第1个）记录作为枢轴，以该记录的关键字值为基准，将待排记录分成独立的两个子序列，其中一个子序列关键字的值均比枢轴记录的大，另一个子序列关键字的值均比枢轴记录的小。如初始序列为{90，63，21，33，45，95，120，10}，则经过一趟快排后，序列变成{10，63，21，33，45}90{120，95}，前一个子序列关键字的值均比90小，后一个均比90大。完成一趟快排后，再分别选取前后两个子序列中的第1个记录作为枢轴，重复上述过程，直至所有记录有序为止。

1.3 堆排序

堆排序也是一种先进的排序方法，从排序方法上来说，它是一种选择排序的方法。堆排序是利用堆的特性进行排序。堆排序的思想是首先根据排序要求建立一个堆，输出堆顶（最小或最大）后，调整剩余元素成为一个新堆，这个过程称之为筛选。之后，再输出筛选后的新的堆顶（次小或次大），重复上述过程，直到输出所有元素，此时按顺序输出的各堆顶的值就是一个有序序列。

除了上述的直接插入排序、快速排序、堆排序外，简单选择排序、二路归并排序都是常见的排序方法。不同排序算法的时间复杂度如表1所示。

2 不同数据分布时排序算法的性能分析

当待排序记录分布不同、数据特征不同时，排序算法的性能也不尽相同，不能一概而论。下面就待排记录几种不同的情况做详细分析。

2.1 待排记录数据分布无规律

如果待排记录杂乱无章，也就是数据的分布没有任何规律，从前面的分析，可以得出结论，快速排序所花费的时间的常数因子k值最小[3]，所花费的时间最短，此时快速排序的性能最优，被认为是效率最高的排序算法。下面图1所示是8个待排记录经过三趟快排就完成了整个排序过程。

对于快速排序，两边的两个子序列长度不一定是相同的，如果两个序列的长度相同或大致相同的话，速度会更快，效率会更高。

2.2 待排记录初始有序或基本有序

如果待排记录有序时，快速排序反而失去了它的优势，蜕化为冒泡排序，如图2所示。

从图2可以看出，当待排记录初始有序时，快速排序每趟只是把枢轴记录归入到有序表，其他记录仍在无序区中，已完全失去了快速排序的优势，时间复杂度也退化为O（n2） [4]，所以此时选择快速排序是非常不可取的。

如果选择堆排序、二路归并排序等先进的排序方法，它们的性能是不受待排数据影响的，均为O（nlog2n）。如果选择简单选择排序，在初始有序的情况下，虽然数据记录移动的次数为0，但对于数据比较次数，不受初始有序的影响，没有发生任何改变，仍为n（n-1）/2，所以时间复杂度仍为O（n2） [5]。

对于初始有序的待排记录，通过前面的分析，采用直接插入排序更快，在排序过程中，经过n-1趟排序，每趟均是待插记录和当前有序表中最后一个记录比，待插记录总是大于当前有序表中最后一个记录，所以比较一次就结束，共n-1次比较，且不需记录移动，记录次数为0。此时直接插入排序时间复杂度为O（n）级，待排记录初始有序时不同排序算法的性能比较见表2所示。

从表2可以看出，当初始有序时，直接插入排序需要比较的次数最少，性能最优，效率最高。

通过上面的分析发现一个问题：如何判定待排数据的分布特征，从而选择相应的高效的排序算法。数据分布的特征，我们也可以通过所有相邻数据的比较来实现，如果前者比后者小的记录数目占的比重较大，其有序高较高；反之则有序程度低，数据分布没有规律，通过数据的有序度来选择相应的排序算法提高效率。

2.3 从n个记录中选择前k项（n值较大）

如果待排记录的n值很大，特别是只要前若干个数据时，堆排序比较适合。例如要得到1000个数据记录中的前8个，在上述的排序方法中，堆排序的效率是最高的。对于快速排序、二路归并排序和直接插入排序，它们必须在得到整个有序序列后才能得到前8位，也就是说，需要先把1000个数据进行完整的排序，得到它们的有序序列后再从中取出前8位，可想而知，所花费的时间是相当长的。

简单简单选择排序和堆排序不必如此，它们在经过若干趟排序后可以得到部分有序子序列。对于简单选择排序，第一趟从n个元素中选择最小的需要n-1次比较；第二趟从n-1个元素中选择最小的需要n-2次比较…...，如果选择出前8名，则需八趟排序，共需的比较次数为（n-1）+（n-2）+…...（n-8）=8n-36次。在堆排序中，对于深度为k的堆，初始建堆需要4n次比较[6]，以后每次从堆中筛选中一个最小值需比较2（k-1）次。由完全二叉树的性质，得到k=└log2n┘+1，n值依次从n-1开始递减1，由于递减1对n值影响不大，可以均用n来表示堆中元素个数。则得到前8名需要建堆一次，筛选七次，比较次数小于4n+2（k-1）*7，k=└log2n┘+1=└log21000┘+1=10，经过推导，可以得出比较次数小于4n+126，与简单选择排序的8n-28次比较相比，少了大约4000次。表3列出了不同的排序方法从n个记录中选择前k项（例如k=8）时所需进行的比较次数，经过数据分析，可以得出，堆排序初始建堆时需要较多的比较次数，但在以后的每次筛选过程中，比较次数会发生质的减少，大大提高排序速度，所以，堆排序对于待排记录的n值很大的情形，效率非常高。

3 结束语

排序是计算机系统开发过程中，非常普遍又非常重要的操作之一，是将一组记录的任意序列按关键字大小重新排列成为一个有序序列。本文详细地讨论了直接插入排序、简单选择排序、二路归并排序、堆排序、快速排序等几种常见的排序方法的思想、排序过程及算法实现，系统地分析了当数据分布没有规律、记录初始有序或基本有序、记录数目多等几种情况下，不同的排序算法的性能。最终实现在不同的数据分布下，如何选择高效率的算法，使得排序效率最高，最节省时间。

参考文献：

[1] 严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2008.

[2] 于晓敏，袁琪.数据结构与算法[M].北京：北京航空航天大学出版社，2010.

[3] 杨晓波.算法时间复杂性分析综述[J].西藏大学学报：自然科学版 ，2011，26（1）： 87-90.

[4] 吕国英.算法设计与分析[M].北京：清华大学出版社，2009.

[5] 刘模群.排序算法时间复杂度研究[J].软件导刊，2012，11（6）： 35-37.

[6] 梁利刚，易超，杨绣丞， 郝树伟.静态排序算法设计与分析[J].计算机应用与软件，2012，29（3）： 283-286.