数据结构(C语言版)严蔚敏清华大学出版社第十章排序课件

三、表插入排序为了减少在排序过程中进行的“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。2/11/20231算法中使用了三个指针：其中：p指示第i个记录的当前位置

i指示第i个记录应在的位置

q指示第i+1个记录的当前位置如何在排序之后调整记录序列？2/11/20232voidArrange(SLinkListType&SL){p=SL.r[0].next;//p指示第一个记录的当前位置for(i=1;i<n;++i){

while(p<i)p=SL.r[p].next;//第i个记录在SL中的当前位置应不小于i，找到第i个记录，//并用p指示其在SL中当前位置

q=SL.r[p].next;

//q指示尚未调整的表尾if(p!=i){

SL.r[p]←→SL.r[i];//交换记录，使第i个记录到位

SL.r[i].next=p;

//指向被移走的记录}

p=q;

//p指示尚未调整的表尾，//为找第i+1个记录作准备}}//Arrange2/11/2023310.1概述10.2插入排序10.3快速排序10.4选择排序10.5归并排序10.6基数排序10.7各种排序方法的比较讨论2/11/2023510.1概述一、排序的定义二、排序的基本概念三、内部排序方法的分类2/11/20236一、排序的定义

什么是排序(Sorting)？简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来（递增或递减）。排序是计算机中经常遇到的操作。2/11/20237排序算法的稳定性判断标准：关键字相同的数据对象在排序过程中是否保持前后次序不变。如2,2*,1，排序后若为1,2*,2则该排序方法是不稳定的。内排序与外排序区分标准：排序过程是否全部在内存进行。排序的时间开销

它是衡量算法好坏的最重要的标志。通常用算法执行中的数据比较次数和数据移动次数来衡量。

2/11/20239排序的方法有很多，但简单地判断那一种算法最好，以便能够普遍选用则是困难的。评价排序算法好坏的标准主要有两条：算法执行所需要的时间和所需要的附加空间。另外，算法本身的复杂程度也是需要考虑的一个因素。排序算法所需要的附加空间一般都不大，矛盾并不突出。而排序是一种经常执行的一种运算，往往属于系统的核心部分，因此排序的时间开销是算法好坏的最重要的标志。2/11/202310三、内部排序的方法

内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区2/11/202311待排记录的数据类型:#defineMAXSIZE1000//待排顺序表最大长度typedefintKeyType;//关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据项}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作哨兵单元intlength;//顺序表长度}SqList;//顺序表类型2/11/2023131.插入

将无序子序列中的一个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。2/11/2023142.交换

通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。2/11/2023154.归并

通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。2/11/2023175.基数不需进行记录关键字间的比较，借助多关键字排序的思想对单逻辑关键字进行排序的方法。2/11/20231810.2插入排序2/11/202319有序序列R[1..i-1]R[i]无序序列R[i..n]有序序列R[1..i]无序序列R[i+1..n]1、一趟插入排序的基本思想2/11/202321实现“一趟插入排序”可分三步进行：3．将R[i]插入(复制)到R[j+1]的位置上。2．将R[j+1..i-1]中的所有记录均后移一个位置；1．在R[1..i-1]中查找R[i]的插入位置，R[1..j].keyR[i].key<R[j+1..i-1].key；2/11/202322直接插入排序（基于顺序查找）表插入排序（基于静态链表存储）不同的具体实现方法导致不同的算法描述折半插入排序（基于折半查找）希尔排序（基于逐趟缩小增量）静态链表：用数组描述的链表2/11/202323从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；R[0]=R[i];//设置“哨兵”循环结束表明R[i]的插入位置为j+1R[0]jR[i]for(j=i-1;R[0].key<R[j].key;--j);//从后往前找j=i-1插入位置2/11/202325对于在查找过程中找到的那些关键字不小于R[i].key的记录，并在查找的同时实现记录向后移动；for(j=i-1;R[0].key<R[j].key;--j);

R[j+1]=R[j]R[0]jR[i]j=i-1上述循环结束后可以直接进行“插入”插入位置2/11/202326例49386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序结果：2/11/202329内部排序的时间分析：实现内部排序的基本操作有两个：（2）“移动”记录。（1）“比较”序列中两个关键字的大小；2/11/202330算法评价时间复杂度若待排序记录按关键字从小到大排列(正序)关键字比较次数：记录移动次数：0若待排序记录按关键字从大到小排列(逆序)关键字比较次数：记录移动次数：若待排序记录是随机的，取平均值关键字比较次数：记录移动次数：T(n)=O(n²)空间复杂度：S(n)=O(1)2/11/202331直接插入排序的稳定性直接插入排序是一种稳定的排序方法。原理：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。2/11/202332

因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。3、折半插入排序2/11/202333voidBInsertSort(SqList&L){}//BInsertSort……//在L.r[1..i-1]中折半查找插入位置；for(i=2;i<=L.length;++i){}//forL.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//记录后移L.r[high+1]=L.r[0];//插入2/11/202334low=1;high=i-1;while(low<=high){}m=(low+high)/2;//折半if(L.r[0].key<L.r[m].key)

high=m-1;//插入点在低半区elselow=m+1;//插入点在高半区2/11/202335例算法评价时间复杂度：T(n)=O(n²)空间复杂度：S(n)=O(1)i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…...i=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sji=820(613203039427085)2/11/202336基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。具体做法为：将记录序列分成若干子序列，分别对每个子序列进行插入排序。4、希尔排序（缩小增量排序）2/11/202337其中，d称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。例如：将n个记录分成d个子序列：{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}2/11/202338例如：162512304711233691831

第一趟希尔排序，设增量d=51123

12

9

181625

36

30

4731

第二趟希尔排序，设增量d=3918

121123

162531

304736第三趟希尔排序，设增量d=1

9111216182325303136472/11/202339voidShellInsert(SqList&L,intdk){for(i=dk+1;i<=n;++i)

if(L.r[i].key<L.r[i-dk].key){L.r[0]=L.r[i];//暂存在R[0]for(j=i-dk;j>0&&(L.r[0].key<L.r[j].key);

j-=dk)L.r[j+dk]=L.r[j];//记录后移，查找插入位置L.r[j+dk]=L.r[0];//插入

}//if}//ShellInsert2/11/202340voidShellSort(SqList&L,intdlta[],intt){//按增量序列dlta[0..t-1]对顺序表L作希尔排序for(k=0;k<t;++t)ShellInsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序}//ShellSort2/11/202341为什么shell排序的时间性能优于直接插入排序呢？因为直接插入排序在初态为正序时所需时间最少，实际上，初态为基本有序时直接插入排序所需的比较和移动次数均较少。另一方面，当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n2)差别不大。在shell排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但组内元素已经过多次排序，数组已经比较接近有序状态，所以新的一趟排序过程也较块。2/11/202342希尔排序中gap的取法Shell最初的方案是gap=n/2,gap=gap/2，直到gap=1.Knuth的方案是gap=gap/3+1其它方案有：都取奇数为好；或gap互质为好等等。2/11/202343希尔排序的时间复杂度对希尔排序的复杂度的分析很困难，在特定情况下可以准确地估算关键字的比较和对象移动次数，但是考虑到与增量之间的依赖关系，并要给出完整的数学分析，目前还做不到。Knuth的统计结论是，平均比较次数和对象平均移动次数在n1.25

与1.6n1.25之间。希尔排序的稳定性希尔排序是一种不稳定的排序方法。如序列322*52/11/202344

假设在排序过程中，记录序列R[1..n]的状态为：第i趟起泡排序无序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1无序序列R[1..n-i]有序序列R[n-i+1..n]比较相邻记录，将关键字最大的记录交换到n-i+1的位置上5、起泡排序2/11/202345冒泡排序的排序过程将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止2/11/202346起泡排序示例i(0)(1)(2)(3)(4)(5)21254925*160810821254925*162081621254925*30816212525*4940816212525*492/11/202347起泡排序算法BUBBLESORT(rectypeR[]){inti,j,noswap;rectypetemp;for(i=0;i<n-2;i++){nos;for(j=n-1;j>=i;j++)if(R[j+1].key<R[j].key){temp＝R[j+1];R[j+1]=R[j];R[j]＝temp;nos;}if(noswap)break;}}2/11/202348起泡排序的时间复杂度考虑关键字的比较次数和对象移动次数1、在最好情况下，初始状态是递增有序的，一趟扫描就可完成排序，关键字的比较次数为n-1，没有记录移动。2、若初始状态是反序的，则需要进行n-1趟扫描，每趟扫描要进行n-i次关键字的比较，且每次需要移动记录三次，因此，最大比较次数和移动次数分别为：起泡排序方法是稳定的。空间复杂度：S(n)=O(1)2/11/202349本节结束2/11/202350第四十九讲数据结构主讲：刘立嘉快速排序与归并排序2/11/202351基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=r[s]，x=rp.key初始时令i=s,j=t首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换重复上述两步，直至i==j为止再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止1、快速排序2/11/202352一、一趟快速排序（一次划分）

目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t]，且

