自考数据结构02142-第七章

第七章排序•7.1概述•7.2插入排序•7.3交换排序•7.4选择排序•7.5归并排序▲数据排序——将一个文件的记录按关键字不减（或不增）次序排列，使文件成为有序文件，此过程称为排序。▲稳定排序——若排序后，相同关键字的记录保持它们原来的相对次序，则此排序方法称为～。▲不稳定排序——▲排序类型——内部排序：全部数据存于内存；外部排序:需要对外村进行访问的排序过程7.1概述内部排序按方法分插入排序交换排序选择排序归并排序▲排序文件的物理表示：数组表示▲排序指标（排序算法分析）：存储空间-空间复杂度比较次数-时间复杂度#definen100/*序列中待排序记录的总数*/typedefstruct{intkey;/*关键字项*/anytypeotheritem;/*其他数据项*/}records;typedefrecordslist[n+1];listr;r[0]r[1]r[2]….r[n]r[i].key——第i个记录的关键字1.过程：对R1，…，Ri-1已排好序，有K1≤K2≤….≤Ki-1，现将Ki依次与Ki-1，Ki-2，…进行比较，并移动元素，直到发现Ri应插在Rj与Rj+1之间(即有Kj≤Ki＜Kj+1)，则将Ri插到j+1号位置上，形成i个有序序列。（i从2～n）2.算法：见P1853.例：见P1864.算法分析：●空间复杂度O(1):需要一个辅助空间●时间复杂度O(n2)●稳定性：稳定排序；▲直接插入排序7.2插入排序（通过比较插入实现排序）▲直接插入排序算法：voidStraightInsertsort(listr,intn);{/*用直接插入排序法对r[1]…r[n]进行排序*/inti,j;for(i=2;i=n;i++){r[0]=r[i];j=i-1;while(r[0].keyr[j].key){r[j+1]=r[j];/*记录后移*/j=j-1;}r[j+1]=r[0];/*插入*/}}7.3交换排序（通过比较交换实现排序）一、冒泡排序1.基本思想：通过多次重复比较、交换相邻记录而实现排序；每一趟的效果都是将当前键值最大的记录换到最后。（见P187）2.例：试对下列待排序序列用冒泡排序法进行排序,给出每趟结果:{49，38，65，97，76，134，27，49}第一趟：38496576972749[134]第二趟：384965762749[97134]第三趟：3849652749[7697134]第四趟：38492749[657697134]第五趟：382749[49657697134]第六趟：2738[4949657697134]第七趟：27[384949657697134]3.冒泡排序算法：见下页。4.算法分析：●时间复杂度：外循环最多n-1次（最少1次），第i次外循环时，内循环n-i次比较，∴最大比较次数为∑ni=1n-i=n(n-1)/2≈n2/2=O(n2)●稳定性：稳定排序。▲冒泡排序算法：VoidbubbleSort(listr,intn){inti,j,temp,endsort;for(i=1;i=n-1;i++){endsort=0;for(j=1;j=n-i-1;j++){if(r[j].keyr[j+1].key){temp=r[j];r[j]=r[j+1];r[j+1]=temp;endsort=1;}}if(endsort==0)break;}}首先取第一个记录，将之与表中其余记录比较并交换，从而将它放到记录的正确的最终位置，使记录表分成两部分{其一（左边的）诸记录的关键字均小于它；其二（右边的）诸记录的关键字均大于它}；然后对这两部分重新执行上述过程，依此类推，直至排序完毕。二、快速排序★1.基本思想：通过分部排序完成整个表的排序；2.过程：记录序列{r[low],r[low+1],…,r[high]}设：左指针i，右指针j;初值：i=low；j=high;处理元素=x;初始时：r[1]=x(2)i指针逐步右移，即：将r[i]与x比较，i不断增1，直到发现某个r[i].key＞x.key时，则：r[i]=j位置上；j-1=j;转(1);此过程直到(1)或(2)中i=j时停止，此时将处理元素x送到i或j位置上，它将原序列分成左、右两个子序列，对它们分别进行上述过程，直至分裂后的子序列都只有一个元素为止。(1)j指针逐步左移，即：将r[j]与x比较，j不断减1，直到发现某个r[j].keyx.key时，则：r[j]=i位置上（开始时i=1）；i+1=i;转(2)4.算法：P189。5.算法分析：●平均时间性能：O(nlog2n);注：若初始记录表有序或基本有序，则快速排序将蜕化为冒泡排序,其时间复杂度为O(n2)；即：快速排序在表基本有序时，最不利于其发挥效率。●稳定性：不稳定排序。第一趟：{36，55,48，37，10}60{84，90}第二趟：{10}36{48，37,55}6084{90}第三趟：1036{37}48{55}608490结果：10363748556084903.例：试对下列待排序序列用快速排序法进行排序,给出每趟结果:{60，55，48，37，10，90，84，36}7.4选择排序（以重复选择的思想为基础进行排序）一、直接选择排序1.过程：设记录R1，R2…，Rn，对i=1，2，…，n-1，重复下列工作：(1)在Ri，…，Rn中选最小(或最大)关键字记录Rj；(2)将Rj与第i个记录交换位置，即将选到的第i小的记录换到第i号位置上。2.例：试对下列待排序序列用选择排序法进行排序,给出每趟结果:{46，15，13，94，17}第一趟：13[15，46，94，17]第二趟：1315[46，94，17]第三趟：131517[94，46]第四趟：13151746943.算法：直接选择排序4.算法分析:●时间：C总=∑ni=1(n-i)=(n2–1)/2≈O(n2)●稳定性：不稳定排序；（P191）二、堆排序1.堆：集合{K1,K2,….,Kn}，对所有i=1,2,…,n/2有：Ki≤K2i且Ki≤K2i+1，则此集合称为堆（最小堆）;（或Ki≥K2i且Ki≥K2i+1最大堆）例：｛13,40,27,88,55,34,65,92｝(最小堆)｛92,65,88,40,55,34,13,27｝(最大堆)下标：12345678堆{K1,K2,….,Kn}概念上可看成顺序存储的完全二叉树（Ri对应结点i）且树中双亲关键字值均不超过孩子的关键字；注：堆根最小；输出根结点剩下的再构造堆直到最后一结点堆排序思想2.建堆（筛选法）：1）方法：设记录{R1,R2,….,Rn}(1)顺序输入成完全二叉树（以数组存储）(2)从最后一个双亲开始，如果有较小的孩子，则将其沿左或右孩中小的那个方向筛下，一直到不能再筛；(3)逐次处理完每个双亲。2）例子：（见下页）；3）算法：下筛一个结点算法(见P195)例：判别下列序列是否为堆，如果不是则将之调整为堆。｛12,70,53,65,24,56,48,92,86,33｝12705348566524928633不是堆12704853566524928633∵7065且70242465∴70沿右筛下∵5348∴53沿右筛下12244853566570928633∵7033∴70沿左筛下122448535665339286703.堆排序：1）过程：①从i=int(n/2）1调用sift(r,i,n)建初始堆对i=n,n-1,n-2,….,2重复②、③②输出r[1],即：r[1]r[i]③调用sift(r,1,i-1),重新建堆2）算法:3）例：（见下页）4.算法分析：●空间：n+1；（仅需1个附加空间）●时间：O（nlogn)O(n2)●稳定性：不稳定排序；例：对下列序列进行堆排序。｛12,70,53,65,24,56,48,92,86,33｝12244853566533928670初始堆输出1270244853566533928612下筛70重建堆24334853566570928612输出2486334853566570922412下筛86重建堆33654853568670922412输出3392654853568670332412下筛92重建堆48655392568670332412输出4892655348568670332412下筛92重建堆53655648928670332412输出5392655648538670332412下筛92重建堆56659248538670332412输出5670659248538656332412下筛70重建堆65709248538656332412输出6586709248536556332412下筛86重建堆70869248536556332412输出7092867048536556332412下筛92重建堆86927048536556332412输出70928670485365563324127.5归并排序1.思想：比较各个子序列的第一个记录的键值，最小的一个就是排序后序列的第一个记录。取出这个记录，继续比较各子序列现有的第一个记录的键值，便可找出排序后的第二个记录。如此继续下去，最终可以得到排序结果。2.两个有序表归并算法（见P199）一、有序序列的合并(两个有序表归并成一个有序表)②两两归并成n/2个，长度为2的有序表（n为奇数，则还有1个长为1的表）二、归并排序1.思想：（2-路归并排序）①n个记录的表看成n个，长度为1的有序表③再两两归并为n/2/2个，长度为4的有序表...再两两归并直至只剩1个，长度为n的有序表；共log2n趟2.例：3.2-路归并算法：(见P200算法)4.算法分析：●空间：n+n；（需n个附加空间）●时间：O（nlogn)●稳定性：稳定排序；第一趟：[137475][219481][382674][326350][506815]第二趟：[137219475481][326350382674][506815]第三趟：[137219326350382475481674][506815]第四趟：[137219326350382475481506674815]试对下列待排序序列用归并排序法进行排序,给出每趟结果:{475，137，481，219，382，674，350，326，815，506}7.6各种排序方法的比较排序方法平均时间最坏情况辅助存储稳定性简单排序(插入、冒泡、直接选择)O(n2)O(n2)O(1)稳定排序(除直接选择是不稳定外)快速排序O(nlog2n)O(n2)O(log2n)不稳定排序堆排序O(nlog2n)O(nlog2n)O(1)不稳定排序归并排序O(nlog2n)O(nlog2n)O(n)稳定排序掌握各种排序算法思想、排序过程、稳定性及算法的时间复杂性。重点：各种排序方法的过程。第七章排序小结1．排序是根据什么的大小重新安排各元素的顺序？（）A．数组B．关键字C．元素D．结点2．快速排序在最坏的情况下的时间复杂度是()A．O(log2n)B.O(nlog2n)C.O(n)D.O(n2)3．以下四种排序方法中，要求附加空间最大的是（）A.插入排序B.冒泡排序C.归并排序D.快速排序4．快速排序的方法是（）A．稳定排序B.不稳定排序C.外部排序D.选择排序5．冒泡排序的方法是（）A．稳定排序B.不稳定排序C.外部排序D.选择排序练习6．以下时间复杂度不是O(n2)的排序方法是（）A.直接插入排序B.冒泡排序C.快速排序D.直接选择排序