第10章排序(上课用)讲述

数据结构主讲人：张立震e-mail:system0@打扑克例子世界杯比赛排名阿根廷法国阿根廷意大利法国意大利法国英国中国巴西巴西阿根廷西班牙葡萄牙阿根廷例子数据结构期末成绩排名学号姓名成绩1110810113刘德华981110810221陈鑫961110820109刘亦菲911110820104黄渤871110820116顼晓宇83………例子第十章内部排序10.1概述10.2插入排序(直接插入、折半插入、希尔排序)10.3交换排序(冒泡排序、快速排序)10.4选择排序(简单选择、树形选择、堆排序)10.5归并排序10.6基数排序10.7各种排序小结排序：整理文件中的记录，使之按关键字递增

(或递减)次序排列起来。关键字：以数据对象的多个属性域中的一个为排序依据，该属性域即为关键字。如何排序什么是排序？为什么排序？？内部排序外部排序将欲处理的数据整个存放到内部存储器中排序，数据可被随机存取交换式排序选择式排序插入式排序由于排序期间数据太多，需要借助外部的辅助存储器，不断在内、外存只见移动的排序，数据不可随机存取

排序的分类归并排序基数排序排序算法衡量标准稳定性不稳定性排序过后能使值相同的数据保持原顺序中的相对位置

排序过后不能使值相同的数据保持原顺序中的相对位置

49325649272732494956时间复杂度（最好情况和最坏情况）空间复杂度稳定性排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。

本教材定义的待排数据表类型

typedefstruct{KeyTypekey;//关键字项

InfoTypeotherinfo;//其他数据项

}RedType;typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或作哨兵

intlength;}SqList;

直接插入排序(InsertSort)

折半插入排序(BinaryInsertSort)

2-路插入排序（略）表插入排序（略）希尔排序(ShellSort)10.2插入排序基本思想

每步将一个待排序的对象，按其排序码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。基本思想：顺序地把待排序的数据元素按其值的大小插入到已排序数据元素子集合的适当位置。有序序列无序序列1.直接插入排序(InsertSort)12578630941256783094基本思想：顺序地把待排序的数据元素按其值的大小插入到已排序数据元素子集合的适当位置。1.直接插入排序(InsertSort)

当插入第i(i

1)个对象时，前面的r[1],…,r[i-1]已经排好序。这时，用r[i]的排序码与r[i-1],r[i-2],…的排序码顺序进行比较，找到插入位置即将V[i]插入，原来位置上的对象向后顺移。子集合的数据元素个数从只有一个数据元素开始逐次增大。当子集合大小最终和集合大小相同时排序完毕。647]896468989646464直接插入排序[64]789624[5]89624[57]624[5724[56][567246489]578924初始序列:第1趟排序:第2趟排序:第3趟排序:第4趟排序:第5趟排序:jjjj6Temp6

直接插入排序的算法(p265算法10.1)voidInsertSort(SqList&L){inti,j;for(i=2;i<=L.length;++i) if(LT(L.r[i].key,L.r[i-1].key)){//"<"时，需将L.r[i]插入有序子表

L.r[0]=L.r[i];//L.r[0]为监视哨

for(j=i-1;LT(L.r[0].key,L.r[j].key);--j) L.r[j+1]=L.r[j]; //记录后移

L.r[j+1]=L.r[0];//插入到正确位置

}

}最坏情况下

最好情况下比较次数：n-1移动次数：0算法分析比较次数：移动次数：2)1)(2(2-+=å=nnini2)1)(4(1-+=+ånnin2=i）（（正序）

（逆序）直接插入排序的时间复杂度为O(n2)。空间性能：需要一个记录的辅助空间（监视哨）。稳定性：直接插入排序算法是一种稳定的排序算法。特点：简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。算法分析2464[57]624[576489]896第2趟排序:第3趟排序:temp62.折半插入(BinaryInsertSort)

基本思想：在查找插入位置时，使用折半查找算法。如何提高查找效率呢？642.折半插入(BinaryInsertSort)

基本思想：在查找插入位置时，使用折半查找算法。如何提高查找效率呢？[57]624[576489]896第2趟排序:第3趟排序:temp689647low6mhighvoidBInsertSort(SqList&L){inti,j,high,low,m;for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//将L.r[i]暂存到L.r[0]

low=1;high=i-1;

while(low<=high)//在r[low..high]中折半查找有序插入的位置

{m=(low+high)/2;//折半

if(LT(L.r[0].key,L.r[m].key))high=m-1;//插入点在低半区

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

}for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//记录后移

L.r[high+1]=L.r[0];//插入

}}//BInsertSort折半插入排序算法时间性能分析：移动次数与直接插入排序相同比较次数与初始顺序无关，只依赖于记录个数插入每个记录需要log2i次比较时间复杂度为O(n2)。空间代价:

与直接插入排序相同稳定性:

稳定算法分析

基本思想：把待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序；小组的个数逐次缩小；当完成了所有数据元素都在一个组内的排序后排序过程结束。希尔排序又称作缩小增量排序。3.希尔排序(ShellSort)开始时

gap（间隔值）

的值较大，子序列中的对象较少，排序速度较快；随着排序进展，gap

值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。希尔排序过程653425871238564614779223566514257787382356341477122365462587923865771234561214653423774625879238121423253438465665778792结果序列gap=6gap=3gap=1voidShellInsert(SqList&L,intgap){

//对顺序表L作一趟希尔插入排序。本算法对算法10.1作了以下修改：

//1.前后记录位置的增量是gap，而不是1；

//2.r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。

inti,j;for(i=gap+1;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-gap].key)){//将L.r[i]插入有序增量子表

L.r[0]=L.r[i];//暂存在L.r[0]

for(j=i-gap;j>0&<(L.r[0].key,L.r[j].key);j-=gap)

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

L.r[j+gap]=L.r[0];//插入

}}//ShellInsert希尔排序的算法(算法10.4)voidShellSort(SqList&L,intdlta[],intt){//按增量序列dlta[0..t-1]对顺序表L作希尔排序。

