西南第10章排序

DATASTRUCTURE2023/7/142第10章排序2023/7/143本章目录10.1概述10.2插入排序

10.2.1直接插入排序

10.2.2折半插入排序*10.2.3二路插入排序*10.2.4表插入排序

10.2.5希尔排序10.3交换排序

10.3.1起泡排序

10.3.2快速排序10.4选择排序10.4.1直接选择排序10.4.2树形选择排序10.4.3堆排序10.5归并排序10.6分配排序10.7内部排序方法的比较10.8外部排序

10.8.1文件管理10.8.2外部排序10.8.3多路归并排序

10.8.4置换选择排序*10.8.5最佳归并树*10.8.6磁带排序2023/7/144主要内容知识点1、排序的定义，排序可以看作是线性表的一种操作2、排序的分类，稳定排序与不稳定排序的定义。3、插入排序（直接插入、对分插入、二路插入、表插入、希尔插入排序）。4、交换排序（冒泡排序、快速排序）。5、选择排序（简单选择排序、树形选择排序、堆排序）。6、归并排序、基数排序。7、外部排序重点难点1、各种排序所基于的基本思想。2、排序性能的分析，是否是稳定排序。3、折半插入、希尔排序。4、快速排序。5、堆排序。6、败者树、置换选择排序、最佳归并树。7、对每种排序方法的学习，能举一反三。2023/7/145基本概念排序：假设含n个记录的序列为{R1,R2,…,Rn}，其相应的关键字序列为{K1,K2,…,Kn}，这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Ks1≤Ks2≤…≤Ksn，按此固有关系将n个记录的序列重新排列为{Rs1,Rs2,

…,Rsn}的操作称作排序。2023/7/146基本概念稳定排序：若Ki为关键字，Ki=Kj（i≠j），且在排序前的序列中Ri领先于Rj。经过排序后，Ri与Rj的相对次序保持不变（即Ri仍领先于Rj），则称这种排序方法是稳定的，否则称之为不稳定的。内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能一次在内存中完成，则称此类排序问题为外部排序2023/7/147排序的类型定义#definen待排序记录的个数typedefstruct{intkey;AnyTypeother;∥记录其它数据域

}RecType;RecTypeR[n+1];2023/7/148基本思想：假定第一个记录有序，从第2个记录开始，将待排序的记录插入到有序序列中，使有序序列逐渐扩大，直至所有记录都进入有序序列中。

插入排序插入排序种类：

直接插入排序折半插入排序二路插入排序表插入排序

希尔排序

2023/7/149直接插入排序基本思想：将记录R[i](2<=i<=n)插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]

2023/7/1410示例初始关键字序列：[51]33629687172851'i=2(33)[3351]629687172851'i=3(62)[335162]9687172851'i=4(96)[33516296]87172851'i=5(87)[3351628796]172851'i=6(17)[173351628796]2851'i=7(28)[17283351628796]51'i=8(51')[1728335151'628796]2023/7/1411一趟直接插入排序算法voidStrOnePass(RecTypeR[]，inti){∥已知R[1..i-1]中的记录按关键字非递减有序排列，本算法

∥插入R[i],使R[1..i]中的记录按关键字非递减有序排列

R[0]=R[i];j=i-1;∥将待排序记录放进监视哨

x=R[0].key;∥从后向前查找插入位置，将大于待排序记录向后移动

while(x<R[j].key){R[j+1]=R[j];j--;}∥记录后移

R[j+1]=R[0];∥将待排序记录放到合适位置}∥StrOnePass2023/7/1412直接插入排序算法voidStrInsSort1(RecTypeR[]，intn){∥本算法对R[1..n]进行直接插入排序

for(i=2;i<=n;i++)∥假定第一个记录有序

StrOnePass(R，i)；}2023/7/1413直接插入排序性能分析最坏情况比较次数为=(n+2)(n-1)/2移动次数为=(n+4)(n-1)/2最好情况比较次数为n-1次移动次数为2（n-1）次2023/7/1414直接插入排序的优缺点直接插入排序算法简单，当待排序记录数量n很小时，局部有序时，较为适用。

当n很大时，其效率不高。若对直接插入排序算法进行改进，可从减少“比较”和“移动”次数这两方面着手。

折半存入排序、二路插入排序、表插入排序、希尔排序都是对直接插入排序的改进。2023/7/1415折半插入排序