R[j].key≤R[i].key≤R[j].key(s≤j≤i-1)

枢轴

(i+1≤j≤t)。2/11/202353stlowhigh设R[s]=52为枢轴

将R[high].key和枢轴的关键字进行比较，要求R[high].key≥

枢轴的关键字

将R[low].key和枢轴的关键字进行比较，要求R[low].key≤

枢轴的关键字high23low80high14low52例如R[0]52lowhighhighhighlow2/11/202354可见，经过“一次划分”，将关键字序列52,49,80,36,14,58,61,97,23,75调整为:23,49,14,36,(52)58,61,97,80,75在调整过程中，设立了两个指针：low和high，它们的初值分别为：s和t，之后逐渐减小high，增加low，并保证

R[high].key≥52，和R[low].key≤52,否则进行记录的“交换”。2/11/202355intPartition(SqList&L,intlow,inthigh){pivotkey=L.r[low].key;while(low<high){while(low<high&&L.r

[high].key>=pivotkey)

--high;

L.r[low]←→L.r[high];//将比枢轴记录小的记录交换到低端while(low<high&&L.r

[low].key<=pivotkey)

++low;

L.r[low]←→L.r[high];//将比枢轴记录大的记录交换到高端}

returnlow;//返回枢轴所在位置}//Partition2/11/202356intPartition(SqList&L,intlow,inthigh){}//PartitionL.r[0]=L.r[low];pivotkey=L.r[low].key;//枢轴while(low<high){}while(low<high&&L.r[high].key>=pivotkey)--high;//从右向左搜索L.r[low]=L.r[high];//将比枢轴记录小的记录移动到低端while(low<high&&L.r[low].key<=pivotkey)++low;//从左向右搜索L.r[high]=L.r[low];//将比枢轴记录大的记录移动到高端L.r[low]=L.r[0];

returnlow;2/11/202357二、快速排序

首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无序的记录序列无序记录子序列(1)无序子序列(2)枢轴一次划分分别进行快速排序2/11/202358void

QSort(SqList&L,intlow,inthigh)

{

//对记录序列L.r[low..high]进行快速排序

if(low<high){

}}//QSortpivotloc=Partition(L,low,high);//对L.r[low..high]进行一次划分QSort(L,low,pivotloc-1);

//对低子序列递归排序，pivotloc是枢轴位置QSort(L,pivotloc+1,high);

//对高子序列递归排序2/11/202359voidQuickSort(SqList&L){

//对顺序表进行快速排序

QSort(L,1,L.length);}//QuickSort