for(intk=0;k<t;++k)ShellInsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序}//ShellSort希尔排序的算法(算法10.5)算法分析对特定的待排序序列，可准确地估算关键字的比较次数和对象移动次数。但想要弄清关键字比较次数和对象移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。增量序列的取法有多种。最初shell提出取gap=n/2，gap=gap/2，直到gap=1。后来Knuth提出取gap=gap/3+1。还有人提出各gap互素为好。Knuth利用大量的实验统计资料得出，当n很大时，关键字平均比较次数和对象平均移动次数大约在n1.25到1.6n1.25的范围内。

冒泡排序(BubbleSort)

快速排序(QuickSort)10.3交换排序基本思想

两两比较待排序对象的关键字，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有对象都排好序为止。基本思想：设待排序序列中的对象个数为n，最多作n-1趟排序。在第i

趟中顺次两两比较r[j].Key和r[j+1].Key，

j=1,2,…,i-1;i=n,n-1,…,2.如果发生逆序，则交换r[j]和r[j+1]。1.冒泡排序(BubbleSort)冒泡排序4938659776132749979797384927137665493849276513493849271349384927133827137676654949382713特点：

n

个数排序共需进行n-1趟比较第i趟共需进行n-i次比较冒泡排序的原始算法voidBubbleSort(SqList&L){//将L中整数序列排列成自小至大有序的序列

for(i=n;i>=2;--i)for(j=1;j<i;++j)if(L.r[j].key>L.r[j+1].key){ElemTypetemp=L.r[j];//交换

L.r[j]=L.r[j+1];

L.r[j+1]=temp;

}}问题：刚才的改进算法是否已经最优?冒泡排序的改进算法123456789123456789123456789123456789

如何解决呢？

冒泡排序的改进算法voidBubbleSort(SqList&L){for(i=n,Change=TRUE;i>=2&&Change;--i){Change=FALSE;for(j=1;j<i;++j)if(L.r[j].key>L.r[j+1].key){ElemTypetemp=L.r[j]; L.r[j]=L.r[j+1]; L.r[j+1]=temp;Change=TRUE;}}}最坏情况（逆序）：最好情况（正序）：比较次数：n-1移动次数：0

