数据结构 第十章 排序

1第十章内部排序本章目标熟练掌握各内部排序方法的基本思想；理解排序方法“稳定”和“不稳定”的含义。掌握排序过程和实现算法；掌握各种排序方法时间复杂度的分析方法；了解各种排序方法的特点（比较和选择）。10.2

插入排序10.3

交换排序10.4

选择排序10.1

概述10.5

归并排序10.6

基数排序10.7

各种内部排序方法的比较10.1概述所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。各科成绩表；奖学金评定综合分；...？什么是排序？为什么排序？如何排序？内部排序外部排序 将欲处理的记录全部存放到内存中排序，数据可被随机存取插入式排序交换式排序选择式排序待排序的记录太多，不能同时存放内存中，排序过程需要借助外存（比如：硬盘）来完成，记录需要在内存和外存间移动。

排序的分类归并排序基数排序比较标准稳定性不稳定性 排序过后能使关键字相等的记录保持原顺序中的相对位置 排序过后不能使关键字相等的记录保持原顺序中的相对位置49325649272732494956时间复杂度空间复杂度稳定性排序算法的基本操作大多数排序算法都有两个基本的操作：(1)比较两条记录的关键字(排序码)大小；(2)移动记录本身或改变指向记录的指针。

注意：

第(2)种基本操作的实现依赖于待排序记录的存储方式。据此可分为静态排序和动态排序。#defineMAXSIZE20

//顺序表的最大长度typedefintKeyType;

//定义关键字类型为整数类型typedefstruct