第一次调用函数Qsort时，待排序记录序列的上、下界分别为1和L.length。2/11/2023602、最好情况是每次所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左右两个无序子区的长度大致相等。考虑关键字的比较次数和对象移动次数1、最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基准的左边（或右边）为空，划分前后无序区的元素个数减少一个，因此，排序必须做n-1趟，每一趟中需做n-i次比较，所以最大比较次数为三、快速排序的时间分析2/11/202361设C(n)表示对长度为n的序列进行快速排序所需的比较次数，显然，它应该等于对长度为n的无序区进行划分所需的比较次数n-1，加上递归地对划分所得的左右两个无序子区进行快速排序所需的比较次数。假设文件长度n=2k，k=log2n，因此有：2/11/202362

快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为O(n2)；最好时间复杂度为O(nlog2n)。可以证明，快速排序的平均时间复杂度也是O(nlog2n)。快速排序是不稳定的排序方法。空间复杂度：需栈空间以实现递归最坏情况：S(n)=O(n)一般情况：S(n)=O(log2n)2/11/202363若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。为避免出现这种情况，需在进行一次划分之前，进行“予处理”，即：先对R(s).key,R(t).key和R[(s+t)/2].key，进行相互比较，然后取关键字为“三者之中”的记录为枢轴记录。2/11/202364

