数据结构-选择排序PPT学习课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,选择排序（,Selection sort,）,1,选择排序（,Selection sort,）是以选择为基础的一种常用排序方法，从记录的无序子序列中,“,选择,”,关键字最小或最大的记录，并将其加入到有序子序列的一端，以增加记录的有序子序列的长度。它也有几种不同的实现方法，这里仅介绍简单选择排序、树形排序和堆排序。,2,1.,简单选择排序,（,1,）算法描述,简单选择排序算法的基本思路：对于一组关键字,(Kl,，,K2,，,，,Kn),，将其由小到大进行排序,首先从,Kl,，,K2,，,，,Kn,中选择最小值，假设是,Kk,，则将,Kk,与,K1,对换；然后从,K2,，,K3,，,，,Kn,中选择最小值,Kk+1,，再将,Kk+1,与,K2,对换。如此进行选择和调换，对第,i,趟选择排序，进行,n-i,次关键字比较，从,n-i+1,个记录中选出关键字最小的记录，并与第,i,个记录交换。令,i,从,1,至,n-1,，进行,n-1,趟选择排序，一个由小到大的有序序列就形成了。,3,例,1,设有一组关键字,49,，,39,，,66,，,49*,，,76,，,11,，,27,，,96,，这里,n,8,。试用简单选择排序方法，将这组记录由小到大进行排序。其排序过程如图所示，,4,算法实现如下：,void SelectSort(SqList&L),/*,对顺序表,L,作简单选择排序。*,/,int i,j;RedType temp;,for(i=1;iL.length;+i),/*,选择第,i,小的记录并交换到位*,/,j=SelectMinKey(L,i);,/*,在,L.ri.L.length,中选择,key,最小的记录*,/,if(i!=j),/*L.riL.rj;,与第,i,个记录交换*,/,temp=L.ri;L.ri=L.rj;L.rj=temp;,/*SelectSort*/,5,（,2,）算法分析,在简单选择排序中，无论待排序的记录初始序列是否有序，都需要执行,n(n-1)/2,次关键字的比较操作。如果待排序的记录初始序列就是已经排好序的正列，则无须移动记录，因为每个元素都位于其最终位置上了；而如果待排序的记录初始序列是逆序，即在最坏情况下，则要做,3(n-1),次记录移动。所以，简单选择排序的时间复杂度是,O(n*n),。,由上面的例,1,很显然看到，,49,在排序前位于,49*,的前面，而经简单选择排序后却位于,49*,后面了，它们的相对位置发生了颠倒，因此简单选择排序算法是不稳定排序算法。,6,3.,堆排序,（,1,）堆的定义,堆是一个记录序列,k1,，,k2,，,，,kn,，对于列表中位置,i,（编号从,1,开始）处的记录的关键字,ki,，当且仅当满足下列关系时，称之为堆。,kik2i,或,kik2i,kik2i+1,kik2i+1,（,i,1,，,2,，,，,n/2,）,其中，每个结点关键字都不小于其子孙结点关键字的堆称为,“,大根堆,”,；而每个结点关键字都不小于其子孙结点关键字的堆称为,“,小根堆,”,。下面的讨论中以小根堆为例。,7,判断下列序列是否为堆？,(100,，,85,，,98,，,77,，,80,，,60,，,82,，,40,，,20,，,15,，,67),(100,，,98,，,85,，,82,，,80,，,77,，,60,，,40,，,20,，,15,，,67),(15,，,20,，,40,，,60,，,67,，,77,，,80,，,82,，,85,，,98,，,100),8,我们已经知道，对于一棵有,n,个结点的完全二叉树，当它的结点由上而下，自左至右编号之后，编号为,1,n/2,的结点为分支结点，编号大于,n/2,的结点为叶子结点，对于每个编号为,i,的分支结点，它的左孩子的编号为,2i,，它的右孩子的编号为,2i+1,。对于每个编号为,i,（,i,1,）的结点，它的双亲的编号为,i/2,。,因此，我们还可以借助完全二叉树来描述堆的概念：若完全二叉树中任一非叶子结点的值均小于等于,(,或大于等于,),其左、右孩子结点的值，则从根结点开始按结点编号排列所得的结点序列就是一个堆。,9,10,（,2,）算法描述,堆顶记录对应完全二叉树的根结点，堆顶记录关键字是所有记录关键字的最值，堆排序就是利用堆的上述特征完成排序的。在输出堆顶的最大（或最小）之后，使得剩余的,n-1,个记录的序列重新调整为一个堆，于是又得到次大（或次小）值,如此反复执行，直至所以记录都排序为一个有序序列。这就是堆排序（,Heap Sort,）。,11,由于初始记录序列不一定满足堆关系，因此堆排序过程大体分两步处理：,初建堆。从堆的定义出发，先取,i=n/2(,它一定是第,n,个结点双亲的编号,),，将以,i,结点为根的子树调整成为堆；然后令,i=i-1,；再将以,i,结点为根的子树调整成为堆。此时可能会反复调整某些结点，直到,i=1,为止，堆初建完成。,堆排序。首先输出堆顶元素,(,一般是最小值,),，让堆中最后一个元素上移到原堆顶位置，然后恢复堆，因为经过第一步输出堆顶元素的操作后，往往破坏了原来的堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的操作，直到全部元素输出完为止。按输出元素的前后次序排列，就形成了有序序列，完成了堆排序的操作。,12,例,设有,n,个记录,(n,8),的关键字是,30,，,50,，,60,，,35,，,86,，,10,，,40,，,45,，试用堆排序方法，将这组记录由小到大进行排序。,13,第一步：初始建堆，其建堆过程如图所示。因为,n=8,，所以从,i,4,开始。,14,第二步：堆排序。这是一个反复输出堆顶元素，将堆尾元素移至堆顶，再调整恢复堆的过程。恢复堆的过程与初建堆中,i=1,时所进行的操作完全相同。,请注意：每输出一次堆顶元素，堆尾的逻辑位置退,1,，直到堆中剩下一个元素为止，排序过程如图所示。,15,16,输出序列：,10 30 35 40 45 50 60 86,17,由上可知，调整恢复堆操作过程要被多次反复调用，即当,i,值确定之后，以,ki,为比较参照值，与其左、右孩子的关键字比较和调整，使以结点,i,为根的子树成为堆，因此把此过程设计成函数,Heap,：,void Heap(RedType r,，,int i,，,int m),/*i,是根结点编号，,m,是以,i,结点为根的子树的最后一个结点编号*,/,x=ri,；,j=2*i,；,/*x,保存根记录的内容，,j,为左孩子编号*,/,while(j=m),if(j,m&rj,key,rj+1,key),j+,；,/*,当结点,i,有左、右两个孩子时，,j,取关键字值较小的孩子结点编号*,/,if(rj.key,x.key),ri=rj,；,i=j,；,j=2*i,；,/*,向下一层探测*,/,else j=m+1,；,/*x.key,小于左、右孩于的关键字，强制使,j,m,，以便结束循环*,/,ri=x,；,/*Heap*/,18,另外，还需要设计一个主体算法，使在初建堆阶段，让,i从,n/2,变化到,1,，循环调用,heap,函数，而在堆排序阶段，每输出一次堆顶元素，将堆尾元素移至堆顶之后，就要调用一次,heap,函数来恢复堆。主体算法由函数,Heapsort,来实现：,void Heapsort(RedType r,，,int n),/*n,为文件的实际记录数，,ro,没有使用*,/,for(i=n/2,；,i,=1,；,i-)Heap(r,，,i,，,n),；,/*,初建堆*,/,for(v=n;v,=2;v-),x=r1;r1=rv;rv=x,；,/*,堆顶堆尾元素对换*,/,Heap(r,1,v-1);,/*,本次比上次少处理一个记录*,/,/*Heapsort*/,19,（,3,）算法分析,在堆排序图示例中，堆越画越小，堆中结点越来越少，实际上，在用来存储堆的数组中堆顶元素输出之后并未删除，而是与堆尾元素对换。从图示看输出的是一个由小到大的升序序列，实际最后数组中记录的关键字从,rl.key,到,rn.key,是一个由大到小的降序序列。算法,Heap,的时间复杂度与堆所对应的完全二叉树的树深,log,2,n,相关，而算法,Heapsort,中对,Heap,的调用数量级为,n,，所以整个堆排序的时间复杂度为,O(nlog,2,n),。,20,稳定性如何？,21,判断下列序列是否为堆。若不是，则把它们依次调整为堆。,(100,，,85,，,98,，,77,，,80,，,60,，,82,，,40,，,20,，,15,，,67),(100,，,98,，,85,，,82,，,80,，,77,，,60,，,40,，,20,，,15,，,67),(15,，,20,，,40,，,60,，,67,，,77,，,80,，,82,，,85,，,98,，,100),练习一,22,(49,，,38,，,65,，,97,，,76,，,13,，,27,，,49*),练习二,23,