【数据结构讲解】排序.ppt

《【数据结构讲解】排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、排序排序（sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序，指的是待排序记录存放在计算机存储器中进行的排序过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中对外存进行访问的排序过程。插入排序线性插入排序的基本思想是：第1遍，将初始文件中的记录R1看作有序子文件，将R2插入这个子文件中。若R2的关键字小于R1的关键字，则R2插在R1

2、的前面，否则R2插在R1的后面。第2遍，将R3插入前面的两个记录的有序子文件中，得到3个记录的有序子文件。依此类推，继续进行下去，直到将Rn插入到前面的n-1个记录的有序子文件中，最后得到n个记录的有序文件。线性插入排序的基本思想是：第1遍，将初始文件中的记录R1看作有序子文件，将R2插入这个子文件中。若R2的关键字小于R1的关键字，则R2插在R1的前面，否则R2插在R1的后面。第2遍，将R3插入前面的两个记录的有序子文件中，得到3个记录的有序子文件。依此类推，继续进行下去，直到将Rn插入到前面的n-1个记录的有序子文件中，最后得到n个记录的有序文

3、件。图9-1所示为线性插入排序的例子。为了避免检测是否应插在R1的前面，在R1的前面设立记录R0，它既是中间变量，又是监视哨。设（R1，R2，…，Ri-1）是已排序的有序子文件，则插入Ri的步骤是：首先将Ri存放到Ro中，然后将Ko（即原Ri的关键字Ki）依次与Ki-1，Ki-2，…比较，若Ko

4、er[n+1],intn)/*r[n+1]为一维数组，其中r[0]为监视哨，r[1]到r[n]为待排序的n个记录，排序好的记录仍放在r中*/{for(i=2;i<=n;i++)/*共进行n-1趟*/{r[0]=r[i];/*r[0]为监视哨，也可做下边循环结束标志*/j=i-1;while(r[j].key>r[0].key){r[j+1]=r[j];j--;}r[j+1]=r[0];}}折半插入排序在线性插入排序中，我们采用顺序查找法来确定记录的插入位置。由于（R1，R2，…，Ri-1）是有序子文件，我们可以采用折半查找法来确定R1的插入位置，这

5、种排序称为折半插入排序。其算法可写出如下：voidbinarysort(structnoder[n+1],intn)/*按关键字递增的次序对记录r[1],r[2],……,r[n]进行折半插入排序*/{for(i=2;i<=n;i++){r[0]=r[i];l=1;h=i-1;while(l<=h){mid=(l+h)/2;if(r[0].key=l;j--)r[j+1]=r[j];r[l]=r[0];}}在上面的算法中，每插入一个R1，平均比较次数为log2i

6、。希尔排序希尔排序（Shell’sMethod）又称“缩小增量排序”（DiminishingIncrementSort），是由D.L.Shell在1959年提出来的。它的作法是：先取定一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序；然后，到第二个增量d2

7、，65，97，76，13，27，49/，55，04。增量序列取值依次为：5，3，1。第一趟排序时，d1=5，整个文件被分成5组：（R1，R6），（R2，R7），…，（R5，R10）各组中的第1个记录都自成一个有序区，我们依次将各组的第2个记录R6，R7，…R10分别插入到各组的有序区中，使文件的各组均是有序的，其结果见图9-2的第七行。第二趟排序时，d2=3，整个文件分成三组：（R1，R4，R7，R10），（R2，R5，R8），（R3，R6，R9），各组的第1个记录仍自成一个有序区，然后依次将各组的第2个记录R4，R5，R6分别插入到该组的当前有序

8、区中，使得（R1，R4），（R2，R5），（R3，R6）均变为新的有序区，接着依次将各组的第3个记录R7，R8，R9分别插