voidBinsSort(RecTypeR[]，intn)∥对R[1..n]进行折半插入排序{for(i=2;i<=n;i++)∥假定第一个记录有序

{R[0]=R[i];∥将待排记录R[i]暂存到R[0]

low=1;high=i-1;∥设置折半查找的范围 R[low..high]while(low<=high){m=(low+high)/2;∥折半

if(R[0].key<R[m].key)high=m-1;∥插入点在低半区

elselow=m+1;∥插入点在高半区

}∥whilefor(j=i-1;j>high;j--)R[j+1]=R[j];∥记录后移

R[high+1]=R[0];∥插入

}∥for}∥BinsSort2023/7/1416折半插入排序性能分析减少了比较次数，移动次数不变。时间复杂度仍为O（n2）。2023/7/1417在对一组记录（54，38，96，23，15，72，60，45，83）

进行直接排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较多少次自测题1

2023/7/1418二路插入排序

对折半插入排序改进，减少了移动记录的次数，但它要借助n个记录的辅助空间，即其空间复杂度为O（n）。基本思想：另设一数组d，将R[1]赋值给d[1]，并将d[1]看作排好序的中间记录，从第二个记录起依次将关键字小于d[1]的记录插入d[1]之前的有序序列，将关键字大于d[1]的记录插入d[1]之后的有序序列。借助两个变量first和final来指示排序过程中有序序列第一个记录和最后一个记录在d中的位置。2023/7/1419初始关键字序列：5133629687172851

i=1[51]first↑↑finali=2[51][33]↑final↑firsti=3[5162][33]final↑↑firsti=4[516296][33]final↑↑firsti=5[51628796][33]final↑↑firsti=6[51628796][1733]final↑↑firsti=7[51628796][172833]final↑↑firsti=8[5151628796172833]final↑↑first

2023/7/1420二路插入排序算法voidBiInsertSort(RecTypeR[]，intn){∥二路插入排序的算法

intd[n+1];∥辅助存储

d[1]=R[1];first=1;final=1;

for(i=2;i<=n;i++)

{if(R[i].key>=d[1].key)∥插入后部

{low=1;high=final;while(low<=high)∥折半查找插入位置

{m=(low+high)/2;if(R[i].key<d[m].key)high=m-1;elselow=m+1;}∥whilefor(j=final;j>=high+1;j--)d[j+1]=d[j];∥移动元素

d[high+1]=R[i];final++;∥插入有序位置

}2023/7/1421

else

{

if(first==1)∥插入前部

{first=n;d[n]=R[i];}else{low=first;high=n;while(low<=high){m=(low+high)/2;if(R[i].key<d[m].key)high=m-1;elselow=m+1;}∥whilefor(j=first;j<=high;j++)d[j-1]=d[j];∥移动元素

d[high]=R[i];first--;

}∥if}∥if}//for}2023/7/1422表插入排序

静态链表

#definen待排序记录的个数typedefstruct{intkey;AnyTypeother;∥记录其他数据域

intnext;}STListType;STListTypeSL[n+1];2023/7/1423表插入排序算法

voidListInsSort(STListTypeSL[],intn)∥对记录序列SL[1..n]作表插入排序。

{SL[0].key=MAXINT;SL[0].next=1;SL[1].next=0;for(i=2;i<=n;i++)∥查找插入位置

{j=0;for(k=SL[0].next;SL[k].key<=SL[i].key;){j=k,k=SL[k].next;}SL[j].next=i;SL[i].next=k;∥结点i插入在结点j和结点k之间

}∥for}∥ListInsSort2023/7/1424表物理排序

voidArrange(STListTypeSL[]，intn){∥调整静态链表SL中各结点的指针值，使记录按关键字有序排列

p=SL[0].next;∥p指示第一个记录的当前位置

for(i=1;i<n;i++){∥SL[1..i-1]记录已按关键字有序，第i个记录的当前位置应不小于iwhile(p<i)p=SL[p].next;∥找到第i个记录，并用p指示其在SL中当前位置

q=SL[p].next;∥q指示尚未调整的表尾

if(p!=i){SL[p]←→SL[i];∥交换记录，使第i个记录到位

SL[i].next=p;∥指向被移走的记录，使得以后可由while循环找回

}∥ifp=q;∥p指示尚未调整的表尾，为找第i+1个记录作准备

}∥for}∥Arrange2023/7/1425希尔(shell1959)排序基本思想：从“减小n”和“基本有序”两方面改进。将待排序的记录划分成几组，从而减少参与直接插入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。2023/7/1426希尔排序示例二趟排序结果：171051／

