内排序方法的选择规则

王明芳

摘要:内部排序的方法很多,基于不同的运行环境,各种方法有各自的优点和缺点。就全面性能而言,无法指明哪种排序方法是最好的。为了提高计算机对数据处理的工作效率,本文对各种排序的方法和对应的算法进行了比较,进而选出最为适合的算法。

关键词:内部排序;时间复杂度;空间复杂度

排序就是把一组记录(元素)按照某个域的值的递增或递减的次序重新排列的过程。内部排序指的是待排序的记录都存放在计算机内存中的排序过程。按排序的规则不同,可分为五类:插入排序、交换排序、选择排序、归并排序、基数排序。本文将对这五种排序方法进行比较,从而给出内排序的选择规则。

1基本思想

1.1插入排序

插入排序的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子文件中的适当位置,直到全部记录插入完成为止。插入排序方法有:直接插入排序和希尔排序。

1.2交换排序

交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。

1.3选择排序

选择排序的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。常用的选择排序方法有直接选择排序和堆排序。

1.4归并排序

归并排序是利用“归并”技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。这里,我们以两路归并方法做介绍。两路归并的基本思想是排序开始时将待排序列看成n个已排好序的子序列,每一个子序列中只含有一个记录。将两个相邻的子序按算法merge逐一两两合并,得到n/2个有序子序列。每个子序列中含有2个记录(最后一个可能只有1个记录的子序列),这是第一趟归并的结果。第二趟归并在第一趟归并的结果上进行,再将相邻的子序逐一两两合并,得n/2/2个有序子序列。如此类推,直到最后归并得到一个有序序列为止。

1.5基数排序

要了解基数排序,首先要了解桶式排序:如果我们有N个整数,范围从1到M(或从0到M-1),我们留置一个数组A,大小为M,并初始化为0。于是该数组有M个单元(我们称之为桶),开始他们都是空的。当数a被读入时,A[a]增1。当所有的输入被读进时,扫描数组,打印出排好序的表。这就是所谓的桶式排序。

当M很大N很小时,空间严重浪费。这就推广出基数排序。我们选取某个较小的数做为基数,比如10,那么我们就只需要10个桶。当M大于基数,我们采用多趟桶式排序。比如M=1000,那么我们需要3次桶式排序。具体做法是用最低有效位优先的方式,将各个数放入桶中;然后遍历各个桶依据次最低有效位来调整,依次类推直到最高有效位。这便是基数排序的基本思想。

2比较

排序在计算机程序设计中非常重要,上面讲述的各种排序方法各有其优缺点,适用的场合也不同。以下我们针对以上各种方法在时间复杂度、空间复杂度、稳定性及算法简单性等几方面进行比较。

2.1时间复杂度

从平均时间复杂度来考虑,直接插入排序、冒泡排序、直接选择排序是三种简单的排序方法,时间复杂度都为O(n2),而快速排序、堆排序、二路归并排序的时间复杂度都为O(nlog2n),希尔排序的复杂度介于这两者之间。

若从最好的时间复杂度考虑,则直接插入排序和冒泡排序的时间复杂度最好,为O(n),其它的最好情形同平均情形相同。

若从最坏的时间复杂度考虑,则快速排序的为O(n2),直接插入排序、冒泡排序、希尔排序同平均情形相同,但系数大约增加一倍,所以运行速度将降低一半,最坏情形对直接选择排序、堆排序和归并排序影响不大。

2.2空间复杂度

归并排序的空间复杂度最大,为O(n),快速排序的空间复杂度为O(log2n),其它排序的空间复杂度为O(1)。

2.3稳定性

直接插入排序、冒泡排序、归并排序是稳定的排序方法,而直接选择排序、希尔排序、快速排序、堆排序是不稳定的排序方法。

2.4算法简单性

直接插入排序、冒泡排序、直接选择排序都是简单的排序方法,算法简单,易于理解,而希尔排序、快速排序、堆排序、归并排序都是改进型的排序方法,算法比简单排序要复杂得多,也难于理解。

3选择规则

3.1根据时间/空间复杂度选择

对元素个数较多的排序,可以选快速排序、堆排序、归并排序,元素个数较少时,可以选简单的排序方法。尽量选空间复杂度为O(1)的排序方法,其次选空间复杂度为O(log2n)的快速排序方法,最后才选空间复杂度为O(n)二路归并排序的排序方法。

3.2一般性选择规则

待排序元素的个数n较大,排序码分布是随机,而对稳定性不做要求时,则采用快速排序为宜。待排序元素的个数n大,内存空间允许,且要求排序稳定时,则采用二路归并排序为宜。待排序元素的个数n大,排序码分布可能会出现正序或逆序的情形,且对稳定性不做要求时,则采用堆排序或二路归并排序为宜。待排序元素的个数n小,元素基本有序或分布较随机,且要求稳定时,则采用直接插入排序为宜。待排序元素的个数n小,对稳定性不做要求时,则采用直接选择排序为宜,若排序码不接近逆序,也可以采用直接插入排序。冒泡排序一般很少采用。基数排序可在O(d × n)时间内完成对n个记录的排序,d是指单逻辑关键字的个数,一般远少于n。但基数排序只适用于字符串和整数这类有明显结构特征的关键字。若n很大,d较小时,用基数排序较好。其它。前面讨论的排序算法,除基数排序外,都是在向量存储上实现的。当记录本身的信息量很大时,为避免大量时间用在移动数据上,可以用链表作为存储结构。插入排序和归并排序都易在链表上实现,但有的排序方法,如快速排序和堆排序在链表上却很难实现。

4结论

根据以上的论述及比较,我们看出,不同的运行环境,不同应用的需求,对算法的影响是很显著的。有些算法理论上是优化了,但实际运行时就不一定最好的。我们无法确定一种算法是否是最优的:有的适用于n较大的情况;有的适用于n较小的情况;有的适用于初始序列基本有序;而有的又在初始序列基本有序时效率最低。因此不能一概而论,应该具体情况具体分析。

参考文献

[1]严蔚敏,吴伟民数据结构(C语言版).北京:清华大学出版社 2000;

[2]Ellis Horowitz(美) 等. 译者:李建中等数据结构(C语言版) .北京 机械工业出版社 2006

[3]徐孝凯.数据结构实用教程 .北京 清华大学出版社2006.