第9章-排序总结_第1页
第9章-排序总结_第2页
第9章-排序总结_第3页
第9章-排序总结_第4页
第9章-排序总结_第5页
已阅读5页,还剩72页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第九章排序19.1基本概念9.2插入排序9.3交换排序9.4选择排序本章书目9.5归并排序9.6基数排序9.7各种内排序的比较小结与习题29.1基本概念排序1排序的分类2内排序33排序排序的定义给定一个记录集合(

r1,r2,…,rn),其相应的关键码分别为(k1,k2,…,kn),排序是将这些记录排成依次为(rs1,rs2,…,rsn)的一个序列,使得相应的关键码满足ks1≤ks2≤…≤ksn(非降序或升序)或ks1≥ks2≥…≥ksn(非升序或降序)。4排序算法的稳定性若对随意的数据元素序列,运用某个排序方法,对它按关键码进行排序若相同关键码元素间的位置关系,排序前与排序后保持一样,称此排序方法是稳定的;不能保持一样的排序方法则称为不稳定的。5排序的分类依据参与排序的数据元素(记录)是否全部放置在内存中可把排序分为内排序和外排序。内排序:指待排序列完全存放在内存中所进行的排序过程,适合不太大的元素序列。外排序:指排序过程中还需访问外存储器,足够大的元素序列,因不能完全放入内存,只能运用外排序。6排序的分类依据排序所依据的关键码的个数可以把排序分为单键排序和多键排序。单键排序:依据一个关键码进行的排序。多键排序:依据多个关键码进行的排序。7排序的分类依据排序的方法是否建立在关键码比较的基础上可以把排序分为:基于比较:主要是通过关键码之间的比较和记录的移动这两种操作来实现的排序。不基于比较:依据待排序数据的特点所实行的其它方法,通常是没有大量的关键码之间的比较和记录的移动操作的排序。8内排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区9内排序的主要方法选择类交换类归并类插入类各种排序直接插入折半插入表插入希尔将无序子序列中的一个或几个记录“插入”到有序序列中,从而增加记录的有序子序列的长度,最终完全排序工作。10内排序的主要方法选择类交换类归并类插入类各种排序冒泡排序快速排序通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录,并将它加入到有序子序列中,以此方法增加记录的有序子序列的长度。11内排序的主要方法选择类交换类归并类插入类各种排序从记录的无序子序列中“选择”关键字最小或最大的记录,并将它加入到有序子序列中,以此方法增加记录的有序子序列的长度。简单选择树形选择堆排序12内排序的主要方法选择类交换类归并类插入类各种排序二路归并排序通过“归并”两个或两个以上的记录有序子序列,逐步增加记录有序序列的长度。139.2插入排序直接插入排序1折半插入排序2表插入排序3希尔排序414算法思想仅有一个记录的表总是有序的,因此,对于n个记录的表,可从其次个记录起先直到第n个记录,逐个向有序表中进行插入操作,从而得到n个记录按关键码有序的表。干脆插入排序15干脆插入排序操作步骤:Step1:选取L.key[1]作为初始的有序序列,i=2;Step2:将L.key[i]插入到前面的有序序列中,使其有序序列长度增加1;Step3:i=i+1,若i的值小于表长,则重复Step2,否则排序结束。16干脆插入排序算法分析:空间效率:仅用了一个协助单元,O(1)。时间效率:最好状况下:初始序列是依次的最坏状况下:初始序列是逆序的平均状况下:初始序列是无序的稳定性:是一种稳定的排序方法。17干脆插入排序总比较次数=n-1

最好最坏平均总移动次数=2(n-1)18折半插入排序算法思想设在依次表中有一个对象序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已经排好序的对象。在插入V[i]时,利用折半查找法找寻V[i]的插入位置。19折半插入排序操作步骤:Step1:依次表中前j-1个记录有序,将第j个记录插入。令low=1;high=j-1;r[0]=r[j];Step2:若low>high,得到插入位置,转Step5;Step3:若low≤high,则取有序子表的中点m=(low+high)/2;Step4:若r[0].key<r[m].key,则插入位置在低半区,令high=m-1;否则插入位置在高半区,令low=m+1;转Step2;Step5:high+1即为待插入位置,从j-1到high+1的记录,逐个后移,r[high+1]=r[0];放置待插入记录。20折半插入排序算法分析:时间困难度:O(n2)。空间困难度:O(1)。稳定性:是一种稳定的排序方法。21表插入排序算法思想:为了削减在排序过程中进行的“移动”记录的操作,必需变更排序过程中接受的存储结构。利用静态链表进行排序,并在排序完成之后,一次性地调整各个记录相互之间的位置,即将每个记录都调整到它们所应当在的位置上。22表插入排序静态链表说明:#defineSIZE200typedefstruct{ElemTypeelem;/*元素类型*/int

