论数据结构中外排序与内排序.docVIP

论数据结构中外排序与内排序 　　摘 要:主要讨论数据结构中的内排序和外排序。通过讨论两者之间的区别来对内外排序进行深入讨。比较了多种内排序的方法,从时间复杂度、空间复杂度和稳定性上一一做了详细探讨并列表比较。? 　　关键词:数据结构;内排序;外排序;存储器;时间复杂度;空间复杂度? 　　中图分类号:TP 　　文献标识码:A 　　文章编号:1672-3198(2010)05-0327-02?? 　　 　　排序是一种计算机必不可少的操作,其功能就是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。而排序分为外排序和内排序,两者固然存在着一定的区别。下面将通过分析二者区别来进一步对内外排做深入探讨。? 　　区别之一,就是外排序和内排序所设计的存储器的不同。一般情况下,内部排序中待排序的文件较小。之所以称之为“内”是因为排序是在内存中完成的,文件一般可以一次在内存中排序。而一般外部排序中待排序的文件较大,不存储于内存而存储于外存,且不能一次调入进入内存。对此计算机所采取的策略是将文件中的数据分段输入内存,在内存中采用内排序的方法对其进行排序,这样完成排序后的文件段称为归并段,然后在将其写回外存,这样在外存中形成许多初始归并段。然后对这些归并短采用某种归并方法,并进行多遍归并,似的已经排序好的归并段逐渐扩大,最后在外存上形成整个文件的单一归并段,也就完成了这个文件的外排序。概括起来说,就是“内排序在内存上排序,外排序借助内排序通过调用间接完成外存上的排序”。? 　　区别之二,除了存储器的不同,内排序和外排序所采用的存储方式也是不同的。内排序主要使用三种存储方式,一种连续地址的方式,即文件在内存中采用连续地址的方式;一种是静态链表的方式,采用链表的方式,实现“逻辑”上的连续存储。且链表使得存储一目了然,简单易懂;还有一种,就是指示各个记录存储位置的地址向量。? 　　而对于外排序而言,主要使用两种存储方式。一种是磁盘存储器,一种是磁带存储器。磁盘存储器一般分为硬盘和软盘,是一种直接存取的存储设备,即访问存储在磁盘上的文件中的任何一条记录所花费的时间几乎相同,而不是像磁带存储器那样是顺序存储。磁盘,也就是和光盘一样,是一个扁平的圆盘,上面有很多磁道,信息就存储在磁道上。磁道这是磁盘上的很多同心圆,计算机根据磁盘上深浅不一的凹槽才进行信息识别。磁盘又有固定头盘和活动头盘的区别。所谓固定,就是每一个磁道上都有独立的磁头来进行识别,而活动头盘也就是说其磁头是可以移动的。因此访问磁盘的时候,必须先找到柱面,然后移动磁头到柱面上,并将要访问的信息转到磁头下面,最后对信息进行读写。而磁带存储器也是比较常见的。? 　　区别之三,内排序和外排序的方法即所采用的策略不同。内排序主要分为五大类,分别为插入排序、选择排序、交换排序、基数排序、归并排序。其中插入排序又分为直接插入排序、折半插入排序、2-路插入排序、表插入排序和希尔(shell)排序。选择排序又分为简单选择排序、树形选择排序和堆排序。交换排序分为冒泡排序和快速排序。归并排序又分为二路归并排序和多路归并排序。而外排序最常用的是归并排序法。主要分为多路归并排序和置换-选择排序两种,其主要的排序方法结构图如下图1、2所示:? 　　在多路归并排序法中,一般使用的两个概念叫做胜者树和败者树。败者树是一课完全二叉树,其中每个结点的关键字(键值)取决于它的两个子节点中的关键字中的较小值(也就是胜者),然后就像淘汰赛一样,胜者进入下一轮的比赛,依次选取最小者,然后根节点的值最小。而胜者树的概念和败者树是相对的,它们之间的区别在于一个选择了胜者(关键字小),一个选择了败者(关键字大),其他的原理基本相同。例如下图3所显示的败者树:? 　　上图中使用败者树原理,首先从根结点中选取关键字较小的一个,“进入下一轮的PK”,然后根节点取最小的值。在后面的应用中,往往把根节点的值输出并用一个新的元素替代,要求构成新的败者树,这是只需要在原来的败者树的基础上进行调整即可。? 　　而在外排序中的置换-选择排序方法,其基本思想是先从输入文件中读取N个记录到内存工作区,然后选这N个记录中键值最小的记录写到输出文件中。如果新读入的记录的键值小于刚写到输出文件的键值,则该记录应归于下段,可在工作区中给记录加标志以示区别;如果新读入的记录的键值大于刚写到输出文件的键值,则记录归入当前段。然后一直重复操作,一直到工作区为空。置换-选择排序示意图如下图4所示:? 　　图4 　　相对与外排序,内排序的方法就相当之多了,本文中就分了五大类:插入排序、交换排序、选择排序、归并排序和基数排序。其中又细分为13小类:直接插入排序、折半插入排序、2_路插入排序、表插入排序、希尔排序、冒泡排序、快速排序、简