数据结构之排序算法讲义.

在此幻灯片插入公司的徽标•从“插入”菜单•选择图片•找到徽标文件•单击“确定”重新设置徽标大小•单击徽标内任意位置。徽标外部出现的方框是“调整控点”•使用这些重新设置对象大小•如果在使用尺寸调整控点前按下shift键，则对象改变大小但维持原比例。1065865姓名学号成绩班级李红976105995机97.62020/4/133第二章数据结构与算法(续)2020/4/1342.8排序2.8.1概述1、排序的功能：将一个数据元素（或记录）的任意序列，重新排成一个按关键字有序的序列。2、排序过程的组成步骤：•首先比较两个关键字的大小；•然后将记录从一个位置移动到另一个位置。2020/4/135假设待排序的记录存放在地址连续的一组存储单元中，那么这种存储方式下的数据类型可描述为：MAX01234………keyinfo#defineMAX20typedefstruct{intkey;floatotherinfo;}RedType;2020/4/136排序方法插入排序选择排序交换排序归并排序直接插入排序折半插入排序简单选择排序堆排序起泡排序快速排序2020/4/1372.8.2插入排序直接插入、折半插入1、直接插入排序:基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上。举例：图8-2-12020/4/1382.8.2插入排序直接插入、折半插入该算法适合于n较小的情况，时间复杂度为O(n2).1、直接插入排序:基本思想：从数组的第2号元素开始，顺序从数组中取出元素，并将该元素插入到其左端已排好序的数组的适当位置上待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]直接插入排序示例对于有n个数据元素的待排序列，插入操作要进行n-1次2020/4/139voidinsertSort(RedTypeL[],intn){inti,j;for(i=2;i=n;i++)if(L[i].keyL[i-1].key){L[0]=L[i];/*作为监视哨*/for(j=i-1;L[0].keyL[j].key;j)L[j+1]=L[j];/*记录后移*/L[j+1]=L[0];/*插入*/}}插入算法如下：方法:Ki与Ki-1,Ki-2,…K1依次比较,直到找到应插入的位置。2020/4/13102、折半插入排序折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。折半插入排序的条件：在有序序列中插入一个关键字。举例，图8-2-22020/4/13112、折半插入排序折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。例：有6个记录，前5个已排序的基础上，对第6个记录排序。[1527365369]42lowmidhigh[1527365369]42lowhighmid[1527365369]42highlow[152736425369](highlow，查找结束，插入位置为low或high+1)(4236)(4253)2020/4/1312voidBinsertSort(RedTypeL[],intn){inti,low,high,mid;for(i=2;i=n;++i){L[0]=L[i];/*r[0]作为监视哨*/low=1;high=i-1;While(low=high){mid=(low+high)/2;if(L[0].keyL[mid].key)high=mid-1;//插入点在低半区elselow=mid+1;}for(j=i-1;j=high+1;j)L[j+1]=L[j];/*记录后移*/L[high+1]=L[0];/*插入*/}/*for*/}/*折半插入排序*/折半插入排序减少了关键字的比较次数，但记录的移动次数不变，其时间复杂度与直接插入排序相同。/*折半后的位置*/2020/4/13131、简单选择排序思想：首先从1~n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。时间复杂度为O(n2)，适用于待排序元素较少的情况。2.8.3选择排序简单选择排序、堆排序举例：图8-2-32020/4/13142.8.3选择排序简单选择排序、堆排序。1、简单选择排序思想：首先从1~n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。时间复杂度为O(n2)，适用于待排序元素较少的情况。初态83916839168391683916ijkijkijkijk13986互换ijk13986ikj13986ikj第一趟第二趟13986ikj第三趟2020/4/1315简单选择排序的算法如下：voidSelectSort(RedTypeL[],intn){inti,j,k,t;for(i=1,i=n;++i）/*选择第i小的元素，并交换到位*/{k=i；for(j=i+1;j=n;++j)if(L[j].keyL[k].key)k=j;/*L[k]中存放的是第I小的元素*/if(k!=i){t=L[i];/*交换*/L[i]=L[k];L[k]=t；}}/*FOR*/}/*SelectSort*/2020/4/13162堆排序也是一种选择排序。是具有特定条件的顺序存储的完全二叉树，其特定条件是：任何一个非叶子结点的关键字大于等于（或小于等于）子女的关键字的值。(1)堆的示例897624331510112536497856(a):堆顶元素取最大值(b):堆顶元素取最小值(2)实现堆排序需解决两个问题：（1）如何由一个无序序列建成一个堆？（2）输出堆顶元素后，如何将剩余元素调整成一个新的堆？举例：图8-2-42020/4/1317(3)输出堆顶元素并调整建新堆的过程(筛选)6525365649784111(b)65365649784111(c)251125365649784165(a)25493656657841(d)11把自堆顶至叶子的调整过程称为“筛选‘。从一个无序序列建堆的过程就是一个反复”筛选“的过程。2020/4/1318（4）由无序序列建初始堆的过程2556497811654136(a)无序序列n=8,int(n/2)=4开始2556493611654178(b):78被筛选后的状态2556413611654978(c):49被筛选后的状态2511413656654978(d):56被筛选后的状态(e):被筛选之后建成堆11254136566549782020/4/1319E、筛选算法（调整建堆）typedefSqlistHeapType;//堆采用顺序表存储表示voidHeapAdjust(HeapType&H,ints,intm){//已知H.r[s..m]中记录的关键字除H.r[s].key外均满足堆定义，//本函数调整H.r[s].key，使H.r[s..m]成为一个堆，其中堆顶元素为最大值rc=H.r[s];for(j=2*s;j=m;j*=2){//沿关键字值较大的孩子结点向下筛选if(jm&&H.r[j].keyH.r[j+1].key)++j;//j为key较大的记录下标if(rc.key=H.r[j].key)break;H.r[s]=H.r[j];s=j;//}//forH.r[s]=rc;}3376101524js107624331512345rc.key=10m=5s=12020/4/1320typedefSqlistHeapType;voidHeapAdjust(HeapType&H,ints,intm){rc=H.r[s];for(j=2*s;j=m;j*=2){if(jm&&H.r[j].keyH.r[j+1].key)++j;if(rc.key=H.r[j].key)break;H.r[s]=H.r[j];s=j;//}//forH.r[s]=rc;}3310761524js7610243315j=2*j=410第一次3310761524s7633241015j=2*j=8m第二次2020/4/1321voidHeapSort(HeapType&H){//堆顺序表H进行堆排序for(i=H.length/2;i0;i)HeapAdjust(H,i,H.length);//把H.r[1..H.length]成为一个堆，For(i=H.length;i1;i){把堆顶元素与最后一个记录相交换//rc=H.r[1];H.r[1]=H.r[i];H.r[i]=rc;HeapAdjust(H,1,i-1);//把H.r[1..i-1]重新调整为一个堆}}F、堆排序算法2020/4/1322A:2556497811654136i=4(1)2556497811654136i=3(2)2556657811494136(3)(4)2556657811494136i=2(5)2578655611494136i=1F、堆排序算法2020/4/1323(7)2556653611494178B:(6)7856653611494125重新调整为一个堆(8)1125364149566578最终结果2020/4/13242.8.4交换排序交换排序的特点在于交换。有冒泡和快速排序两种。1、冒泡排序（起泡排序）思想：小的浮起，大的沉底。从左端开始比较。第一趟：第1个与第2个比较，大则交换；第2个与第3个比较，大则交换，……关键字最大的记录交换到最后一个位置上；第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换到第n-1个位置上；依次类推，则完成排序。正序：时间复杂度为O(n)逆序：时间复杂度为O(n2)适合于数据较少的情况。排序n个记录的文件最多需要n-1趟冒泡排序。举例：图8-2-52020/4/1325第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始关键字思想：小的浮起，大的沉底。49364165117836653641563641654136415611783636414911564925252511494956111111252525252020/4/1326冒泡排序的C程序段：Voidbubsort(RedTypeL[],intn){inti,x,j=1,k=1;while(jn)&&(k0);{k=0;for(i=1;i=n-j;i++)if(L[i+1].keyL[i].key){k++;x=L[i];L[i]=L[i+1];L[i+1]=x;}j++;}/*while*/}/*Bobsort*/2020/4/13272、快速排序(对冒泡排序的改进）思想：通过一趟排序将待排序列分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分排序，以达到整个序列有序。关键字通常取第一个记录的值为基准值。做法：附设两个指针low和high，初值分别指向第一个记录和最后一个记录，设关键字为key，首先从high所指位置起向前搜索，找到第一个小于基准值的记录与基准记录交换，然后从low所指位置起向后搜索，找到第一个大于基准值的记录与基准记录交换，重复这两步直至low=high为止。时间复杂度：O(log2n)举例图8-2-62020/4/1328快速排序过程示意图：有序序列618235267key初始序列235266718lowhigh一次交换185266723lowhigh二次交换182366752high三次交换[186]23[6752]//完成一趟排序后分别进行快速排序lowhigh2020/4/13292.8