归并排序的过程基于下列基本思想进行：

将两个或两个以上的有序子序列“归并”为一个有序序列。2、归并排序2/11/202365在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录的有序序列。有序序列R[l..n]有序子序列R[l..m]有序子序列R[m+1..n]这个操作对顺序表而言，是轻而易举的。2/11/202366voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){//将有序的记录序列SR[i..m]和SR[m+1..n]//归并为有序的记录序列TR[i..n]for(j=m+1,k=i;

i<=m

&&

j<=n;++k)

{//将SR中记录由小到大地并入TRif(LQ(SR[i].key,SR[j].key))TR[k]=SR[i++];elseTR[k]=SR[j++];}2/11/202367if(i<=m)TR[k..n]=SR[i..m];//将剩余的SR[i..m]复制到TRif(j<=n)TR[k..n]=SR[j..n];//将剩余的SR[j..n]复制到TR}//Merge2/11/202368归并排序的算法如果记录无序序列R[s..t]的两部分R[s..(s+t)/2]和R[(s+t)/2+1..t]分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。由此，应该先分别对这两部分进行2-路归并排序。2/11/202369例如：52,23,80,36,68,14(s=1,t=6)[52,23,80]

[36,68,14][52,23][80][52][23,52][

23,52,80][36,68][14][36][68][36,68][14,36,68][14,23,36,52,68,80][23]2/11/202370void

Msort(RcdTypeSR[],RcdType&TR1[],ints,intt)

{//将SR[s..t]归并排序为TR1[s..t]if(s==t)TR1[s]=SR[s];else{

m=(s+t)/2;//将SR[s..t]平分为SR[s..m]和SR[m+1..t]

Msort(SR,TR2,s,m);//递归地将SR[s..m]归并为有序的TR2[s..m]

Msort(SR,TR2,m+1,t);//递归地SR[m+1..t]归并为有序的TR2[m+1..t]

Merge(TR2,TR1,s,m,t);//将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]}}//Msort2/11/202371voidMergeSort(SqList&L){//对顺序表L作2-路归并排序MSort(L.r,L.r,1,L.length);}//MergeSort以上是递归的算法，下面介绍递推过程的算法2/11/202372归并算法MERGE(rectyprR[],rectypeR1[],intlow,intmid,inthigh){inti,j,k;i=low;j=mid+1;k=low;while((i<=mid)&&(j<=high))if(R[i].key<=R[j].key)R1[k++]=R[i++];elseR1[k++]=R[j++];while(j<=mid)R1[k++]=R[i++];while(j<=high)R1[k++]=R[j++];}2/11/202373

归并排序就是利用上述归并操作实现排序的。其基本思想是：将待排序列R[0]到R[n-1]看成n个长度为1的有序子序列，把这些子序列两两归并，便得到high(n/2)个有序的子序列。然后再把这high(n/2)个有序的子序列两两归并，如此反复，直到最后得到一个长度为n的有序序列。上述每次的归并操作，都是将两个子序列归并为一个子序列，这就是“二路归并”，类似地还可以有“三路归并”或“多路归并”。2/11/202374归并过程示例(25)(57)(48)(37)(12)(92)(86)(2557)(3748)(1292)(86)(25374857)(128692)(12253748578692)2/11/202375一趟归并算法MERGEPASS(rectypeR[],rectypeR1[],intlength){inti,j;i=0;while(i+2*length-1<n){MERGE(R,R1,i,i+length-1,i+2*length-1);i=i+2*length;}if(i+length-1<n-1)MERGE(R,R1,i,i+length-1,n-1);elsefor(j=i;j<n;j++)R1[j]=R[j];}2/11/202376归并排序算法MERGESORT(rectypeR[]){intlength=1;while(length<n){MERGEPASS(R,R1,length);length=2*length;MERGEPASS(R1,R,length);length=2*length;}}

2/11/202377算法复杂性分析归并排序是稳定的排序方法。归并排序在第i趟归并后，有序子文件长度为2i，因此，因此，对于具有n个记录的序列来说，必须做high(log2n)趟归并，每趟归并所花的时间为O(n)。所以，二路归并排序算法的时间复杂度为O(nlog2n)，辅助数组所需的空间为O(n)。2/11/202378本节结束2/11/202379第五十讲数据结构主讲：刘立嘉选择排序2/11/202380假设排序过程中，待排记录序列的状态为：有序序列R[1..i-1]无序序列R[i..n]第i趟简单选择排序从中选出关键字最小的记录有序序列R[1..i]无序序列R[i+1..n]1、简单选择排序/直接选择排序2/11/202381简单选择排序的算法描述如下：voidSelectSort(SqList&L){

//对记录序列作简单选择排序。for(i=1;i<L.length;++i){

//选择第i小的记录，并交换到位}}//SelectSortj=SelectMinKey(L,i);

//在L.r[i..L.length]中选择关键字最小的记录if(i!=j)L.r[i]←→L.r[j];//与第i个记录交换2/11/202382直

接

选择

排序

示

例4938659776132749’1338659776492749’1327659776493849’1327389776496549’1327384976976549’1327384949’9765761327384949’6597761327384949’6576972/11/202383算法评价时间复杂度记录移动次数最好情况：0最坏情况：3(n-1)比较次数：空间复杂度：S(n)=O(1)算法的稳定性：不稳定。T(n)=O(n²)2/11/202384堆是满足下列性质的数列{r1,r2,…，rn}：或堆的定义:(小顶堆)(大顶堆)2、堆排序2/11/202385rir2i

r2i+1

若将该数列视作完全二叉树，则r2i是ri的左孩子；r2i+1是ri的右孩子。1236276549817355403498例如:是堆14不2/11/202386988127731109是大顶堆12968338例如:2/11/2023879881244730是小顶堆1212368553912/11/202388

堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。在输出堆顶的最小值之后,使得剩余n-1个元素的序列重又建成一个堆,则得到n个元素中的次小值.如此反复执行,便能得到一个有序序列,这个过程称之为堆排序.如何“建堆”？两个问题:如何“筛选”？2/11/202389堆排序的第一个工作是建堆，即把整个记录数组R[1]到R[n]调整为一个堆。显然,只有一个结点的树是堆，而在完全二叉树中，所有序号i>=low(n/2)的结点都是叶子，因此以这些结点为根的子树都已是堆。这样，我们只需依次将序号为low(n/2)，low(n/2)-1，...，1的结点作为根的子树都调整为堆即可。我们以大根堆为例进行说明2/11/202390

若已知结点R[i]的左右子树已是堆，如何将以R[i]为根的完全二叉树也调整为堆？解决这一问题可采用“筛选法”，其基本思想是：因为R[i]的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的结点，所以我们必须在R[i]和它的左右孩子中选取关键字最大的结点放到R[i]的位置上。若R[i]的关键字已是三者中的最大者，则无须做任何调整，以R[i]为根的子树已构成堆，否则必须将R[i]和具有最大关键字的左孩子R[2i]或右孩子R[2i+1]进行交换。假定R[2i]的关键字最大，将R[i]和R[2i]交换位置，交换之后有可能导致R[2i]为根的子树不再是堆，但由于R[2i]的左右子树仍然是堆，于是可以重复上述过程，将以R[2i]为根的子树调整为堆，...，如此逐层递推下去，最多可能调整到树叶。2/11/202391例子：关键字序列为42，13，91，23，24，16，05，88，n=8，故从第四个结点开始调整421391232416058842139123241605882/11/20239242139188241605234213918824160523不调整2/11/202393421391882416052342139188241605232/11/202394428891232416051342889123241605132/11/20239591884223241605139188422324160513建成的堆2/11/202396筛选算法SIFT(rectypeR[],inti;intm){intj;rectypetemp;temp=R[i];j=2*i;while(j<=m){if((j<m)&&(R[j].key<R[j+1].key))j++;if(temp.key<R[j].key){R[i]=R[j];i=j;j=2*i;}elsebreak;}R[i]=temp;}2/11/202397

上述算法只是对一个指定的结点进行调整。有了这个算法，则将初始的无序区R[1]到R[n]建成一个大根堆，可用以下语句实现：for(i=n/2;i>=1;i--)SIFT(R,i,n)

由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，所以，应该将R[1]和R[n]交换，这就得到了第一趟排序的结果。第二趟排序的操作首先是将无序区R[1]到R[n-1]调整为堆。这时对于当前堆来说，它的左右子树仍然是堆，所以，可以调用SIFT函数将R[1]到R[n-1]调整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区的最后一个记录R[n-1]交换，如此反复进行下去。2/11/20239891884223241605139188422324160513（a）初始堆R[1]到R[8]2/11/20239913884223241605911388422324160591（b）第一趟排序之后2/11/2023100（c）重建的堆R[1]到R[7]882442231316059188244223131605912/11/202310105244223131688910524422313168891（d）第二趟排序之后2/11/2023102（e）重建的堆R[1]到R[6]422416231305889142241623130588912/11/2023103（f）第三趟排序之后052416231342889105241623134288912/11/2023104（g）重建的堆R[1]到R[5]242316051342889124231605134288912/11/2023105（h）第四趟排序之后132316052442889113231605244288912/11/2023106（i）重建的堆R[1]到R[4]231316052442889123131605244288912/11/2023107（j）第五趟排序之后051316232442889105131623244288912/11/2023108（k）重建的堆R[1]到R[3]161305232442889116130523244288912/11/2023109（l）第六趟排序之后051316232442889105131623244288912/11/2023110（m）重建的堆R[1]到R[2]130516232442889113051623244288912/11/2023111（n）第七趟排序之后051316232442889105131623244288912/11/2023112堆排序算法HEAPSORT(rectypeR[]){inti;rectypetemp;for(i=n/2;i>=1;i--)SIFT(R,i,n);for(i=n;i>=1;i--){temp=R[1];R[1]=R[i];R[i]=temp;SIFT(R,1,i-1);}}2/11/2023113堆排序的时间复杂度分析：1.对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；3.调整“堆顶”n-1次，总共进行的关键字比较的次数不超过2(log2(n-1)+log2(n-2)+…+log22)<2n(log2n)因此，堆排序的时间复杂度为O(nlogn)。2.对n个关键字，建成深度为h(=log2n+1)的堆，

所需进行的关键字比较的次数至多4n；2/11/2023114堆排序的空间复杂性为O(1)堆排序是不稳定的排序方法。优点：对小文件效果不明显，但对大文件有效。2/11/2023115本节结束2/11/2023116第五十一讲数据结构主讲：刘立嘉基数排序2/11/2023117

基数排序采用“分配”和“收集”的办法，是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。多关键字的排序链式基数排序1、基数排序2/11/2023118一、多关键字的排序多关键字排序方法示例如对扑克牌的排序每张扑克牌有两个“关键字”：花色和面值它们之间有次序的优先。对以上排序，可以先对花色排序，或先对面值排序。2/11/2023119多关键字有序的概念考虑对象序列{V0,V1,...,Vn-1}，每个对象Vi含d个关键字(Ki1,Ki2,...,Kid)。若对序列中的任意两个对象Vi和Vj都有

(Ki1,Ki2,...,Kid)<(Kj1,Kj2,...,Kjd)则称序列对关键字(Ki1,Ki2,...,Kid)有序，且K1称为最高位关键字，Kd称为最低位关键字。2/11/2023120多关键字排序原理：根据组成关键字的各位的值进行排序。实现基数排序的两种方法：

1最高位优先(MSD)排序：从关键字的高位到低位

2最低位优先(LSD)排序：从关键字的低位到高位MSD方法通常是一个递归的过程。2/11/2023121多关键字排序（续）LSD和MSD方法也可应用于对一个关键字进行的排序。此时可将单关键字Ki看成是一个子关键字组：

(Ki1,Ki2,...,Kid)如对关键字取值范围为0到999的一组对象，可看成是(K1,K2,K3)的组合。MSD方法按K1,K2,K3的顺序对所有对象排序；LSD方法按K3,K2,K1的顺序对所有对象排序。2/11/2023122例：对一副扑克牌该如何排序？答：若规定花色为第一关键字（高位），面值为第二关键字（低位），则使用MSD和LSD方法都可以达到排序目的。MSD方法的思路：先设立4个花色“箱”，将全部牌按花色分别归入4个箱内（每个箱中有13张牌）；然后对每个箱中的牌按面值进行插入排序（或其它稳定算法）。LSD方法的思路：先按面值分成13堆（每堆4张牌），然后对每堆中的牌按花色进行排序（用插入排序等稳定的算法）。想一想：用哪种方法更快些？2/11/2023123因为有分组，故此算法需递归实现。讨论：是借用MSD方式来排序呢，还是借用LSD方式？例：初始关键字序列T=（32,13,27,32*,19，33），请分别用MSD和LSD进行排序，并讨论其优缺点。法1（MSD）：原始序列：32,13,27,32*,19，33

先按高位Ki1

排序：（13,19）,27,（32,32*，33）

再按低位Ki2排序：13,19，27,32,32*,33法2（LSD）：原始序列：32,13,27,32*,19，33先按低位Ki2排序：

32,32*,13,33,27,19

再按高位Ki1排序：

13,19,27,32,32*,33无需分组，易编程实现！2/11/2023124

例如:学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。无序序列对K2排序对K1排序对K0排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18

1,2,152,1,202,3,183,1,203,2,30LSD的排序过程如下:2/11/2023125二、链式基数排序假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。对于数字型或字符型的单关键字，可以看成是由多个数位或多个字符构成的多关键字，此时可以采用这种“分配-收集”的办法进行排序，称作基数排序法。2/11/2023126单逻辑关键字怎样“按位值”排序？设n个记录的序列为：{V0,V1,…,Vn-1}，可以把每个记录Vi的单关键码Ki

看成是一个d元组（Ki1,Ki2,…,Kid），则其中的每一个分量Kij

(1

jd)也可看成是一个关键字。4注1：

Ki1＝最高位，Kid＝最低位；Ki共有d位，可看成d元组；注2：每个分量Kij

(1

j

d)有radix种取值，则称radix为基数。26(9,8,4)(0,1,…,9)（a,b,…,z）(d,i,a,n)310例1：关键码984可以看成是

元组；基数radix为

。例2：关键码dian可以看成是

元组；基数radix为

。思路：2/11/2023127例如：对下列这组关键字{209,386,768,185,247,606,230,834,539}首先按其“个位数”取值分别为0,1,…,9“分配”成10组，之后按从0至9的顺序将它们“收集”在一起；然后按其“十位数”取值分别为0,1,…,9“分配”成10组，之后再按从0至9的顺序将它们“收集”在一起；最后按其“百位数”重复一遍上述操作。2/11/2023128

在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：

１．待排序记录以指针相链，构成一个链表；２．“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同；３．“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;４．对每个关键字位均重复2)和3)两步。2/11/20231291792083069385998455927133B[0].fB[1].fB[2].fB[3].fB[4].fB[5].fB[6].fB[7].fB[8].fB[9].fB[0].eB[1].eB[2].eB[3].eB[4].eB[5].eB[6].eB[7].eB[8].eB[9].e27193339845530620817985992/11/20231302719333984553062081798599B[0].fB[1].fB[2].fB[3].fB[4].fB[5].fB[6].fB[7].fB[8].fB[9].fB[0].eB[1].eB[2].eB[3].eB[4].eB[5].eB[6].eB[7].eB[8].eB[9].e33984306208955859271179932/11/20231313062089335585927117998493B[0].fB[1].fB[2].fB[3].fB[4].fB[5].fB[6].fB[7].fB[8].fB[9].fB[0].eB[1].eB[2].eB[3].eB[4].eB[5].eB[6].eB[7].eB[8].eB[9].e179306984859933559320827193355931792082713068599842/11/2023132分配排序算法typedefstruct{intkey[d];intnext;datatypeother;}rectype;

rectypeR[n];

typedefstruct{intf,e;}queue;

queueB[m];2/11/2023133for(j=d-1;j>=0;j--){for(i=0;i<m;i++){B[i].f=-1;B[i].e=-1;}while(p!=-1){k=R[p].key[j];if(B[k].f==-1)B[k].f=p;elseR[B[k].e].next=p;B[k].e=p;p=R[p].next;}i=0;while(B[i].f==-1)i++;t=B[i].e;p=B[i].f;while(i<m-1){i++;if(B[i].f!=-1){R[t].next=B[i].f;t=B[i].e;}}R[t].next=-1;}returnp;}intRADIXSORT(rectypeR[]){inti,j,k,t,p;for(i=0;i<n-1;i++)R[i].next=i+1;R[n-1].next=-1;p=0;2/11/2023134注意：１．“分配”和“收集”的实际操作仅为修改链表中的指针和设置队列的头、尾指针；２．为查找使用，该链表尚需应用算法Arrange将它调整为有序表。2/11/2023135算法评价特点：不用比较和移动，改用分配和收集，时间效率高！时间复杂度：分配：T(n)=O(n)收集：T(n)=O(rd)T(n)=O(d(n+rd))其中：n——记录数d——关键字数rd——关键字取值范围空间复杂度：S(n)=2rd个队列指针+n个指针域空间稳定性：稳定。(一直前后有序)。2/11/2023136一、时间性能1.平均的时间性能基数排序时间复杂度为O(nlogn)：快速排序、堆排序和归并排序时间复杂度为O(n2)：直接插入排序、起泡排序和简单选择排序时间复杂度为O(n):2、各种排序方法的综合比较2/11/20231372.当待排记录序列按关键字顺序有序时3.

简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。直接插入排序和起泡排序能达到O(n)的时间复杂度，快速排序的时间性能蜕化为O(n2)。2/11/2023138二、空间性能指的是排序过程中所需的辅助空间大小1.所有的简单排序方法(包括：直接插入、起泡和简单选择)

和堆排序的空间复杂度为O(1)；2.

快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间；2/11/20231393.

归并排序所需辅助空间最多，其空间复杂度为O(n);4.

链式基数排序需附设队列首尾指针，则空间复杂度为

O(rd)。2/11/2023140三、排序方法的稳定性能

1.稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。2.当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。排序之前:{·····Ri(K)·····Rj(K)·····}排序之后:{·····Ri(K)Rj(K)··········}2/11/2023141例如：

排序前

(56,34,47,23,66,18,82,

47)若排序后得到结果(18,23,34,47,47,56,66,82)则称该排序方法是稳定的;若排序后得到结果(18,23,34,47,47,56,66,82)则称该排序方法是不稳定的。2/11/20231423.对于不稳定的排序方法，只要能举出一个实例说明即可。4.快速排序、堆排序和希尔排序是不稳定的排序方法。例如:对{4,3,4,2}进行快速排序，得到{2,3,4,4}2/11/2023143四、关于“排序方法的时间复杂度的下限”