{

KeyTypekey;

//关键字项

InfoTypeotherinfo;

//其他数据项}RedType；

//记录类型typedefstruct{

RedTyper[MAXSIZE+1];

//r[0]闲置或作哨兵单元

intlength;

//顺序表的当前长度}SqList;

//顺序表类型待排记录的数据类型--顺序存储结构10.2

插入排序10.3

交换排序10.4

选择排序10.1

概述10.5

归并排序10.6

基数排序10.7

各种内部排序方法的比较10.2

插入排序

2.

折半插入排序3.2-路插入排序4.表插入排序

1.直接插入排序5.希尔排序基本思想：（1）排序过程分步完成；（2）每步将一个待排序的记录，按其关键字大小，插入到前面已经排好序的一组记录（有序序列）的适当位置上；（3）通过若干步，便可将所有记录全部插入，从而完成排序。通常，将这里的每个步骤称为“趟”。1.直接插入排序基本操作：将一个待排序的记录按其关键字的大小插入到前面已排好序的有序序列中。有序序列无序序列125786309412567830941.直接插入排序有序序列从只有一个记录开始逐次增大；当插入第i(i>=2)个记录r[i]时，前面的r[1],r[2],…,r[i-1]已经排好序。这时，用r[i]的关键字与r[i-1],r[i-2],…的关键字依次进行比较，找到插入位置后将r[i]插入，原来位置上及以后的所有记录顺次向后移动；当有序序列大小最终和原始记录集大小相同时排序完毕。1.直接插入排序[64]789624[564]89624[5764]624[576489]24[5676489][567246489]5789624初始序列:第一趟排序:第二趟排序:第三趟排序:第四趟排序:第五趟排序:Temp6j89j64j7j61.直接插入排序算法:voidInsertSort（SqList&L）{for(i=2;i<=L.length;++i)ifLT(L.r[i].key,L.r[i-1].key){

L.r[0]=L.r[i];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];}}1.直接插入排序最坏情况下（逆序）：时间复杂度为O(n2)比较次数：移动次数：2)1)(2(1-+=å=nn

(i+1)n-1i2)1)(4(2-+=+ånnin-11=i）（最好情况下（正序）：

比较次数：n-1移动次数：0时间复杂度为O(n)性能分析:空间性能：需要一个记录的辅助空间。直接插入排序算法是一种稳定的排序算法。特点：简单、容易实现，适用于待排序记录基本有序或待排序记录较少的情形。2.折半插入排序[5764]624[576489]24896第二次排序:第三次排序:Tfmp689647low6基本思想:在查找插入位置时,使用折半查找算法。mhigh2.折半插入排序算法:voidBInsertSort(SqList&L){

for(i=2;i<=L.length;++i){L.r[0]=L.r[i];low=1;high=i-1;

while(low<=high){m=(low+high)/2;

ifLT(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];}//for}//BInsertSort2.折半插入排序稳定空间代价：O(1)时间代价：比较次数与待排记录的初始顺序无关，只依赖记录个数插入每个记录需要O(log2i)次比较

最多移动i+1次，最少2次（临时记录）

最佳情况下总时间代价为O(nlog2n)，最差和平均情况下仍为O(n2)3.2-路插入排序基本思想：增设同类型数组d,视为循环向量。以d[1]为中心，原数列中比d[1]小的往前插，比d[1]大的往后插原数列：4938659776132749d数组：49d1firstfinal38first6597final76final13first27first9749finalvoidTwoWaySort(SqList&L){intfirst=1,final=1,i,j;RedTyped[MAXSIZE+1];//辅助存储d[1].key=L.r[1].key;for(i=2;i<=L.length;i++){if(L.r[i].key>=d[1].key){//插入d1后for(j=final;d[j].key>L.r[i].key;j--)d[j+1].key=d[j].key;d[j+1].key=L.r[i].key;final++;}else{//插入d1前if(first==1){first=MAXSIZE-1;d[first].key=L.r[i].key;}else{for(j=first;d[j].key<L.r[i].key&&d[j].key&&j<MAXSIZE;j++)d[j-1].key=d[j].key;d[j-1].key=L.r[i].key;first--;}}}//forfor(i=first,j=1;L.r[j].key;i=i%(MAXSIZE-1)+1,j++)L.r[j].key=d[i].key;//将序列复制回去}4.希尔排序

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

4.希尔排序653425871238564614779223566514257787382356341477122365462587923865771234561214653423774625879238121423253438465665778792结果序列4.希尔排序voidShellInsert(SqList&L,intdk)

{

//1.前后记录位置的增量是dk,而不是1;

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

for(i=dk+1;i<=L.length;++i)

if(LT(L.r[i].key,L.r[i-dk].key)){//需将L.r[i]插入有序增量子表L.r[0]=L.r[i];//暂存在L.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];//插入}}4.希尔排序voidShellSort(SqList&L,intdlta[],intt){//按增量序列dlta[0..t-1]对顺序表L作希尔排序。

for(k=0;k<t;++k)

ShellInsert(L,dlta[k]);//一趟增量为dlta[k]的插入排序}Gap的取法有多种。最初shell提出取gap=n/2，gap=gap/2，直到gap=1。后来knuth提出取gap=gap/3+1。还有人提出都取奇数为好，也有人提出各gap互质为好。10.2

插入排序10.3

交换排序10.4

选择排序10.1

概述10.5

归并排序10.6

基数排序10.7

各种内部排序方法的比较起泡排序基本思想：设数组a中存放了n个数据元素，循环进行n-1趟如下的排序过程：依次比较相邻两个数据元素，若a[i]>a[i+1]，则交换两个数据元素，否则不交换。当完成一趟交换以后，最大的元素将会出现在数组的最后一个位置。依次重复以上过程，当第n-1趟结束时，整个n个数据元素集合中次小的数据元素将被放置在a[1]中，a[0]中放置了最小的数据元素。起泡排序4938659776132749979797384927137665493849276513493849271349384927133827137676654949382713特点：1.n个数排序共需进行n-1趟比较2.第i趟共需要进行n-i次比较起泡排序的原始算法voidbubble_sort(SqList&L){//将a中整数序列排列成自小至大有序的序列(起泡排序)

for(i=1,i<=L.length-1;++i)for(j=1;j<=L.length-1;++j)if(LT(L.r[j+1].key,L.r[j].key))L.r[j]←→L.r[j+1]；}起泡排序的改进算法（一）voidbubble_sort(SqList&L){//将a中整数序列排列成自小至大有序的序列(起泡排序)for(i=1;i<=L.length-1;++i)for(j=1;j<=L.length-i;++j)if(LT(L.r[j+1].key,L.r[j].key))L.r[j]←→L.r[j+1]}115246175115617524115617524161551724注意第i趟比较了n-i次，则可以有效的较少比较次数问题：刚才的改进算法是否已经最优?起泡排序的改进算法（二）123456789123456789123456789

123456789

分析：因为给定的待排序序列已经是一个正序的序列，经过第一趟的比较以后，已经没有交换发生，但是算法仍然会继续执行。解决：添加一个算法的结束条件，即当某一趟排序过程中只有比较而没有交换的时候，就认定序列已经有序，可以提前结束循环。起泡排序的改进算法（二）voidbubble_sort(SqList&L){//将a中整数序列排列成自小至大有序的序列(起泡排序)for(i=1,chang=TRUE；(i<=L.length-1)&&chang;++i){chang=FALSE;for(j=1;j<L.length-i;++j)if(LT(L.r[j+1].key,L.r[j].key)){L.r[j]

←→L.r[j+1];

change=TRUE;}}}最坏情况（反序）：最好情况（正序）：比较次数：n-1移动次数：0

时间复杂度为O(n)；时间复杂度为O(n2)。比较次数：移动次数：2)1(1-=å=nn(n-i)n-1i2)1(1-=å=n3n3(n-i)n-1i平均情况：时间复杂度为O(n2)。时间性能分析快速排序算法思想：指定枢轴(通常为第一个记录)通过一趟排序将以枢轴为中心，把待排记录分割为独立的两部分，使得左边记录的关键字小于枢轴值，右边记录的关键字大于枢轴值对左右两部分记录序列重复上述过程，依次类推，直到子序列中只剩下一个记录或不含记录为止。快速排序4938659776132749pivotkey=49lowhigh27low65high13low97highhigh49第一趟结果：[273813]49[76976549]小于49大于等于49快速排序算法

intPartition(SqList&L,intlow,inthigh){L.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;//返回枢轴位置}快速排序算法

voidQSort(SqList&L,intlow,inthigh){//对顺序表L中的//长度大于1

if(low<high){pivotloc=Partition(L,low,high);//将L.r[low..high]一分为二QSort(L,low,pivotloc-1);//对低子表递归排序，pivotloc是枢轴位置QSort(L,pivotloc+1,high);//对高子表递归排序

}}

voidQuickSort(SqList&L){//对顺序表L作快速排序。算法10.8

QSort(L,1,L.length);}算法分析在n个元素的序列中，对一个对象定位所需时间为O(n)。若设t(n)是对n个元素的序列进行排序所需的时间，而且每次对一个对象正确定位后，正好把序列划分为长度相等的两个子序列，此时，总的计算时间为：T(n)cn+2t(n/2) //c是一个常数cn+2(cn/2+2t(n/4))=2cn+4t(n/4)2cn+4(cn/4+2t(n/8))=3cn+8t(n/8)………cnlog2n+nt(1)=o(nlog2n)10.2

插入排序10.3

交换排序10.4

选择排序10.1

概述10.5

归并排序10.6

基数排序10.7

各种内部排序方法的比较直接选择排序基本思想：从待排序的数据元素集合中选取最小的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置上数据元素的集合中选取最小的数据元素并将它与原始数据元素集合中的第二个数据元素交换位置；如此重复，直到数据元素集合中只剩一个数据元素为止。直接选择排序149238365497576613727849ki=1jkjjjjkjjk1349直接选择排序149238365497576613727849i=kjjjjjj1349kk2voidSelectSort(SqList&L){for(inti=1;i<L.length;i++) k=SelectMinKey(L,i);if(i!=k)L.r[i]←→L.r[k];}voidSelectMinKey(SqList&L,constinti){intk=i; for(j=i+1;j<=L.length;j++)if(L.r[j].key<L.r[k].key) k=j;//当前具最小关键码的对象returnk; }直接选择排序的算法最坏情况：3(n-1)次直接选择排序算法的性能分析移动次数：最好情况（正序）：0次比较次数：)()1(21211nOnninni=-=-å-=）（简单选择排序的时间复杂度为O(n2)。树形选择排序排序思想：首先取得n个对象的关键码，进行两两比较，得到n/2个比较的优胜者(关键码小者)，作为第一步比较的结果保留下来。然后对这n/2个对象再进行关键码的两两比较，…，如此重复，直到选出一个关键码最小的对象为止。133813973865493876131327652749139749387613652749381338651327∞27382738657627279749387613652749382738657627∞13∞38384938657649算法分析除第一次选择具有最小关键码的对象需要进行n-1次关键码比较外，重构胜者树选择具有次小、再次小关键码对象所需的关键码比较次数均为O(log2n)。总关键码比较次数为O(nlog2n)。对象的移动次数不超过关键码的比较次数，故锦标赛排序总的时间复杂度为O(nlog2n)这种排序方法虽然减少了许多排序时间，但是使用了较多的附加存储。堆排序把待排序的数据元素集合构成一个完全二叉树结构，则每次选择出一个最大（或最小）的数据元素设数组a中存放了n个数据元素，数组下标从0开始，如果当数组下标2i+1<n时有：a[i]≥a[2i+1]；如果当数组下标2i+2<n时有：a[i]≥a[2i+2]，则这样的数据结构称为最大堆。性质5（2）如果2×i+1<n，则序号为i结点的左孩子结点的序号为2×i+1；如果2×i+1≥n，则序号为i结点无左孩子结点。堆排序(续)设数组a中存放了n个数据元素，数组下标从0开始，如果当数组下标2i+1<n时有：a[i]≤a[2i+1]；如果当数组下标2i+2<n时有：a[i]≤a[2i+2]，则这样的数据结构称为最小堆。9683273811091236248547913053堆排序基本思想：以初始关键字序列，建立堆；输出堆顶最小元素；调整余下的元素，使其成为一个新堆；重复2,3步，直到n个元素输出，得到一个有序序列。关键问题：如何由一个无序序列建成一个堆?如何调整余下的元素成为一个新堆?堆调整过程1338277697654949rc=13筛选过程voidHeapAdjust(SqListR[],ints,intm){

//已知R[s..m]中记录的关键字除R[s].key之外均满足堆的定义，本函数调整R[s]的关键字，使R[s..m]成为一个大顶堆rc=R[s];for(j=2*s;j<=m;j*=2){

//沿key较大的孩子结点向下筛选if(j<m&&R[j].key<R[j+1].key)++j;//j为key较大 //的记录的下标if(rc.key>=R[j].key)break;//rc应插入在位置s上R[s]=R[j];s=j;}R[s]=rc;//插入}

//HeapAdjust建堆过程无序序列建堆过程

方法：从完全二叉树的最后一个非叶结点

n/2开始，反复调用筛选过程，直到第一个结点，则得到一个堆。建堆算法voidHeapSort(SqListR[],intn){//对记录序列R[1..n]进行堆排序。

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

HeapAdjust(R,i,n);

for(i=n;i>1;--i){R[1]←→R[i];//将堆顶记录和当前未经排序子序列//R[1..i]中最后一个记录相互交换

HeapAdjust(R,1,i-1);

}//将R[1..i-1]重新调整为大顶堆}//HeapSort性能分析对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1);对n个关键字，建成深度为h(=log2n+1)的堆，所需进行的关键字比较的次数至多为4n;调整“堆顶”n-1次，总共进行的关键字比较的次数不超过2(log2(n-1)+log2(n-2)+…+log22)<2n(log2n)因此，堆排序的时间复杂度为O(nlogn)，不稳定。10.2

插入排序10.3

交换排序10.4

选择排序10.1

概述10.5

归并排序10.6

基数排序10.7

各种内部排序方法的比较归并排序基本思想：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，……，直至得到一个长度为n的有序序列为止。归并排序过程<初态>(49)(38)(65)(97)(76)(13)(27)(3849)<第2趟>(38496597)(132776)<第3趟>(13273849657697)<第1趟>(6597)(1376)(27)归并排序算法voidMerge(RedTypeSR[],RedType&TR[],inti,intm,intn){//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]intj,k,l;for(j=m+1,k=i;i<=m&&j<=n;++k)//将SR中记录由小到大地并入TRifLQ(SR[i].key,SR[j].key)TR[k]=SR[i++];elseTR[k]=SR[j++];if(i<=m)TR[k…n]=SR[i…m];//将剩余的SR[i..m]复制到TRif(j<=n)TR[k…n]=SR[j…n];//将剩余的SR[j..n]复制到TR}归并排序算法(续)voidMSort(RedTypeSR[],RedType&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]}}voidMergeSort(SqList&L){//对顺序表L作归并排序。算法10.14MSort(L.r,L.r,1,L.length);}10.2

插入排序10.3

交换排序10.4

选择排序10.1

概述10.5

归并排序10.6

基数排序10.7

各种内部排序方法的比较基数排序排序思想：基数排序是按组成关键字的各位的值进行分配和收集，与前面介绍的排序方法不同，它无需进行关键字之间的比较。设关键字有d位，每位的取值范围为r(称为基数)，则需要进行d趟分配与收集，需要设立r个队列。例如，关键字是4位字符串，需要26个队列，4趟分配与收集；关键字3位十进制数，需要10个队列，3趟分配与收集基数排序过程278—109—063—930—589—184—505—269—008—083f[0]f[1]f[2]f[3]

f[4]f[5]f[6]f[7]f[8]f[9]e[0]e[1]e[2]e[3]

e[4]e[5]e[6]e[7]e[8]e[9]278pp109p063p930p589p184p505p269p008p083930—063—083—184—505—278—008—109—589—269505—008—109—930—063—269—278—083—184—589f[0]f[1]f