数据结构第六章排序

基本概念插入排序交换排序选择排序归并排序基数排序外部排序10-1排序的基本概念是记录中的一个(或多个)字段，如果是

关键码，则按关键码排序；排序码也

可以不是关键码，则可能有多个记录具

有相同的排序码，排序的结果不惟一。将一个数据元素集合或序列重新

排列成一个按数据元素某个数据

项值有序的序列。排序排序码稳定排序不稳定排序内排序外排序假设{R0,R1,…,Rn-1}是由n个记录组成

的文件，{K0,K1,…,Kn-1}是排序码集合，

假设Ki=Kj(0<=i,j<=n-1,i≠j)，且在排序

前的序列中Ri领先于Rj(即i<j)，若在排

序后的序列中Ri仍领先于Rj，则称所用

的排序方法是稳定的，否则是不稳定的。待排序的记录在排序过程中全部存放在内存

的称为内排序，如果排序过程中需要使用

外存的称为外排序。排序方法可以分为五种：插入排序、选择排序、

交换排序、基数排序和归并排序。排序中的基本操作：比较关键码大小和移动记录。评价排序算法好坏的标准主要有两条∶①执行算法所需的时间；②执行算法所需要的附加空间。排序的时间开销可以用算法执行中的比较和移动次数来表示。10-2插入排序插入排序的基本思想：每步将一个待排序的记录按其

关键字大小插入到前面已排序表中的适当位置，直到

全部插入完为止。直接插入排序假设待排序的n个记录{R0,R1,…,Rn-1}存放在数组中，

直接插入法是在插入记录Ri(i=1,2…n-1)时，记录集合

被划分为两个区间[R0，Ri-1]和[Ri，Rn-1]，其中，

前一个子区间已经排好序，后一个子区间是当前未

排序的部分，将排序码Ki与Ki-1，Ki-2,…,K0依次比

较，找出应该插入的位置，将记录Ri插入，原位置

的记录向后顺移。例：设待排序记录的排序码为：49，38，65，97，76，13，27，49，请用直接插入排法排序。i=2:[49]38659776132749i=3:[3849]659776132749i=4:[384965]9776132749i=5:[38496597]76132749i=6:[3849657697]132749i=7:[133849657697]27

49i=8:[13273849657697]49i=9:[1327384949657697]typedefstruct{KeyTypekey；

…；}DataType;voidInsertSort(DataTypeR[],intn){intI;for(i=2;i<=n;i++)

if(R[i].key<R[i-1].key){R[0]=R[i];for(j=i-1;R[0].dey<R[j].key;j--)R[j+1]=R[j];R[j+1]=R[0];}}算法分析如下:空间效率：只需要一个记录的辅助空间。时间效率：最小比较记录的次数为n-1=O(n)；最大比较记录的次数为(n+2)(n-1)/2=O(n2)；最小移动记录的次数为0次；最大移动记录的次数为(n+4)(n-1)/2=O(n2)。

平均情况下，插入记录大约同前面i/2个记录进行关键码比较和移动，因此插入排序的时间复杂度为O(n2)直接插入排序是稳定的排序算法二分法插入排序由于插入排序的基本操作是在有序表中进行查找,而

查找的过程是可以用折半查找来实现的。由此实现

的排序称为二分法插入排序。二分法插入排序必须采用顺序存储方式。voidB_InsertSort(DataTypeR[],intn){intI;intcow,high,mid;for(i=2;i<=n;i++){R[0]=R[i];low=1;high=i-1;while(low<=high){mid=(low+high)/2;if(R[0].key>R[mid].key)low=mid+1;elsehigh=mid-1;}for(j=i-1;j>=high+1;j--)R[j+1]=R[j];R[high+1]=R[0];}}i=2:[49]38659776132749i=3:[3849]659776132749i=4:[384965]9776132749i=5:[38496597]76132749i=6:[3849657697]132749i=7:[133849657697]2749i=8:[13273849657697]49i=9:[1327384949657697]low=1,high=1low=1,high=2low=1,high=3low=1,high=4low=1,high=5算法分析如下:定位一个关键码的位置需比较次数至多为,比较次数时间复杂度为而移动记录的次数和直接插入排序相同，

因此时间复杂度仍为O(n2)二分插入排序是一个稳定的排序方法。表插入排序基本思想：在直接插入的基础上减少移动次数，主要

是在记录中设置一个指针字段，记录链接成链表，初

始时，链表为空，头结点指针域置为0，并在头结点数

据域放比所有记录关键码都大的整数，然后，向链表

