学文网摘 要:主要讨论数据结构中的内排序和外排序。通过讨论两者之间的区别来对内外排序进行深入讨。比较了多种内排序的方法,从时间复杂度、空间复杂度和稳定性上一一做了详细探讨并列表比较。
关键词:数据结构;内排序;外排序;存储器;时间复杂度;空间复杂度
中***分类号:TP
文献标识码:A
文章编号:1672-3198(2010)05-0327-02
排序是一种计算机必不可少的操作,其功能就是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。而排序分为外排序和内排序,两者固然存在着一定的区别。下面将通过分析二者区别来进一步对内外排做深入探讨。
区别之一,就是外排序和内排序所设计的存储器的不同。一般情况下,内部排序中待排序的文件较小。之所以称之为“内”是因为排序是在内存中完成的,文件一般可以一次在内存中排序。而一般外部排序中待排序的文件较大,不存储于内存而存储于外存,且不能一次调入进入内存。对此计算机所采取的策略是将文件中的数据分段输入内存,在内存中采用内排序的方法对其进行排序,这样完成排序后的文件段称为归并段,然后在将其写回外存,这样在外存中形成许多初始归并段。然后对这些归并短采用某种归并方法,并进行多遍归并,似的已经排序好的归并段逐渐扩大,最后在外存上形成整个文件的单一归并段,也就完成了这个文件的外排序。概括起来说,就是“内排序在内存上排序,外排序借助内排序通过调用间接完成外存上的排序”。
区别之二,除了存储器的不同,内排序和外排序所采用的存储方式也是不同的。内排序主要使用三种存储方式,一种连续地址的方式,即文件在内存中采用连续地址的方式;一种是静态链表的方式,采用链表的方式,实现“逻辑”上的连续存储。且链表使得存储一目了然,简单易懂;还有一种,就是指示各个记录存储位置的地址向量。
而对于外排序而言,主要使用两种存储方式。一种是磁盘存储器,一种是磁带存储器。磁盘存储器一般分为硬盘和软盘,是一种直接存取的存储设备,即访问存储在磁盘上的文件中的任何一条记录所花费的时间几乎相同,而不是像磁带存储器那样是顺序存储。磁盘,也就是和光盘一样,是一个扁平的圆盘,上面有很多磁道,信息就存储在磁道上。磁道这是磁盘上的很多同心圆,计算机根据磁盘上深浅不一的凹槽才进行信息识别。磁盘又有固定头盘和活动头盘的区别。所谓固定,就是每一个磁道上都有***的磁头来进行识别,而活动头盘也就是说其磁头是可以移动的。因此访问磁盘的时候,必须先找到柱面,然后移动磁头到柱面上,并将要访问的信息转到磁头下面,最后对信息进行读写。而磁带存储器也是比较常见的。
区别之三,内排序和外排序的方法即所采用的策略不同。内排序主要分为五大类,分别为插入排序、选择排序、交换排序、基数排序、归并排序。其中插入排序又分为直接插入排序、折半插入排序、2-路插入排序、表插入排序和希尔(shell)排序。选择排序又分为简单选择排序、树形选择排序和堆排序。交换排序分为冒泡排序和快速排序。归并排序又分为二路归并排序和多路归并排序。而外排序最常用的是归并排序法。主要分为多路归并排序和置换-选择排序两种,其主要的排序方法结构***如下***1、2所示:
在多路归并排序法中,一般使用的两个概念叫做胜者树和败者树。败者树是一课完全二叉树,其中每个结点的关键字(键值)取决于它的两个子节点中的关键字中的较小值(也就是胜者),然后就像淘汰赛一样,胜者进入下一轮的比赛,依次选取最小者,然后根节点的值最小。而胜者树的概念和败者树是相对的,它们之间的区别在于一个选择了胜者(关键字小),一个选择了败者(关键字大),其他的原理基本相同。例如下***3所显示的败者树:
上***中使用败者树原理,首先从根结点中选取关键字较小的一个,“进入下一轮的PK”,然后根节点取最小的值。在后面的应用中,往往把根节点的值输出并用一个新的元素替代,要求构成新的败者树,这是只需要在原来的败者树的基础上进行调整即可。
而在外排序中的置换-选择排序方法,其基本思想是先从输入文件中读取N个记录到内存工作区,然后选这N个记录中键值最小的记录写到输出文件中。如果新读入的记录的键值小于刚写到输出文件的键值,则该记录应归于下段,可在工作区中给记录加标志以示区别;如果新读入的记录的键值大于刚写到输出文件的键值,则记录归入当前段。然后一直重复操作,一直到工作区为空。置换-选择排序示意***如下***4所示:
***4
相对与外排序,内排序的方法就相当之多了,本文中就分了五大类:插入排序、交换排序、选择排序、归并排序和基数排序。其中又细分为13小类:直接插入排序、折半插入排序、2_路插入排序、表插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、树形选择排序、堆排序、二路归并排序、多路归并排序和基数排序。
在插入排序中,直接插入排序的基本思想是:顺序地把待排序序列中的各个记录按其关键字的大小,插入到已排序的序列的适当位置。从第一个元素开始,将它和第二个元素进行比较,将较小的放在前面(如果是升序排序的话),然后将第三个元素考虑进来,和第二个元素进行比较,将较小的放在前面,然后在跟第一个元素进行比较,依次类推,最终可以得到一个正确的升序序列。而另一种排序方法―折半插入排序,它其实和直接插入排序类似。区别就是在寻找插入点上,直接插入排序是从后向前依次比较,而折半插入排序是选取中心位置之后再进行比较,关键字比中心位置记录的关键字大,就在后面,反之则在中心位置的前面。而2_路插入排序是在直接插入排序的基础上,从减少“移动“的角度进行了优化,从而提高了效率,但它是以增加辅助空间为代价的。表插入排序则是将存储结构由向量变成了单循环链表,再进行插入排序。采用链表的好处无须在修改记录的位置,只需要修改所对应的链表指针即可。也可以说表插入直接减少了“移动”的次数,是一个对于直接插入排序很有效的改进。而希尔排序,又成为缩小增量排序。其基本思想是把待排序的记录分成若干个小组,并对同一组内的记录进行排序。同时保证了当前组内的记录个数超过前面分组排序是组内的记录个数。
在交换排序中,冒泡排序的基本思想是:顺序地把待排序序列中的各个记录按其关键字的大小,插入到已排序的序列的适当位置。从第一个元素开始,将它和第二个元素进行比较,将较小的放在前面(如果是升序排序的话),然后将第三个元素考虑进来,和第二个元素进行比较,将较小的放在前面,依次类推,知道序列中最后一个记录处理完毕为止。这样称之为一次冒泡。然后经过多次冒泡后,即可以得到正确的排序序列。而快速排序,其实是对冒泡算法的一种改进。其基本思想是,在待排序的序列中选取一个记录,设为Ri。调整序列中各个记录的位置,使得排在Ri前面的记录的关键字都小于Ri的关键字,使得排在Ri后面记录的关键字大于Ri。这样的过程,我们称之为一次快速排序。与此同时,待排序的序列实际上是根据Ri被分成了两部分,然后在每一部分再次进行排序,最终得到正确的排序序列。
在选择排序中,简单选择排序的基本思想:第i趟简单选择排序是指通过n-i次关键字的比较,从n-i+1个记录中选出关键字最小的记录,并和第i个记录进行交换。共需进行i-1趟比较,直到所有记录排序完成为止。而树型选择排序的思想其实很像败者树思想。而堆排序,则是运用了完全二叉树,通过构建堆,使得线性表中的最大(最小)元素一定处于堆的根位置,将根结点和最后一个叶结点交换位置,然后去掉这个叶结点,剩余的元素成为一个类堆,将这个类堆转化为堆,如此反复,知道所以的元素从堆中移出,得到一个有序序列。
在归并排序中,将一组无序的元素通过一系列的合并过程产生一个有序序列。“归并”的含义就是将两个或两个以上的有序表组合成一个新的有序表。和外排序相同,常见的归并排序分为二路归并排序或者多路归并排序(也简称K路归并排序)。
在基数排序中,不需要进行关键字值的比较,而是根据关键字的各位值进行排序。一般基数排序是指用多关键字的LSD方法排序,即对待排序的记录序列按照复合关键字从低位到高位的顺序交替地进行“分组”、“收集”,最终得到有序的记录序列。在此我们将一次“分组”、“收集”称为一趟。对于由d位关键字组成的复合关键字,需要经过d趟的“分配”与“收集”。
综上所述,内排序和外排序各自有各自所使用的方法,具体的选择还是要根据各大方法的具体情况而定。
区别之四,依据选取排序策略的不同而效益不同。外排序其实是依赖内排序的,要具体说到效益其实还是看外排序所选择的内排序策略。由于内排序策略很多,所以内部排序方法之间的比较还是非常值得我们探讨的。而如果待排序的数据量很小,最好使用编程简单的排序算法,毕竟在这种情况下采用编程复杂的效率较高的排序方法所能节约的计算机时间还是很有限的。几种主要的内部排序方法的比较如下***:
就平衡性能而言,快速排序最佳,但在最坏情况下,快速排序不如堆排序和归并排序。时间复杂度不熟数据初始状态影响,恒为O(n2)的是插入排序。
综上所述,外部排序和内部排序主要存在四大区别,且二者之间也有很深的联系,即“外排序依赖内排序”。在具体选用的时候,则是要依据具体情况而定了。
参考文献
[1]邹永林,周蓓,唐晓阳,杨剑勇编著.数据结构与算法教程[M].北京:机械工程出版社,2004.
[2]秦玉平,马靖善,冯佳昕.数据结构(C语言版)[M].北京:清华大学出版社,2005.
转载请注明出处学文网 » 论数据结构中的外排序与内排序