比较次数：移动次数：2)1(1-=å=nn(n-i)n-1i2)1(1-=å=n3n3(n-i)n-1i算法分析

时间复杂度为O(n2)

稳定性：稳定基本思想：任取待排序对象序列中的某个对象（例如取第一个对象）作为枢轴(pivot)，按照该对象的关键字大小，将整个对象序列划分为左右两个子序列：2.快速排序(QuickSort)左侧子序列中所有对象的关键字都小于枢轴对象的关键字。右侧子序列中所有对象的关键字都大于或等于枢轴对象的关键字。枢轴对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。一趟快速排序的具体过程4938659776132749pivot=49lowhigh27low65high13low97highhigh49第一趟结果：

[273813]49[76976549]小于49大于等于49快速排序每一趟的划分

intPartition(SqList&L,intlow,inthigh){/*交换顺序表L中子表r[low…high]的记录，枢轴记录到位，并返回其所在的位置，此时在它之前（后）的记录均不大（小）于它*/}//Partition

快速排序每一趟的划分

intPartition(SqList&L,intlow,inthigh){/*交换顺序表L中子表r[low…high]的记录，枢轴记录到位，并返回其所在的位置，此时在它之前（后）的记录均不大（小）于它*/

L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录

intpivotkey=L.r[low].key;//枢轴记录关键字}//Partition

快速排序每一趟的划分

intPartition(SqList&L,intlow,inthigh){/*交换顺序表L中子表r[low…high]的记录，枢轴记录到位，并返回其所在的位置，此时在它之前（后）的记录均不大（小）于它*/

L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录

intpivotkey=L.r[low].key;//枢轴记录关键字

while(low<high){}}//Partition

快速排序每一趟的划分

intPartition(SqList&L,intlow,inthigh){/*交换顺序表L中子表r[low…high]的记录，枢轴记录到位，并返回其所在的位置，此时在它之前（后）的记录均不大（小）于它*/

L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录

intpivotkey=L.r[low].key;//枢轴记录关键字

while(low<high){}L.r[low]=L.r[0];//枢轴记录到位

returnlow;//返回枢轴位置

}//Partition

快速排序每一趟的划分

intPartition(SqList&L,intlow,inthigh){/*交换顺序表L中子表r[low…high]的记录，枢轴记录到位，并返回其所在的位置，此时在它之前（后）的记录均不大（小）于它*/

L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录

intpivotkey=L.r[low].key;//枢轴记录关键字

while(low<high){while(low<high&&L.r[high].key>=pivotkey)--high;

}L.r[low]=L.r[0];//枢轴记录到位

returnlow;//返回枢轴位置

}//Partition

快速排序每一趟的划分

intPartition(SqList&L,intlow,inthigh){/*交换顺序表L中子表r[low…high]的记录，枢轴记录到位，并返回其所在的位置，此时在它之前（后）的记录均不大（小）于它*/

L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录

intpivotkey=L.r[low].key;//枢轴记录关键字

while(low<high){while(low<high&&L.r[high].key>=pivotkey)--high;L.r[low]=L.r[high];//将比枢轴记录小的记录移到低端

}L.r[low]=L.r[0];//枢轴记录到位

returnlow;//返回枢轴位置

}//Partition

快速排序每一趟的划分

intPartition(SqList&L,intlow,inthigh){/*交换顺序表L中子表r[low…high]的记录，枢轴记录到位，并返回其所在的位置，此时在它之前（后）的记录均不大（小）于它*/

L.r[0]=L.r[low];//用子表的第一个记录作枢轴记录

intpivotkey=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;//返回枢轴位置

}//Partition

快速排序算法voidQSort(SqList&L,intlow,inthigh){//对顺序表L中的子序列L.r[low…high]作快速排序

if(low<high)//长度大于1{pivotloc=Partition(L,low,high);//将L.r[low..high]一分为二

QSort(L,low,pivotloc-1);//对低子表递归排序

QSort(L,pivotloc+1,high);//对高子表递归排序

}}//QSort算法分析最理想的情况：每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同。就平均时间而言，快速排序是最好的一种内部排序方法。平均计算时间是O(nlog2n)最坏情况：初始关键字有序或基本有序。此时快速排序蜕化为冒泡排序，时间复杂度为O(n2)。占用附加存储(即栈)将达到O(n)。快速排序是一种不稳定的排序方法。对于n较大的平均情况而言，快速排序是“快速”的，但是当n

很小时，这种排序方法往往比其它简单排序方法还要慢。

简单选择排序(SimpleSelectionSort)

树形选择排序(TreeSelectionSort)

堆排序(HeapSort)10.4选择排序基本思想

每一趟(例如第i趟,i=1,…,n-1)在后面n-i+1个待排序记录中选出排序码最小的记录,作为有序序列中的第i个记录。待到第n-1趟作完,待排序记录只剩下1个,就不用再选了。基本思想：i从1开始，直到n-1，进行n-1趟排序。第i

趟的排序过程为：在一组对象r[i]～r[n](i=1,2,…,n-1)中选择具有最小关键字的对象，并和第i个对象进行交换。1.简单选择排序(SimpleSelectionSort)一趟简单选择排序的过程149238365497576613727849ki=1jkjjjjkjjk1349149238365497576613727849i=kjjjjjj1349kk2一趟简单选择排序的过程voidSelectSort(SqList&L){for(inti=1;i<L.length;i++){k=SelectMinKey(L,i);if(i!=k){ElemTypetemp=L.r[i];L.r[i]=L.r[k];L.r[k]=temp;}}}intSelectMinKey(SqList&L,inti){intm=i; for(j=i+1;j<=L.length;j++)if(L.r[j].key<L.r[m].key) m=j;//当前具最小关键码的对象

returnm; }简单选择排序的算法最坏情况：算法分析移动次数：最好情况：比较次数：)()1(21211nOnninni=-=-å-=）（

时间复杂度为O(n2)。

稳定性：不稳定为什么？0次3(n-1)次世界杯比赛排名巴西法国巴西意大利法国意大利法国英国中国巴西巴西阿根廷西班牙葡萄牙阿根廷8个国家参加世界杯，需要多少次比赛得出冠军？树形选择排序又称为锦标赛排序。基本思想：与体育比赛时的淘汰赛类似。首先取得n个对象的关键码，进行两两比较，得到n/2

个比较的优胜者(关键码小者)，作为第一步比较的结果保留下来。然后对这n/2

个对象再进行关键码的两两比较，…，如此重复，直到选出一个关键码最小的对象。2.树形选择排序(TreeSelectionSort)133813973865493876131327652749139749387613652749381338651327∞27382738657627279749387613652749382738657627∞13∞38384938657649锦标赛排序构成的树是满的完全二叉树，其深度为log2(2n-1)取上整，其中n为待排序元素个数。除第一次选择具有最小关键字的对象需要进行n-1次关键字比较外，重构胜者树选择具有次小、再次小关键字对象所需的关键字比较次数均为O(log2n)。总关键字比较次数为O(nlog2n)。对象的移动次数不超过关键字的比较次数，所以锦标赛排序总的时间复杂度为O(nlog2n)。这种排序方法虽然减少了许多排序时间，但是使用了较多的附加存储。锦标赛排序是一个稳定的排序方法。算法分析3.堆排序(HeapSort)堆定义：n

个元素的序列{k1,k2,…,kn}当且仅当满足下列关系时，称之为堆。

ki≤k2i

ki≥k2i

ki≤k2i+1

ki

≥

k2i+1其中，i=1,2,…,[n/2].前者称为最小堆，后者称为最大堆。或最小堆与最大堆举例9683273811091236248547913053最大堆最小堆基本思想：在输出堆顶的最小值之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素中的次小值。反复执行，直到得到一个有序序列。堆排序分为两个步骤：根据初始输入数据形成初始堆；通过一系列的对象交换和重新调整堆进行排序。3.堆排序(HeapSort)关键问题：如何由一个无序序列建成一个堆?如何调整余下的元素成为一个新堆?3.堆排序(HeapSort)堆调整过程1338277697654949rc=13492525*211608123456082525*16214913654249252125*160808252125*1649交换1

号与6号对象,6号对象就位初始最大堆堆调整2525*082116491234561625*082521491365422525*210816491625*210825

49交换1

号与5号对象,5号对象就位从1号到5号重新调整为最大堆堆调整25*1608212549123456081625*25214913654225*16210825

4908162125*

25

49交换1

号与4号对象,4号对象就位从1号到4号重新调整为最大堆堆调整211625*082549123456081625*25214913654221160825*

25

49081621

25*

25

49交换1

号与3号对象,3号对象就位从1号到3号重新调整为最大堆堆调整160825*212549123456081625*25214913654216082125*

25

490816

21

25*

25

49交换1

号与2号对象,2号对象就位从1号到2号重新调整为最大堆堆调整212525*491608123456i212525*164908136542i21254925*1608初始关键字集合21254925*1608i=3时的局部调整建立初始的最大堆212525*491608123456i492525*16210813654221254925*160849252125*1608i=1时的局部调整形成大顶堆i=2时的局部调整建立初始的最大堆最大堆的第一个对象r[1]具有最大的关键字，将r[1]与r[n]对调，把具有最大关键字的对象交换到最后，再对前面的n-1个对象，使用堆的调整算法HeapAdjust(1,n-1)，重新建立最大堆。结果具有次最大关键字的对象又上浮到堆顶，即r[1]位置。再对调r[1]和r[n-1]，调用HeapAdjust(1,n-2)，对前n-2个对象重新调整。如此反复执行，最后得到全部排序好的对象序列。这个算法即堆排序算法。typedefSqListHeapType;//顺序存储方式基于初始堆进行堆排序voidHeapAdjust(HeapType&H,ints,intm){//调整H.r[s]的关键字，使H.r[s…m]成为一个大顶堆

ElemTyperc=H.r[s];

for(intj=2*s;j<=m;j*=2)//沿较大的孩子结点向下筛选

{if((j<m)&&(LT(H.r[j].key,H.r[j+1].key)))++j;//j为key较大的结点下标

if(!(LT(rc.key,H.r[j].key)))break;//找到rc待插位置s

H.r[s]=H.r[j];s=j;/*改变后的局部子堆顶的值，s随着

j的向下移动而向下移动*/

}

H.r[s]=rc;//插入}最大堆的向下调整算法voidHeapSort(HeapType&H){inti;RedTypetemp;for(i=H.length/2;i>0;--i)//把H.r[1..H.length]建成大顶堆

HeapAdjust(H,i,H.length);for(i=H.length;i>1;--i){temp=H.r[i];H.r[i]=H.r[1];H.r[1]=temp;/*将堆顶记录和当前未经排序子序列Hr[1..i]中

最后一个记录相互交换*/

HeapAdjust(H,1,i-1);//将H.r[1..i-1]重新调整为大顶堆

}}//HeapSort堆排序算法算法分析适宜记录较多的文件在最坏的情况下，时间复杂度为O(nlog2n)堆排序是一个不稳定的排序方法。10.5归并排序基本思想