中插入结点typedefstruct{DataTypedata;intnext;}NodeType;NodeTypeR[n+1];MAX49386597761327490--------0112030445262738这个有序的链表，查找则只能顺序查找，而不能随机查找若需要，要发对记录进行重排，使其在物理上有序。012345678voidB_InsertSort(NodeTypeR[],intn){inti,j,p;DataTypeS;j=R[0].next;i=1;while(i<n)if(i==j){j=R[j].next;i++;}elseif(i<j){p=R[j].next;S=R[i];R[i]=R[j];R[j]=S;R[i].next=j;j=p;}elsewhile(j<i)j=R[j].next;}012345678MAX4938659776132749681504723jip134986jip27381jij7p387655jij496970pjip497648jijp659770jijp769708ij希尔排序Shell排序又称缩小增量排序，排序的基本思想是先取d1<n,

将整个待排记录分成d1个组，所有距离为d1倍数的记录放在同一组中，先在各组进行直接插入排序；然后，取d2<d1

重复上述分组和排序工作；直到di=1为止，就可以完成整个

的排序工作。Shell排序的一个特点是：子序列的构成不是简单“逐段

分割”，而是将相隔某个增量的记录组成一个子序列。di有各种取法,Shell取D.Knuth取49386597761327495504初始：

d1=10/2=549132738496555970476一趟排序后：

1327495504493865977604273855二趟排序后：13044938274955659776041338494938279776希尔排序是个不稳定的排序方法voidShellInsert(DataTypeR[],intdk){inti;for(i=dk+1;i<=n;i++)if(R[i].key<R[i-dk].key){R[0]=R[i];for(j=i-dk;j>0&&R[0].key<R[j].key;j=j-dk)R[j+dk]=R[j];R[j+dk]=R[0];}}voidShellSort(DataTypeR[],intn,intd[],intt){intk;for(k=0;k<t;k++)ShellInsert(R,d[k]);}10-3交换排序交换排序的基本方法是两两比较待排序记录的排序码，

交换不满足顺序要求的偶对，直到全部满足为止。冒泡排序的方法是先将序列中的第一个记录R0与第二个

记录R1比较，若前者大于后者，则两个记录交换位置，

否则不交换;然后,对新的第二个记录R1与第三个记录R2

做同样的处理；依次类推，直到处理完第n-1个记录和

第n个记录，从(R0,R1)到(Rn-2,Rn-1)的n-1次比较和交换

过程称为一次起泡。重复这样起泡过程最多n-1次就能完

成排序.冒泡排序voidBubble_Sort(DataTypeR[],intn){inti,j,swap;

for(i=1;i<n;i++){swap=0;for(j=1;j<=n-i;j++)

if(R[j].key>R[j+1].key){R[0]=R[j];R[j]=R[j+1];R[j+1]=R[0];swap=1;}if(swap==0)break;}}13

0449

38

27

49

55

65

97

76041338492749769704

13

38

27

49

49

55

65

76

97

2738最好情况下：移动次数为0，

比较次数为n-1最差情况下：比较次数

稳定的排序方法快速排序快速排序基本思想是：通过一趟排序将待排记录分割

成独立的两部分，其中一部分记录的关键字均比另一

部分记录的关键字小，则可分别对这两部分记录继续

进行排序，以达到整个序列有序。一趟快速排序的具体做法是：附设两个指针i和j,它们的

初值分别是一个序列的第一个和最后一个记录的位置，

设枢轴记录的关键字为temp.key，在首先从j所指位置起

向前搜索直到第一个关键字小于temp.key的记录和i记录

交换，然后从i所指位置起向后搜索，找到第一个

关键字大于temp.key的记录和j记录互相交换，重复

交替这两步直到i=j为止。491438749665849552749ij27iii74jjj8i96jj492714388496596495574ij278ii38j278142738496596495574ij65j55i96j49i658142738495549659674intPartition(DataTypeR[],inti,intj)

{R[0]=R[i];while(i<j){while(i<j&&R[j].key>=R[0].key)j--;if(i<j){R[i]=R[j];i++;}while(i<j&&R[i].key<R[0].key)i++;if(i<j){R[j]=R[i];j--;}}R[i]=R[0];returni;}voidQuick_Sort(DataTypeR[],ints,intt){if(s<t){i=Partition(R,s,t);Quick_Sort(R,s,i-1);Quick_Sort(R,i+1,t);}}voidQuick(DataTypeR[],intn){

Quick_Sort(R,1,n);}快速排序的记录移动次数不大于比较次数，所以，

快速排序的最坏时间复杂度应为O(n2),最好时间

复杂度为O(nlog2n)。4927651483855499674上例中对应的递归调用过程的二叉树快速排序是通常被认为同数量级的排序方法中