33285152629687三趟排序结果：1017283351／

5152628796

初始关键字序列：5133629687172851／

5210

一趟排序结果：172851／

521051336296872023/7/1427希尔排序算法voidShellSort(RecTypeR[]，intn){∥以步长di/2分组的希尔排序，第一个步长取n/2，最后一个取1for(d=n/2;d>=1;d=d/2) {for(i=1+d;i<=n;i++) ∥将R[i]插入到所属组的有序列段中

{R[0]=R[i];j=i-d; while(j>0&&R[0].key<R[j].key) {R[j+d]=R[j];j=j-d;}∥whileR[j+d]=R[0];∥第i个元素插入到合适位置

}∥for}∥for}∥ShellSort2023/7/1428自测题2希尔排序示例请给出对一组记录（54,38,96,23,15,90,72,60,45,83）进行希尔排序（增量序列为5，3，1）时的排序过程。2023/7/1429交换排序基本思想：在排序过程中，通过对待排序记录序列中元素间关键字的比较，发现逆序的，则交换元素位置。

交换排序种类：

起泡排序快速排序2023/7/1430起泡排序基本思想：对所有相邻记录的关键字值进行比较，如果是逆序（a[j].key>a[j+1].key），则将其交换，最终达到有序化

2023/7/1431起泡排序示例初始关键字5133629687172851第一趟3351628717285196第四趟3317285151628796第三趟3351172851628796第二趟3351621728518796第五趟1728335151628796第六趟17283351516287962023/7/1432voidBubbleSort(RecTypeR[]，intn)∥起泡排序

{i=n;∥i指示无序序列中最后一个记录的位置

while(i>1)

{LastExchange=1;∥记最后一次交换发生的位置

for(j=1;j<i;j++)if(R[j].key>R[j+1].key)

{R[j]↔R[j+1];∥逆序时交换

LastExchange=j;

}∥ifi=LastExchange;}∥while}

起泡排序算法2023/7/1433起泡排序性能分析平均时间复杂度：O(n2)2023/7/1434一组关键字（19,01,26,92,87,11,43,87,21），

进行冒泡排序，

试列出每一趟排序后的关键字序列

自测题3冒泡排序示例2023/7/1435快速排序基本思想：从排序序列中任选一记录作为枢轴（或支点），凡其关键字小于枢轴的记录均移动至该记录之前，而关键字大于枢轴的记录均移动至该记录之后。一趟排序后“枢轴”到位，并将序列分成两部分，再分别对这两部分排序。

由Hoare(图灵奖获得者)1962年提出，被评为20世纪十大优秀算法之一。2023/7/1436快速排序图示不大于不小于1n枢轴2023/7/1437快速排序示例初始关键字序列：[51]336296871728

51R[0]=[51]i↑(枢轴)↑jj向前扫描i↑↑j第一次交换之后：283362968717[]51i↑↑ji向后扫描i↑↑j第二次交换之后：2833[]9687176251i↑↑jj向前扫描i↑↑j第三次交换之后：2833179687[]6251i向后扫描i↑↑j第四次交换之后：283317[]87966251j向前扫描i↑↑j完成一趟排序：283317[51]87966251

i↑↑j

2023/7/1438快速排序示例初始关键字序列：5133629687172851一趟排序之后：[283317]

51

[87966251]分别进行快速排序：[17]28[33]

结束结束[5162]87[96]

51[62]结束结束快速排序后的序列：17283351516287962023/7/1439快速排序算法intPartition(RecTypeR[]，intl，inth){∥交换记录子序列R[l..h]中的记录，使枢轴记录到位并返回其所在位置

inti=l;j=h;∥用变量i,j记录待排序记录首尾位置

R[0]=R[i];

∥以子表的第一个记录作枢轴，将其暂存到记录R[0]中

x=R[i].key;∥用变量x存放枢轴记录的关键字

while(i<j)∥从表的两端交替地向中间扫描

{while(i<j&&R[j].key>=x)j--;R[i]=R[j];∥将比枢轴小的记录移到低端

while(i<j&&R[i].key<=x)i++;R[j]=R[i];∥将比枢轴大的记录移到高端

}∥whileR[i]=R[0];∥枢轴记录到位

returni;∥返回枢轴位置}∥Partition2023/7/1440快速排序算法voidQuickSort(RecTypeR[]，ints，intt){∥对记录序列R[s..t]进行快速排序

if(s<t)

{k=Partition(R,s,t);QuickSort(R,s,k-1);QuickSort(R,k+1,t);

}∥if}∥QuickSort

