《数据结构》排序》PPT课件复习过程.ppt

单击此处编辑母版标题样式,单击此处编辑母版副标题样式,第9章 排序,9.1,插入排序,9.2,交换排序,9.3,选择排序,9.4,归并排序,习题,排序是针对记录的集合R1,R2,Rn，其相应的关键字序列为K1,K2,Kn，重组记录之间的关系，使,记录的,排列次序满足相应的,关键字,的,递增,或,递减,关系。记录的集合也称为待排序,序列,。若待排序,序列,完全存放,在内存,中，则该排序称为,内部排序,；若由于,数据,集合太大，在排序过程中，需对,外存,进行访问，则该排序称为,外部排序,。,有如下一组待排序序列(每个记录只列出关键字一项)：,53,25,67(1),46,29,67(2),89,43,67(3),76,括号,里的,数字,代表等值记录的,位置,，若排序后为：,25,29,43,46,53,67(1),67(2),67(3),76,89,则称所用的,排序方法,是,稳定,的，反之，若三个等值记录的排列顺序不是上述顺序，就称所用排序的方法是不稳定的。,9.1 插入排序,9.1.1 直接插入排序,它的基本操作是在处理第i个记录时，前面1到i-1记录已排成有序，将第i个记录插入有序表中，得到一个新的有序表，表的长度加1。当表中只有一个记录时，该表已是有序表，所以，可以从第二个记录开始，逐个插入记录，直至处理完待排序序列的所有记录。,直接插入排序的时间复杂度为O(n2)，并且是一种稳定排序。当n较小时，排序的效率较高，是一种常用的排序方法,处理记录号,插入位置,下标,0,1,2,3,4,5,6,i=1,j=0,91,67,35,62,29,72,46,i=2,j=0,67,91,35,62,29,72,46,i=3,j=0,35,67,91,62,29,72,46,i=4,j=1,35,62,67,91,29,72,46,i=5,j=0,29,35,62,67,91,72,46,i=6,j=4,29,35,62,67,72,91,46,i=7,j=2,29,35,46,62,67,72,91,图9.1 直接插入排序示例,例如，有一组关键字序列为91,67,35,62,29,72,46，直接插入排序过程如图9.1所示。,用C语言描述的直接插入排序算法如下：,typedef struct,int key;,/*其他域*/,NODE;,算法9.1,直接插入排序算法。,void InsertSort(NODE array,int n),/*对存放在数组array中，长度为n的序列排序*/,int i,j;NODE x;,for(i=1;i=0&x.keyd2dt，并且当t1时，d1=1，该序列都可选作步长序列。一般采用步长序列为d1=n/2，di+1=di/2(n为待排序序列的长度)。,用C语言描述的希尔排序算法如下：,算法9.2,希尔排序算法。,void ShellSort(NODE array,int n),/*对存放在数组array中，长度为n的序列希尔排序*/,int i,j,step;NODE x;,for(step=n/2;step0;step=step/2),/*step不断变小，直至为1*/,for(i=step;i=0&x.keyarrayj.key),arrayj+step=arrayj;j=j-step;,arrayj+step=x;,希尔排序的分析是一个复杂的问题，但它的排序速度要比直接插入排序快，另外，它是一种不稳定排序,9.2 交换排序,交换排序,基本思想,：,比较,二个待排序记录的,关键字,，若为,逆序,，则,交换,位置，反之，保持原序。,9.2.1 冒泡(简单交换排序),冒泡排序的方法是：首先,比较,array,n-1,.key和array,n-2,.key，若为,逆序,则,交换,之，然后,比较,array,n-2,.key和array,n-3,.key，依此类推，直到,比较,array,1,.key和array,0,.key，称为一趟“冒泡”，其,结果,是将具有,最小关键字,的记录,排到,序列的,第1,个位置上。然后再arrayn-1到array1之间进行一趟“冒泡”，将具有次小关键字的记录排到序列的第2个位置上。依此类推，直到第n-1趟，在arrayn-1和arrayn-2之间进行“冒泡”后，待排序序列已排成有序。,下一趟区间,下标,0,1,2,3,4,5,6,初始关键字 6，0,91,67,35,62,29,72,46,第一趟冒泡后 6，1,29,91,67,35,62,46,72,第二趟冒泡后 6，2,29,35,91,67,46,62,72,第三趟冒泡后 6，3,29,35,46,91,67,62,72,第四趟冒泡后 6，4,29,35,46,62,91,67,72,第五趟冒泡后 6，5,29,35,46,62,67,91,72,第六趟冒泡后 序列有序,29,35,46,62,67,72,91,图9.3 冒泡排序示例,例如，有一组关键字序列为91,67,35,62,29,72,46，冒泡排序过程如图9.3所示。,用C语言描述的简单交换排序算法如下：,算法9.3,冒泡排序算法。,void BubbleSort(NODE array,int n),/*对存放在数组array中，长度为n的序列冒泡排序*/,int i,j,flag;NODE temp;,for(i=0;ii;j-),/*从后向前比较，小数向前交换，最小值到前位*/,if(arrayj.keyarrayj-1.key),temp=arrayj;arrayj=arrayj-1;arrayj-1=temp;,flag=1;,/*有逆序存在，flag为1*/,if(flag=0)break;,/*若一趟“冒泡”中没有逆序，则序列已有序*/,冒泡排序的时间复杂度为O(n2)，并且是一种稳定排序。,9.2.2 快速排序,冒泡排序的一种改进。基本思想是：通过,一趟排序,后，,大幅度减小排序序列的长度,。在,一趟排序后,将某个记录根据其,关键字,，,排到,序列的,中间位置,，且,左边,所有记录的关键字都,比它,的关键字,小,，而,右边,所有记录的关键字都,比它,的关键字,大,，这样一趟排序后，不仅有一个记录已排到正确的位置上，如下标为i，而且,待排序序列分裂,成长度较小的,两个,待排序,区间,(array,0,到array,i-1,和array,i+1,到array,n-1,)，将上述过程,称为“划分”,。一次划分得到两个小序列，再,递归,地对,这两个小序列进行划分,，直到序列的长度为1，这时待排序序列已排成有序。显然，一次划分的时间复杂度是O(n)，下面讨论,划分的算法,。,对array,start,到array,end,序列进行,划分,，首先要确定一个划分标准，通常,选取序列,的,第一个记录的关键字,，用变量mid暂存，另附设,两个指针,i和j，其初值,分别,为,start,和,end,，划分的具体做法如下(,i=start，j=end,)：,(1)j从所指的位置开始从后向前扫描，直到,arrayj.key=end)return;,/*仅有一个记录*/,i=start;j=end;mid=arrayi;,while(ij),while(imid.key)j-;,if(ij)arrayi=arrayj;i+;,while(ij,if(ij)arrayj=arrayi;j-;,arrayi=mid;,/*一趟划分结束*/,Quick_Sort(array,start,i-1);,/*对start到i-1的记录进行划分*/,Quick_Sort(array,i+1,end);,/*对i+1到end的记录进行划分*/,平均时间复杂度为O(nlog2n)，最坏这时快速排序等同于冒泡排序，时间复杂度为O(n2)。快速排序是不稳定的排序。,9.3 选择排序,选择排序的,基本思想,是：每一趟在n-i+1(i=1,2,n-1)个记录中选,关键字最小,的记录作为有序序列中第i个记录。,9.3.1 直接选择排序,直接选择排序又称为简单选择排序，其算法是：对n个记录排序，依次,选出n-1个极值,，置于相应目标位置。对array0到arrayn-1排序，,需进行n-1趟扫描,，,第i趟扫描是从arrayi到arrayn-1中,，经过n-i次比较，选出,关键字最小,的元素，,置于arrayi,位置中。,算法9.5,直接选择排序算法。,void Select_Sort(NODE array,int n),/*对array中n个记录进行选择排序*/,int i,j,min;NODE temp;,for(i=0;in-1;i+),min=i;,/*设min为第i趟中最小关键值记录的下标*/,for(j=i+1;jn;j+),if(arrayj.keyarraymin.key),min=j;,/*找最小关键值的下标*/,if(i!=min),temp=arrayi;arrayi=arraymin;,arraymin=temp;,直接选择排序算法的时间复杂度为O(n2)，它是一个不稳定排序。,9.3.2 树形选择排序,(1),简单树形选择排序,简单树形选择排序的方法是：首先对待排序序列中n个记录的,关键字,进行,两两比较,，将其中关键字,较小,的n/2个记录,取出,，然后将这n/2个关键字,再进行两两比较,，选择出具有,较小,关键字的记录，如此重复，直到选出一个最小关键字的记录。这个过程可用一棵有n个叶子结点的完全二叉树表示。,有一组关键字序列为49,38,65,97,76,13,27,49,，在这8个关键字中选出最小关键字的过程如图9.5(a)所示。在输出最小关键字后，仅需将叶子结点中最小关键字(13)改为“最大值”，然后调整从树叶到根结点的路径上各结点的关键字，则根结点的关键字为次小关键字，如图9.5(b)所示。同理，可依次选出从小到大的所有关键字。,图9.5 树形选择排序的示例,时间复杂度:O(nlog2n),缺点:,是占用较多的存储空间来保存比较结果。,(2),堆排序,堆的定义：,有n个记录的线性序列，其关键值序列为(k1,k2,kn)，满足如下条件：,ki=k2i 2i=n,ki=2i+1 2i+1=n,为在C语言中设计算法方便，修改堆定义为：若关键值序列为(k0,k1,kn-1)，满足如下条件：,ki=k2i 2i+1=n,ki=k2i+2 2i+2=n,称之为堆。,图9.6 堆的示例,一维数组看作是一棵完全二叉树的顺序存储形式。则堆是：完全二叉树中所有的非终端结点的关键字均不大于(或不小于)其左右孩子结点的关键字。,若在输出,堆顶,具有,最小关键字,值的记录之后，使得,剩余,n-1记录的序列,重,又,建,成一个,堆,，则,得到,n个记录中关键字,次小值,。如此反复执行，直到得到一个有序序列，这个过程称为堆排序。由此，实现,堆排序,需要,解决两个问题,：,如何将一个待排序序列,建成,一个,堆,？,如何在输出堆顶记录之后，,调整,剩余记录成一个,新堆,?,关键字序列13,38,27,49,76,65,49,97是一个堆，如图9.7(a)所示，在输出堆顶记录之后，以,堆中,最后,一个元素替代,之，如图9.7(b)所示。此时，根结点的,左、右子树均为堆,，则仅需自上而下,进行调整,即可。首先以堆顶元素和其,左、右子树,根结点的,较小值,27,比较,，因堆顶元素97大，所以二者交换。交换之后又破坏右子树“堆”，则需要进行和上述相同的调整，直至树叶(如图9.7(c)所示)或调整后子树的“堆”没有被破坏结束。,图9.7 输出堆顶元素并调整建成新堆的过程,称这个自堆顶至树叶的调整过程为“筛选”,现在讨论第一个问题，即将一个待,排序序列,建成一个堆的过程，该,过程,就是一个,反复“筛选”,的过程。此时将,序列,看成一个,完全二叉树,，并且树,最后一个非终端结点,是序列的,第trunc(n/2),个元素，在该元素开始到序列第一个元素的区间里，,依次,以,每一个元素作为堆顶进行一次“筛选”,，可将待排序序列建成一个堆。,例如，有一组关键字序列为,49,38,65,97,76,13,27,49,，,将这8个关键字建成一个堆的过程如图9.8所示。,称这个自堆顶至树叶的调整过程为“筛选”,图9.8 将待排序列建成堆的过程,算法9.6,堆排序算法。,void heapshift(NODE array,int i,int n),/*对以arrayi为顶的堆，进行筛选，n为待排序列长度*/,NODE temp=arrayi;,int j=2*i+1;/*j为结点i左孩子的下标*/,while(jarrayj.key),arrayi=arrayj;i=j;j=2*i+1;,else break;,/*筛选结束*/,arrayi=temp;,/*arrayi是temp应在的位置*/,未完结下一页,void heapsort(NODE array,int n),/*对存放在array中，长度为n的序列进行对排序*/,int i;NODE temp;,for(i=n/2-1;i=0;i-),heapshift(array,i,n);,/*以每一个非终端结点为堆顶，筛选建立堆*/,for(i=n-1;i0;i-),temp=array0;array0=ai;,ai=temp;,/*将最小值交换至数组末尾*/,/*从array0开始在array0到arrayi-1之间筛选*/,heapshift(a,0,i);,堆排序的时间复杂度O(nlog2n)，它是一种不稳定的排序方法。,9.4 归并排序,归并是将两个有序序列归并为一个有序序列。将2-路归并的思想用于有n个记录的待排序列中，就得到归并排序。首先，把n个记录看成是长度为1有序表，将它们两两归并，得到长度为2的若干个有序子表，重复上述过程，直到得到长度为n的有序表为止。,例如，有一组关键字序列为,49,38,65,97,76,13,27,对这7个关键字进行归并排序的过程如图9.9所示。,下标,0,1,2,3,4,5,6,初始关键字,49,38,65,97,76,13,27,-,一趟归并之后,38,49,65,97,76,13,27,-,二趟归并之后,38,49,65,97,13,27,76,-,三趟归并之后,13,17,38,49,65,76,97,图9.9 2-路归并排序的示例,归并排序的时间复杂度为O(log2n)，是一种稳定的排序方法，但该算法所占用空间较大，需要一个与待排序列相同的辅助空间。具体算法由读者根据两个有序序列归并算法，即“平移指针，一次扫描”的算法，自己完成。,