将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到

n/2

个长度为2的有序序列，再进行两两归并，得到

n/4个长度为4的有序序列，……，直至得到一个长度为n的有序序列为止。归并排序过程<初态>(49)(38)(65)(97)(76)(13)(27)(3849)(13273849657697)<第1趟>(6597)(1376)(27)<第2趟>(38496597)(132776)<第3趟>voidMerge(ElemTypeSR[],ElemTypeTR[],inti,intm,intn){for(intj=m+1,k=i;i<=m&&j<=n;++k){if(LQ(SR[i].key,SR[j].key))TR[k]=SR[i++]; elseTR[k]=SR[j++];}

if(i<=m)for(intn1=k,n2=i;n1<=n&&n2<=m;n1++,n2++) TR[n1]=SR[n2];if(j<=n)for(intn1=k,n2=j;n1<=n&&n2<=n;n1++,n2++) TR[n1]=SR[n2];}二路归并排序算法voidMSort(ElemTypeSR[],ElemTypeTR1[],ints,intt){ElemTypeTR2[MAXSIZE];if(s==t)TR1[s]=SR[s];else{intm=(s+t)/2; MSort(SR,TR2,s,m); MSort(SR,TR2,m+1,t); Merge(TR2,TR1,s,m,t); }}voidMergeSort(SqList&L){MSort(L.r,L.r,1,L.length);}二路归并排序算法在归并排序算法中，递归深度为O(log2n)，对象关键字的比较次数为O(nlog2n)。算法总的时间复杂度为O(nlog2n)。归并排序占用附加存储较多，需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。归并排序是一个稳定的排序方法。算法分析10.6基数排序基本思想