快速排序的平均时间复杂度为O（nlog2n）最差为O(n2)2023/7/1441对下列一组关键字

（46,58,15,45,90,18,10,62）

试写出快速排序的每一趟的排序结果

自测题4快速排序示例2023/7/1442

设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排，使得红色砾石在前，白色砾石居中，蓝色砾石居后。对每粒砾石的颜色只能察看一次，且只允许交换操作来调整砾石的位置。

【上海大学2019二2(18分)】算法举例10.1

快速排序2023/7/1443红、白、兰三色排序算法

voidQkSort(rectyper[],intn){inti=1,j=1,k=n;while(j<=k)if(r[j]==1)∥当前元素是红色

{r[i↔r[j];i++;j++;}elseif(r[j]==2)j++;∥当前元素是白色

else∥(r[j]==3当前元素是兰色

{r[j↔r[k];k--;}}∥QkSort2023/7/1444

冒泡排序算法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)请给出上浮和下沉过程交替的冒泡排序算法。

【吉林大学2019二.3(9分)】

【北京邮电大学1992六(10分)】算法举例10.2双向冒泡排序2023/7/1445voidBubbleSort2(inta[],intn)∥相邻两趟向相反方向起泡的冒泡排序算法{change=1;low=0;high=n-1;∥冒泡的上下界

while(low<high&&change){change=0;∥设不发生交换

for(i=low;i<high;i++)∥气泡上浮,大元素下沉(向右)if(a[i]>a[i+1]){a[i]<-->a[i+1];change=1;}∥有交换,修改标志changehigh--;∥修改上界

for(i=high;i>low;i--)∥气泡下沉,小元素上浮(向左)if(a[i]<a[i-1]){a[i]<-->a[i-1];change=1;}∥有交换,修改标志changelow++;∥修改下界

}∥while}∥BubbleSort2

算法举例10.2双向冒泡排序的算法2023/7/1446

对给定关键字序号j(1<j<n)，要求在无序记录A[1..n]中找到关键字从小到大排在第j位上的记录，写一个算法利用快速排序的划分思想实现上述查找。(要求用最少的时间和最少的空间)

例如：给定无序关键字{7,5,1,6,2,8,9,3}，当j=4时，找到的关键字应是5。

【中科院研究生院2019十二(15分)】

【武汉理工大学2019四.3(35/3分)】算法举例10.3快速排序2023/7/1447intpartition(RecTypeA[],int1,n){inti=1,j=n;x=A[i].key;i=1;while(i<j){while(i<j&&A[j].key>=x)j--;if(i<j)A[i++]=A[j];while(i<j&&A[i].key<=x)i++;if(i<j)A[j--]=A[i];}returni;}voidFind_j(RecTypeA[],intn,intj){i=partition(A,1,n);while(i!=j)if(i<j)i=quicksart(A,i+1,n);∥在后半部分继续进行划分

elsei=quicksart(R,1,i-1);∥在前半部分继续进行划分

}算法举例10.3的算法2023/7/1448选择排序基本思想：依次从待排序记录序列中选择出关键字值最小（或最大）的记录、关键字值次之的记录、……，并分别将它们定位到序列左侧（或右侧）的第1个位置、第2个位置、……，从而使待排序的记录序列成为按关键字值由小到大（或由大到小）排列的有序序列。

选择排序种类：

直接（简单）选择排序树形选择排序堆排序

2023/7/1449直接选择排序待排记录序列的状态为：有序序列R[1..i-1]

无序序列R[i..n]

有序序列中所有记录的关键字均小于无序序列中记录的关键字，第i趟直接选择排序是从无序序列R[i..n]的n-i+1记录中选出关键字最小的记录加入有序序列

2023/7/1450直接选择排序示例初始关键字序列：5133629687172851／

↑↑第一趟排序后：[17]

33629687512851／↑↑第二趟排序后：[1728]

629687513351／↑↑第三趟排序后：[1728

33]

9687516251／第四趟排序后：[1728

3351]

87966251／第五趟排序后：[1728

3351

51／]966287第六趟排序后：[1728

3351

51／

62]

9687第七趟排序后：[1728

3351

51／

62

87

96]2023/7/1451直接选择排序算法voidSelectSort(RecTypeR[]，intn){∥对记录序列R[1..n]作直接选择排序。

for(i=1;i<n;i++)∥选择第i小的记录，并交换到位

{k=i;∥假定第i个元素的关键字最小

for(j=i+1;j<=n;j++)∥找最小元素的下标

If(R[j].key<R[k].key)k=j;if(i!=k)R[i]←→R[k];∥与第i个记录交换

}∥for}∥SelectSort直接选择排序的平均时间复杂度为O（n2）

记录移动次数最好情况：0最坏情况：3(n-1)比较次数(与初始状态无关):2023/7/1452

基本思想：对n个待排序记录的关键字进行两两比较，从中选出n/2个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。一趟选出的关键字最小的记录称为“冠军”，而“亚军”是从与“冠军”比较失败的记录中找出。输出“冠军”后，将（冠军）叶子结点关键字改为最大，继续进行锦标赛排序，直到选出关键字次小的记录为止，如此循环直到输出全部有序序列。

树形选择排序(锦标赛排序)2023/7/1453

对关键字序列72,73,71,23,94,16,05,68进行树形选择排序树形选择排序(锦标赛排序)052305722316057273712394160568冠军2023/7/1454

“亚军”是从与“冠军”比较失败的记录中找出的树形选择排序(锦标赛排序)16231671231668727371239416∞68亚军2023/7/1455

n个记录的锦标赛排序，每选择一个记录需log2n次比较，时间复杂度为O(nlog2n)。缺点：需要较多的辅助存储空间；

与“最大值”进行多次多余的比较。

对树形排序的改进是堆排序

树形选择排序性能分析2023/7/1456堆的定义：堆是满足下列性质的序列{K1,K2,…,Kn}：

堆排序或（i=1,2,…,

n/2）

若上述序列是堆，则K1必是序列中的最小值或最大值，分别称作小顶堆或大顶堆（小堆或大堆，小根堆或大根堆）。若将此序列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，任何一个结点的值不大于(或不小于)左/右子女结点（若存在）的值

2023/7/1457堆排序示例

96，51，87，33，28，62，51，17是大顶堆

例如：17，28，51，33，62，96，87，51

是小顶堆2023/7/1458堆排序基本思想：先建一个堆，即先选得一个关键字最大或最小的记录，然后与序列中最后一个记录交换，之后将序列中前n-1个记录重新调整为一个堆（调堆的过程称为“筛选”），再将堆顶记录和第n-1个记录交换，如此反复直至排序结束。

堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？2023/7/1459第二个问题解决方法方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆第一个问题解决方法方法：把整个数组R[1]到R[n]调整为一个大根堆，即把完全二叉树中以每一个结点为根的子树都调整为堆。需要将以序号为n/2，n/2－1，…，1的结点作为根的子树调整为堆用筛选法调整堆2023/7/1460调整堆示例2851336287961751(a)堆2851336287965117(b)17与51／交换后的情景2023/7/1461调整堆示例5151876228963317(d)28与87交换后调成的新堆3351516287962817(c)调整后的新堆2023/7/1462建堆示例初始关键字序列：51，33，62，96，87，17，28，51为例，其初始建大顶堆过程

3362968728175151(a)4..8是堆，不调整3362968728175151(b)3..8是堆，不调整2023/7/1463建堆示例3362968728175151(c)2..8不是堆，进行筛选9662518728175133(d)1..8不是堆，进行筛选8762515128179633(e)建成的大顶堆2023/7/1464堆排序筛选算法voidSift(RecTypeR[]，inti，intm){∥假设R[i+1..m]中各元素满足堆的定义，本算法调整R[i]使序列∥R[i..m]中各元素满足堆的性质

R[0]=R[i];

∥暂存

for(j=2*i;j<=m;j*=2){if(j<m&&R[j].key<R[j+l].key)j++;∥沿大者（右）方向筛选

if(R[0].key<R[j].key){R[i]=R[j];i=j;}

elsebreak;}∥for

R[i]=R[0];}∥Sift2023/7/1465堆排序算法voidHeapSort(RecTypeR[]，intn){∥对记录序列R[1..n]进行堆排序。

for(i=n/2;i>0;i--)∥把R[1..n]建成大顶堆

Sift(R,i,n);

for(i=n;i>1;i--)∥输出并调堆

{R[1]←→R[i];Sift(R,1,i-1);∥将R[1..i-1]重新调整为大顶堆

}∥for}∥HeapSort

堆排序的时间复杂度为O（nlog2n）

2023/7/1466时间复杂度：最坏情况下T(n)=O(nlogn)

建初始堆时间：调用SIFT过程n/2次，每次以R[i]为根的子树调整为堆。具有n个结点的完全二叉树深度是h=logn+1,第i层结点个数至多为2i-1。SIFT对深度为k的完全二叉树进行比较的关键字次数至多为2(k-1)，因此比较总次数不超过C1(n)＝2i-1*2(h-1)

=2h-1+2h-2*2+2h-3*3+…+2*(h-1)<=2*2(log2n)+1=4n重新建堆时间：排序过程中重新建堆比较总次数不超过C2(n)=2*(logn-1

+logn-2+…+log2

)<2nlogn

=O(nlogn)2023/7/1467自测题

9.已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是A.3,5,12,8,28,20,15,22,19B.3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D.3,12,5,8,28,20,15,22,19【2009年全国硕士研究生入学计算机学科专业基础综合试题】2023/7/1468

已知一组关键字

（46,58,15,45,90,18,10,62）

试写出堆排序建的初始堆和排序的过程

自测题5堆排序示例2023/7/1469

已知关键字序列(K1,K2,K3,…,Kn-1)是大根堆。

(1)试写出一算法将(K1,K2,K3,…,Kn-1,Kn)调整为大根堆；

(2)利用(1)的算法写一个建大根堆的算法。

【中科院软件所2019七.2(7分)】算法举例10.4

2023/7/1470算法举例10.4

的算法

(1)voidsift(RecTypeR[],intn){∥假设R[1..n-1]是大堆,本算法把R[1..n]调成大堆

j=n;R[0]=R[j];for(i=n/2;i>=1;i=i/2)

if(R[0].key>R[i].key){R[j]=R[i];j=i;}

else

break;R[j]=R[0];

}∥sift

(2)voidHeapBuilder(RecTypeR[],intn){for(i=2;i<=n;i++)sift(R,i);}2023/7/1471归并排序基本思想：将具有n个待排序记录的序列看成是n个长度为1的有序序列，进行两两归并，得到「n/2个长度为2的有序序列，再进行两两归并，得到「n/4个长度为4的有序序列，如此重复，直至得到一个长度为n的有序序列为止

2023/7/1472归并排序示例二趟归并排序后：[33516296]

[1728

87]

初始关键字序列：[51]

[33]

[62]

[96]

[87]

[17]

[28]

一趟归并排序后：[3351]

[6296]

[1787]

[28]

三趟归并排序后：[17

28335162

8796]2023/7/1473一趟归并排序算法voidMerge(RecTypeR[],RecTypeR1[],inti,intl,inth){∥将有序的R[i..l]和R[l+1..h]归并为有序的R1[i..h]

for(j=l+1,k=i;i<=l&&j<=h;k++)∥R中记录由小到大地并入R1if(R[i].key<=R[j].key)R1[k]=R[i++];elseR1[k]=R[j++];if(i<=l)R1[k..h]=R[i..l];∥将剩余的R[i..l]复制到R1if(j<=h)R1[k..h]=R[j..h];∥将剩余的R[j..h]复制到R1}∥Merge2023/7/1474归并排序算法voidMsort(RecTypeR[],RecTypeR1[],ints,intt){∥将R[s..t]进行2-路归并排序为R1[s..t]if(s==t)R1[s]=R[s];else{m=(s+t)/2;∥将R[s..t]平分为R[s..m]和R[m+1..t]Msort(R,R2,s,m);∥递归地将R[s..m]归并为有序的R2[s..m]Msort(R,R2,m+1,t);∥递归地R[m+1..t]归并为有序的R2[m+1..t]Merge(R2,R1,s,m,t);∥将R2[s..m]和R2[m+1..t]归并到R1[s..t]}∥if}∥MSort2023/7/1475归并排序算法voidMergeSort(RecTypeR[],intn){∥对记录序列R[1..n]作2-路归并排序。

MSort(R,R,1,n);}∥MergeSort归并排序的设计复杂度为O(nlogn)2023/7/1476自测题

10.若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A.起泡排序B.插入排序C.选择排序D.二路归并排序【2009年全国硕士研究生入学计算机学科专业基础综合试题】2023/7/1477分配排序基本思想：利用关键字的结构，通过“分配”和“收集”的办法来实现排序

分配排序可分为桶排序和基数排序两类

2023/7/1478桶排序桶排序（BucketSort）也称箱排序（BinSort），其基本思想是：设置若干个桶，依次扫描待排序记录R[1..n]，把关键字等于k的记录全部都装到第k个桶里（分配），然后，按序号依次将各非空的桶首尾连接起来（收集）。

2023/7/1479基数排序

基数排序就是一种借助“多关键字排序”的思想来实现“单关键字排序”的算法

假设n个记录待排序序列{R1,R2,…，Rn}，每个记录Ri中含有d个关键字(Ki0,Ki1,…,Kid-1),则称上述记录序列对关键字(Ki0,Ki1,…,Kid-1)有序是指：对于序列中任意两个记录Ri和Rj(1≤i<j≤n)都满足下列(词典)有序关系：(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)其中K0被称为“最主”位关键字，Kd-1被称为“最次”位关键字。2023/7/1480最高位优先MSD法：先对K0进行排序，并按K0的不同值将记录序列分成若干子序列之后，分别对K1进行排序，…，依次类推，直至最后对最次位关键字排序完成为止。最低位优先LSD法：先对Kd-1进行排序，然后对Kd-2进行排序，依次类推，直至对最主位关键字K0排序完成为止。排序过程中不需要根据“前一个”关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。实现多关键字排序通常有两种作法:2023/7/1481基数排序示例p→369→367→167→239→237→138→230→139第一次分配得到：B[0].f→230←B[0].eB[7].f→367→167→237←B[7].eB[8].f→138←B[8].eB[9].f→369→239→139←B[9].e第一次收集得到：p→230→367→167→237→138→369→239→1392023/7/1482基数排序示例第二次分配得到：B[3].f→230→237→138→239→139←B[3].eB[6].f→367→167→369←B[6].e第二次收集得到：p→230→237→138→239→139→367→167→3692023/7/1483基数排序示例第三次分配得到：B[1].f→138→139→167←B[1].eB[2].f→230→237→239←B[2].eB[3].f→367→369←B[3].e第三次收集之后便得到记录的有序序列：p→138→139→167→230→237→239→367→369

2023/7/1484基数排序的类型定义#definen待排序记录的个数typedefstruct{intkey[d];∥关键字由d个分量组成

intnext;∥静态链域

AnyTypeother;∥记录其他数据域

}SLRecType;SLRecTypeR[n+1];∥R[1..n]存放n个待排序记录typedefstruct

{intf,e;∥队列的头、尾指针

}SLQueue;SLQueueB[m]∥用队列表示桶，共m个2023/7/1485基数排序的算法intRadixSort(SLRecTypeR[],intn){∥对R[1..n]进行基数排序，返回收集用的链头指针

for(i=1;i<n;i++)∥将R[1..n]链成一个静态链表

R[i].next=i+1;R[n].next=-1;∥将初始链表的终端结点指针置空

p=1;∥p指向链表的第一个结点

for(j=d-1;j>=0;j--)∥进行d趟排序

{for(i=0;i<m;i++)∥初始化桶

{B[i].f=-1;B[i].e=-1;}∥for

while(p!=-1)∥一趟分配，按关键字的第j个分量进行分配

{k=R[p].key[j];∥k为桶的序号

if(B[k].f==-1)B[k].f=p;∥B[k]为空桶，将R[p]链到桶头

elseR[B[k].e].next=p;∥将R[p]链到桶尾

B[k].e=p;∥修改桶的尾指针

p=R[p].next;∥扫描下一个记录

}∥while＝＝＝接下页＝＝＝

2023/7/1486基数排序的算法（续）＝＝＝接上页＝＝＝

i=0;//一趟收集

while(B[i].f==-1)i++;∥找第一个非空的桶

t=B[i].e;p=B[i].f∥p为收集链表的头指针,t为尾指针

while(i<m-1){i++;∥取下一个桶

if(B[i].f!=-1){R[t].next=B[i].f;t=B[i].e;}∥连接非空桶

}∥whileR[t].next=-1;∥本趟收集完毕，将链表的终端结点指针置空

}∥forreturnp;}∥RadixSort2023/7/1487基数排序的性能分析基数排序的时间复杂度是O(d*(rd+n))。当n较小、d较大时，基数排序并不合适。只有当n较大、d较小时，特别是记录的信息量较大时，基数排序最为有效。基数排序存储空间复杂度为O（rd）。基数排序是稳定的。2023/7/1488自测题6已知8个记录，其关键字分别为

(179，208，306，093，859，984，271，033)

试用基数排序法实施排序，描述其排序过程

2023/7/1489排序方法平均时间最坏情况辅助空间稳定性直接插入排序O（n2）O（n2）O（1）稳定起泡排序O（n2）O（n2）O（1）稳定直接选择排序O（n2）O（n2）O（1）不稳定希尔排序O（n1.3）O（n1.3）O（1）不稳定快速排序O（nlog2n）O（n2）O（log2n）不稳定堆排序O（nlog2n）O（nlog2n）O（1）不稳定2-路归并排序O（nlog2n）O（nlog2n）O（n）稳定基数排序O(d*(rd+n))O(d*(rd+n))O(rd)稳定内部排序方法的比较2023/7/1490内部排序小结（1）若n较小（如n≤50），可采用直接插入排序或直接选择排序。（2）若待排序记录的初始状态已是按关键字基本有序，则选用直接插入排序或起泡排序为宜。（3）当n较大，若关键字有明显结构特征（如字符串、整数等），且关键字位数较少易于分解，采用时间性能是线性的基数排序较好。若关键字无明显结构特征或取值范围属于某个无穷集合（例如实数型关键字）时，应借助于“比较”的方法来排序，可采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。2023/7/1491（4）对于以主关键字进行排序的记录序列，所用的排序方法是否稳定无关紧要，而用次关键字进行排序的记录序列，应根据具体问题所需慎重选择排序方法及描述算法。（5）前面讨论的排序算法，大都是利用一维向量实现的。若记录本身信息量大，为避免移动记录耗费大量时间，可用链式存储结构。比如插入排序和归并排序都易于在链表上实现。但象快速排序和堆排序这样的排序算法，却难于在链表上实现，此时可以提取关键字建立索引表，然后对索引表进行排序。内部排序小结（续）2023/7/1492以关键码序列（503，087，512，061，908，170，897，275，653，246）为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：（1）直接插入排序；（2）希尔排序（增量5，3，1）；（3）起泡排序（4）快速排序；（5）简单选择排序（6）堆排序；（7）归并排序；（8）基数排序。自测题72023/7/1493自测题8

选择题下列内部排序算法中：

A.快速排序B.直接插入排序C.二路归并排序D.简单选择排序E.起泡排序F.堆排序(1)其比较次数与序列初态无关的算法是()(2)不稳定的排序算法是()(3)在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序，k<<n)的情况下，排序效率最高的算法是()(4)排序的平均时间复杂度为O(n•logn)的算法是(),为O(n•n)的算法是()【北京工业大学2000一.1(10分每问2分)】2023/7/1494自测题9