平均性能最好的。快速排序是一个不稳定排序方法10-4选择排序每一趟在n-i+1个记录中选取关键码最小的记录作为

有序序列中第i个记录，直到全部排完。简单选择排序基本方法是首先在所有记录中选出排序码最小的记录，

与第一个记录交换，然后在其余的记录中再选出排序

码最小的记录与第二个记录交换，以此类推，直到所

有记录排好序。voidSelect_Sort(DataTypeR[],intn){inti,j,k;

for(i=1;i<n;i++){for(k=i,j=i+1;j<=n;j++)if(R[j].key<R[k].key)k=j;if(i!=k){R[0]=R[k];R[k]=R[i];R[i]=R[0];}}}4938659749132776i=1,k=6[13]38659749492776i=2,k=7[1327]659749493876i=3,k=7[132738]9749496576i=4,k=5[13273849]97496576i=5,k=6…直接选择排序的比较次数与文件初始状态无关。直接选择排序的时间复杂度：最好移动次数为0，最坏移动次数为3(n-1)=O(n)。比较次数为n(n-1)/2=树形选择排序树形选择排序又称锦标赛排序，是一种按照锦标赛的

思想进行选择排序的方法。首先对n个记录的关键字

进行两两比较，然后在n/2个较小者之间再进行两两

比较，如此重复，直至选出最小的记录为止。493865977613274938651327381313M76M2727由于含有n个子结点的完全二叉树的深度为log2n+1，

则在树形选择排序中，除了最小数值之外，每选择

一个次小数仅需要进行log2n次比较，因此，它的时

间复杂度为O(nlogn)。但是，这种排序方法尚有辅

助存储空间较多、和“最大值”进行多余比较等缺点。

为了弥补，威洛姆斯（J.willioms）在1964年提出了

另一种形式的选择排序——堆排序。堆排序堆的概念：高有n个元素的序列{k1,k2,…,kn},当且仅当

满足下述关系之一，称这为堆。如果堆中根结点的排序码最小，则称为小根堆；如果堆中根结点的排序码最大，则称为大根堆。堆排序的思想是：首先设法把原始序列构造成一个堆，使得n个元素的最大值处于序列的第一个位置；然后交换序列第一元素(最大值元素)与最后一个元素。再把序列的前n-1个元素组成的子序列构成一个新堆，重复以上步骤，最终整个序列成为有序序列。堆排序的关键是：(1)如何将一个无序序列建成一个堆；

(2)如何把“去掉”了最大值元素后的序列

调整剩余元素为一个新的堆。构造初始堆是指把整个记录从R1到Rn调整为一个大根堆。

完全二叉树中，所有序号i>n/2的结点都是叶结点，以这

些结点为根的子树均已是堆，只需依次将以序号

n/2,n/2-1,…,1结点为根的子树调整为堆即可。

用筛选法为以Ri为根的完全二叉树建堆，若Ri的左右子树

都是堆，可以把Ri与其左右子树根结点R2i+1,R2i+2中最大者

交换位置。若交换位置后破坏了子树的堆特性，则再对这

棵子树重复交换过程，直到以Ri为根结点的子树成为堆。VoidheapAdjust(DataTypeR[],ints,intt){inti,j;DataTyperc;rc=R[s];i=s;for(j=2*i;j<=t;j=2*j){if(j<t&&R[j].key<R[j+1].key)j=j+1;if(rc.key>R[j].key)break;R[i]=R[j];i=j;}R[i]=rc;}05615948191126150105rcij61ij48ij1505voidHeapSort(DataTypeR[],intn){intI;for(i=n/2;i>0;i--)HeapAdjust(R,i,n);for(i=n;i>1;i--){R[0]=R[1];R[1]=R[i];R[i]=R[0];HeapAdjust(R,1,i-1);}}初始序列为26,5,77,1,61,11,59,15,48,19，请用堆排序法排序。（1）初始完全二叉树(2)调整序号为5的结点(3)调整序号为4的结点(4)调整序号为3的结点(5)调整序号为2的结点(6)调整序号为1的结点(7)结点77与结点5互换(8)重建堆(9)结点61与结点1互换(10)重建堆(11)结点59与结点05互换(12)重建堆(13)结点48与结点1互换(14)重建堆(15)结点26与结点1互换(16)重建堆(17)结点19与结点5互换(18)重建堆(19)结点15与结点1互换(20)重建堆堆排序的时间耗费主要在构造初始堆，以及排序中去掉

最大元素后重建堆两部分。初始建堆共调用HeapAdjust函数n/2次，每次将一个Ri(i<n/2)

为根的子树树调整为堆。个结点的完全二叉树，其深度的结点层数依次为：0,1,1,2,2,2,…,h-1。