基数排序是按组成关键字的各位的值进行“分配”和“收集”，与前面介绍的排序方法不同，它无需进行关键字之间的比较，而是借助多关键字进行排序。多关键字对象X=(K1,K2,…,Kd)以扑克牌排序为例。每张扑克牌有两个“关键字”：花色和面值。其有序关系为：花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A如果把所有扑克牌排成以下次序：

2,…,A,2,…,A,2,…,A,2,…,A这就是多关键字排序。排序后形成的有序序列叫做词典有序序列。多关键字排序一般情况下，假定有一个n

个对象的序列

{V0,V1,…,Vn-1}，且每个对象Vi

中含有d

个关键字如果对于序列中任意两个对象Vi和Vj(0

i<j

n-1)都满足：则称序列对关键字(K1,K2,…,Kd)有序。其中，K1

称为最高位关键字，Kd

称为最低位关键字。多关键字排序如果关键字是由多个数据项组成的数据项组，则依据它进行排序时就需要利用多关键字排序。实现多关键字排序有两种常用的方法最高位优先MSD(MostSignificantDigitfirst)最低位优先LSD(LeastSignificantDigitfirst)多关键字排序原始序列：278109063930589184505269008083第一遍：按个位数放入10个箱子（队列）01234567890123456789278012345678910901234567890630123456789930012345678958901234567891840123456789505012345678926901234567890080123456789083按0-9的顺序从10个箱子中收集数字第一趟收集的序列：930

063083

184

505

278008

109589269

收集序列：930

063083

184

505

278008

109589269

第二遍：按十位数放入10个箱子（队列）按0-9的顺序从10个箱子中收集数字第二趟收集的序列：50500810993006326927808318458901234567890123456789930012345678906301234567890830123456789184012345678950501234567892780123456789008