选择题设被排序的结点序列共有N个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为()。

A.O(N)，O(N)，O(N)B.O(N)，O(N*log2N),O(N*log2N)C.O(N)，O(N*log2N),O(N2)D.O(N2)，O(N*log2N),O(N2)【上海交通大学2019四.5(2分)】2023/7/1495自测题10

选择题一个排序算法的时间复杂度与()有关。A.排序算法的稳定性B.所需比较关键字的次数C.所采用的存诸结构D.所需辅助存诸空间的大小【华中科技大学2019一.8(1分)】2023/7/1496自测题11

选择题一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为()。A.(38,40,46,56,79,84)B.(40,38,46,79,56,84)C.(40,38,46,56,79,84)D.(40,38,46,84,56,79)【燕山大学2019一.4(2分)】2023/7/1497自测题12

选择题有些排序算法在每趟排序过程中，都会有一个元素被放置在其最终的位置上，下列算法不会出现此情况的是()。

A.SHELL排序

B.堆排序

C.冒泡排序

D.快速排序【北京交通大学2019一.7(2分)】2023/7/1498自测题13

选择题在下列排序方法中，()方法可能出现这种情况：在最后一趟开始之前，所有的元素都不在其最终应在的正确位置上。A、快速排序B、冒泡排序C、堆排序D、插入排序

【武汉理工大学2019一.10(26/12分)】2023/7/1499自测题14

选择题就分类算法所用的辅助空间而言，堆分类、快速分类和归并分类的关系是()。A.堆分类<快速分类<归并分类B.堆分类<归并分类<快速分类C.堆分类>归并分类>快速分类D.堆分类>快速分类>归并分类【哈尔滨工业大学2019二.6(1分