个，以它为根的子树深度为h-m。第m层上结点数最多为HeapAdjust算法的每层上与两个子女和排序码值进行比较，

所以在m层上结点执行初始建堆最多比较2(h-m)次，第m层

所有子树建堆最多比较次数为第一部分初始建堆总的比较次数为排序中每去掉最大元素后需要重建堆。重建堆需要与

排序码的比较次数为第二部分排序中重建堆比较花费总次数为整个堆排序总的比较次数为结点移动的次数小于比较次数，故总的时间复杂度。堆排序是不稳定的!归并排序的基本思想是把待排序的文件分成若干个子文件，

先将每个子文件内的记录排序，再将已排序的子文件合并，

得到完全排序的文件。10-5归并排序假设初始的序列含有n个记录，可以看成n个有序的子序列，

每个子序列的长度为1，然后两两归并，得到个长度为

2或1的有序子序列；再两两归并，如此重复直到得到一个

长度为n的有序序列为止。这种排序方法称为二路归并排序。voidMerge(DataTypeR[],DataTypeR1[],ints,intm,intt)

{inti,j,k;i=s;j=m+1;k=s;while(i<=m&&j<=t)

if(R[i].key<R[j].key){R1[k]=R[i];k++;i++;}else{R1[k]=R[j];k++;j++;

}while(i<=m)

{R1[k]=R[i];k++;i++;}

while(j<=t){R1[k]=R[j];k++;j++;

}}voidMergePass(DataTypeR[],DataTypeR1[],intlen,intn)

{inti;for(i=1;i+2*len-1<n;i=i+2*len)Merge(R,R1,i,i+len-1,i+2*len-1)if(i+len-1<n)Merge(R,R1,i,i+len-1,n);elseif(i<=n)while(i<=n)R1[i++]=R[i+1];}归并排序的迭代算法VoidMergeSort(DataTypeR[],intn){DataTypeR1[MAXNUM];intlen;len=1;while(len<n){MergePass(R,R1,len,n)len=2*len;MergePass(R1,R,len,n);}}归并排序的递归算法voidMSort(DataTypeR[],DataTypeR1[],ints,intt){intm;if(s==t)R1[s]=R[s];else{m=(s+t)/2;MSort(R,R1,s,m);MSort(R,R1,m+1,t);Merge(R1,R,s,m,t);}}voidMergeSort(DataTypeR[],intn){DataTypeR1[MAXNUM];MSort(R,R1,1,n);}25

57

48

37

12

82

75

29

16

255737481282297516253748571229758216122529374857758216121625293748577582算法分析：时间复杂度：空间复杂度:和待排记录等量的空间。

二路归并算法是稳定的。一般情况下很少用于内部排序。10-6基数排序基数排序属于分配排序，分配排序的思想是把排序码

分解成若干部分，然后通过对各个部分排序码的分别

排序，最终达到整个排序码的排序。基数排序是采用“分配”与“收集”的办法，用对多关键码

进行排序的思想实现对单关键码进行排序的方法。多关键码排序1.以扑克牌排序为例。每张扑克牌有两个“关键码”：

花色和面值。其有序关系为：花色：梅花<方块<红心<黑桃面值：2<3<4<5<6<7<8<9<10<J<Q<K<A

可以先按花色排序，之后再按面值排序；

也可以先按面值排序，再按花色排序。文件中任一记录R[i]的关键字均由d个分量

构成。

若这d个分量中每个分量都是一个独立的关键字，则文件是多

关键字的(如扑克牌有两个关键字：点数和花色)；设单关键字的每个分量的取值范围均是：

C0≤kj≤Crd-1(0≤j<d)

可能的取值个数rd称为基数。

基数排序的基本思想是：从低位到高位依次对

Kj(j=d-1，d-2，…，0)进行箱排序。在d趟箱排

序中，所需的箱子数就是基数rd，这就是“基数

排序"名称的由来。

2781090639305891845052690080830123456789q.e0123456789q.fq[0].e2781090639305891845050830082699300630831845052780081095892690123456789q.e0123456789q.f9300630831845052780081095892695050081099300632692780831845890123456789q.e0123456789q.f505008109930063269278083184589008063083109184269278505589930#defineKEY_NUM…#defineRADIX…#defineMAX_SPACE…Typedefstruct{KeyTypekeys[KEY_NUM];InfoTypeotheritems;intnext;}NodeType;Typedefstruct{intf;inte;}Q_Node;TypedefQ_NodeQueue[RADIX];voidDistribute(NodeTypeR[],inti,Queueq){intj;for(j=0;j<RADIX;j++)