next;/*指针项*/}NodeType;/*表结点类型*/typedefstruct{NodeTyper[SIZE];/*静态链表*/int

length;/*表长度*/}L_TBL;/*静态链表类型*/23表插入排序操作步骤Step1:从第一个记录起先调整,令j=l->r[0].next;将i指向第一个记录位置;Step2:若i=l->length时,调整结束;否则:2.1若i=j,j=l->r[j].next;数据元素应在这重量中,不用调整处理下一个结点:i++;转Step2;2.2若j>i,则l->r[i].elem<-->l->r[j].elem;保存下一个结点地址:p=l->r[j].next;同时保持后续链表不被中断:l->r[j].next=l->[i].next;l->[i].next=j;指向下一个处理的结点:j=p;i++;转Step2;2.3若j<i,j重量中原记录已移走,沿j的指针域找寻原记录的位置:while(j<i)j=l->r[j].next;转到2.1。24表插入排序举例说明Play25表插入排序算法分析:时间困难度:设有序表长度为i,则须要比较至多i+1次,修改指针两次。因此,总比较次数与干脆插入排序相同,修改指针总次数为2n次。所以,时间困难度仍为O(n2)。空间困难度:表插入排序的空间困难度为O(1)。稳定性:表插入排序是一种稳定的排序方法。26希尔排序算法思想先将整个待排记录分割成若干个子序列,在子序列中分别进行干脆插入排序,待整个序列基本有序的时候,再对全体序列进行一次干脆插入排序。27希尔排序操作步骤:Step1:选择一个步长序列t1,t2,…,tk,其中ti>tj,tk=1;Step2:按步长序列个数k,对序列进行k趟排序;Step3:每趟排序,依据对应的步长ti,将待排序列分割成若干长度为m的子序列,分别对各子表进行直接插入排序。仅步长因子为1时,整个序列作为一个表来处理,表长度即为整个序列的长度。28希尔排序举例说明:Play29希尔排序算法分析:时间困难度:由于希尔排序是依靠于增量的选取,它的时间困难度是在O(nlog2n)~O(n2)之间。空间困难度:在希尔排序的过程中只须要一个协助空间用于暂存当前待插入的记录,因此,希尔排序的空间困难度为O(1)。稳定性:希尔排序方法是一种不稳定的排序方法。309.3交换排序冒泡排序1快速排序231冒泡排序

假设在排序过程中,记录序列R[1..n]的状态为:第i趟冒泡排序无序序列R[1..n-i+1]有序序列R[n-i+2..n]n-i+1无序序列R[1..n-i]有序序列R[n-i+1..n]比较相邻记录,将关键字最大的记录交换到n-i+1的位置上32冒泡排序算法思想对n个记录的表,第一趟冒泡得到一个关键码最大的记录r[n],其次趟冒泡对n-1个记录的表,再得到一个关键码最大的记录r[n-1],如此重复,直到n个记录按关键码有序的表。33冒泡排序一趟冒泡方法:Step1:i=1;//设置从第一个记录起先进行两两比较Step2:若i≥j,一趟冒泡结束。Step3:比较r[i].key与r[i+1].key,若r[i].key≤r[i+1].key,不交换,转Step5;Step4:当r[i].key>r[i+1].key时,r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];//将r[i]与r[i+1]交换Step5:i=i+1;对下两个记录进行两两比较,转Step2;34冒泡排序操作步骤:Step1:从n记录的表尾起先,j=n;Step2:若j<2,排序结束;Step3:i=1;一趟冒泡,从第一个记录起先进行两两比较;Step4:若i≥j,一趟冒泡结束,j=j-1;冒泡表的记录数-1,转Step2;(转下页)35冒泡排序(续上页)Step5:

比较r[i].key与r[i+1].key,若r[i].key≤r[i+1].key,不交换,转Step7;Step6:

