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