当r[i].key>r[i+1].key时,将r[i]与r[i+1]交换;Step7:i=i+1;调整对下两个记录进行两两比较,转Step4;36冒泡排序语言描述:template<classtype>voidBubbleSort(SqList<type>&L){ for(inti=1;i<L.length;i++)//用i限制比较趟数共n-1趟 { typet;//协助变量,作交换用 for(intj=1;j<=L.length-i;j++) if(L.key[j]>L.key[j+1]) { t=L.key[j]; L.key[j]=L.key[j+1]; L.key[j+1]=t;//交换L.key[j]和L.key[j+1]的值 } }}37冒泡排序算法分析:空间困难度:冒泡排序的空间困难度为O(1)。时间困难度:总共要进行n-1趟冒泡,对j个记录的表进行一趟冒泡须要j-1次关键码比较。冒泡排序的时间困难度为O(n2)。稳定性:冒泡排序是一种稳定的排序方法。38快速排序算法思想:找一个记录,以它的关键字作为“枢轴”,凡其关键字小于枢轴的记录均移动至该记录之前,反之,凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后,记录的无序序列R[s..t]将分割成两部分:R[s..i-1]和R[i+1..t],且

R[j].key≤R[i].key

R[j].key(s≤j≤i-1)

枢轴

(i+1≤j≤t)。39快速排序示例stlowhigh设R[s]=52为枢轴high23low80high14low52R[0]52lowhighhighhighlow40快速排序操作步骤:Step1:假如待排子序列中元素的个数大于1,则以L.r[low]作为枢轴,进行一次划分;否则排序结束。Step2:对枢轴左半子序列重复Step1;Step3:对枢轴右半子序列重复Step1;41快速排序算法分析:空间困难度:快速排序是递归的,递归调用层次数与其二叉树的深度一样。因而,存储开销在志向状况下为O(log2n);在最坏状况下,为O(n)。时间困难度:最好状况下为O(nlog2n),最坏状况,快速排序蜕化为冒泡排序。稳定性:快速排序是一个不稳定的排序方法。429.4选择排序简单选择排序1树形选择排序2堆排序343简洁选择排序假设排序过程中,待排记录序列的状态为:有序序列R[1..i-1]无序序列R[i..n]第i趟简洁选择排序从中选出关键字最小的记录有序序列R[1..i]无序序列R[i+1..n]44简洁选择排序算法思想:第一趟,从n个记录中找出关键码最小的记录与第一个记录交换;其次趟,从其次个记录起先的n-1个记录中再选出关键码最小的记录与其次个记录交换;如此,第i趟,则从第i个记录起先的n-i+1个记录中选出关键码最小的记录与第i个记录交换,直到整个序列按关键码有序。45简洁选择排序操作步骤:Step1:

从L.key[i]~从L.key[length]记录中选择一个关键字值最小的记录,将其下标保存至min中;Step2:

若L.key[i]≤L.key[min];则交换这两个记录;否则转Step3;Step3:i=i+1,若i≤L.length,则转Step1;否则排序结束。46简洁选择排序算法分析:时间困难度:从算法中可看出,简洁选择排序移动记录的次数较少,但关键码的比较次数照旧是,算法的时间困难度仍是O(n2)。空间困难度:简洁选择排序算法只须要一个协助空间来作为交换记录用的暂存单元。因此,它的空间困难度O(1)。稳定性:简洁选择排序是一种稳定的排序方法。47树形选择排序操作步骤:Step1:从最底层叶子结点起先,按层一一进行兄弟间的竞赛,关键字值较大者上升为子树根结点,直到树的顶层为止;Step2:将树的根结点输出,把底层叶子中值相同的结点值改为0;假如输出的结点总数小于初始时树的叶子结点总数,则重复Step1;否则结束排序。48树形选择排序算法分析:时间困难度:除了最大关键字之外,每选择一个次大的关键字只须要进行log2n次比较,因此,它的时间困难度为O(nlogn)。空间困难度:须要附加n个协助空间用来保存排序的结果,还要n-1个协助空间作为排序过程中运用。因此,它的空间困难度O(n)。稳定性:树形选择排序是一种不稳定的排序方法。这是因为在比较的过程中是跳动式进行的。49堆排序堆的定义:第一种定义方式:设有n个元素的序列{k1,k2,…,kn},当且仅当满足下述关系之一时,称之为堆。其次种定义方式:堆是具有下列性质的完全二叉树:每个结点的值都小于或等于其左右孩子结点的值(称为小根堆或小顶堆);或者每个结点的值都大于或等于其左右孩子结点的值(称为大根堆或大顶堆)。iiiikkkk212{££+

iiiikkkk212{³³+

(i=1,2,…,[n/2])

50堆排序算法思想:设有n个元素,将其按关键码排序。首先将这n个元素按关键码建成堆,将堆顶元素输出,得到n个元素中关键码最小(或最大)的元素。然后,再对剩下的n-1个元素建成堆,输出堆顶元素,得到n个元素中关键码次小(或次大)的元素。如此反复,便得到一个按关键码有序的序列。称这个过程为堆排序。51堆排序堆排序需解决的两个问题:1.怎样建堆:如何将n个元素的序列按关键码建成堆;2.怎样调整:输出堆顶元素后,怎样调整剩余n-1个元素,使其按关键码成为一个新堆。52堆排序建堆方法:先把待排序序列构造成一棵完全二叉树;然后从下往上,自右而左进行筛选,最终得到堆.36

30

91

47

24

12

5385

a.8个结点的初始状态

例:53堆排序36

30

85

47

24

12

53

91

c.对第3个结点开始筛选b.从第4个结点起先筛选

36

30

91

47

24

12

5385

36

12

85

47

24

30

53

91

d.第2个结点为根的子树已是堆54堆排序36

12

85

47

24

30

53

91

36

53

85

47

24

30

12

91

e.对整棵树进行筛选55堆排序操作步骤:Step1:i=1,对依次表L[1…L.lengh-i+1]中的建大顶堆;Step2:将堆顶元素和L[L.lengh-i+1]交换;Step3:i=i+1,若i<L.lengh,则将L[1…L.lengh-i+1]调整;使之成为新的大顶堆;转Step2;否则排序结束。56堆排序算法分析:时间困难度:在建好堆后,排序过程中的筛选次数不超过nlog2n,而建堆时的比较次数不超过4n次,因此堆排序最坏状况下,时间困难度也为O(nlog2n)。空间困难度:堆排序中,只须要一个用来交换的暂存单元,因此它的空间困难度为O(1)。算法的稳定性:由于记录的比较和交换是跳动式进行的,因此,堆排序是一种不稳定的排序方法。579.5二路归并排序算法思想归并排序的基本思想是基于将两个或两个以上的有序子序列“归并”为一个有序序列。归并为一个记录的有序序列有序序列R[l..n]有序子序列R[l..m]有序子序列R[m+1..n]58二路归并排序操作步骤:Step1:设置两个子表的起始下标及协助数组的起始下标:i=u;j=v;k=u;Step2:若i>v或j>t,则比较选取结束转Step4;Step3:选取r[i]和r[j]中关键码较小的存入协助数组rf。假如r[i].key<r[j].key,则rf[k]=r[i];i++;k++;否则,rf[k]=r[j];j++;k++。转Step2;Step4:将尚未处理完的子表中元素存入rf:Step5:合并结束。59二路归并排序递归算法操作步骤:Step1:

将待排序的记录序列分为两个相等的子序列,分别将这两个子序列进行排序;Step2:

调用一次归并算法Merge,将这两个有序子序列合并成一个含有全部记录的有序序列。60二路归并排序算法分析:时间困难度:归并过程对应由叶向根生成一棵二叉树的过程,所以归并趟数约等于二叉树的高度-1,即log2n,每趟归并需移动记录n次,故时间困难度为O(nlog2n)。空间困难度:须要一个与表等长的协助元素数组空间,所以空间困难度为O(n)。稳定性:由一次归并算法中的if语句可知,二路归并算法是一种稳定的算法。619.6基数排序基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。多关键码排序1链式基数排序262多关键码排序定义:n个记录的序列{R1,R2,…,Rn}对关键字(Ki1,Ki2,…,Kid)有序是指:对于序列中随意两个记录Ri和Rj(1≤i<j≤n)都满足下列(词典)有序关系:(Ki1,Ki2,…,Kid)<(Kj1,Kj2,…,Kjd),其中:K1被称为“最主”位关键字,Kd被称为“最次”位关键字。63多关键码排序两种方法最高位优先MSD法先对K1进行排序,并按K1的不同值将记录序列分成若干子序列之后,分别对K2进行排序,...…,依次类推,直至最终对最次位关键字排序完成为止。最低位优先LSD法先对Kd进行排序,然后对Kd-1进行排序,依次类推,直至对最主位关键字K1排序完成为止。64多关键码排序例如:学生记录含三个关键字:系别、班号和班内的序列号,其中以系别为最主位关键字。LSD的排序过程如下:

无序序列对K3排序对K2排序对K1排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18

1,2,152,1,202,3,183,1,203,2,3065链式基数排序算法思想:从最低位关键码起,按关键码的不同值将序列中的记录“安排”到RADIX个队列中,然后再“收集”之。如此重复d次即可。链式基数排序是用RADIX个链队列作为安排队列,关键码相同的记录存入同一个链队列中,收集则是将各链队列按关键码大小依次链接起来。66链式基数排序操作步骤:Step1:初始化,建立待排序列的静态链表SL;Step2:从最低位关键码起先,按关键码值将SL中记录安排到各个单链表中;Step3:依据关键码的值,从小到大将各个单链表进行收集,重复Step2,直到排序完成。67链式基数排序例:初始状态:278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集:68链式基数排序505008109930063269278083184589二趟收集:083184589063505269930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269一趟收集:69链式基数排序008063083109184269278505589930三趟收集:109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]三趟分配063083269278505589505008109930063269278083184589二趟收集:70链式基数排序算法分析:时间效率:设待排序列为n个记录,d个关键码,关键码的取值范围为radix,则进行链式基数排序的时间困难度为O(d(n+radix))。空间效率:须要2*radix个指向队列的协助空间,以及用于静态链表的n个指针。稳定性:在基数排序的过程中,并没有交换记录的前后位置,因此该排序方法是一种稳定的排序方法。719.7各种内部排序方法的比较排序方法

平均情况

最好情况

最坏情况

辅助空间

直接

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论