《【教学课件】第3节选择类排序.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第3节选择类排序.ppt（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第九章 排序技术 基本思想：基本思想：基本思想：基本思想：在待排记录中依次选择关键字最小的记录作为有在待排记录中依次选择关键字最小的记录作为有序序列的最后一条记录，逐渐缩小范围直至全部序序列的最后一条记录，逐渐缩小范围直至全部记录选择完毕。记录选择完毕。9.3 选择类排序选择类排序选择类排序的具体实现算法：选择类排序的具体实现算法：一、一、简单选择排序简单选择排序 二、二、堆排序堆排序 49 38 65 97 76 49 38 65 97 76 1313 27 27 4949 13 38 65 97 76 49 13 38 65 97 76 49 2727 4949 13 27 65 97 7
2、6 49 13 27 65 97 76 49 38 38 4949 13 27 38 65 97 76 13 27 38 65 97 76 49 49 4949 13 27 38 49 65 97 76 13 27 38 49 65 97 76 4949 13 27 38 49 13 27 38 49 4949 65 65 97 76 97 76 13 27 38 49 13 27 38 49 4949 65 97 65 97 7676 13 27 38 49 13 27 38 49 4949 65 76 97 65 76 97简单选择排序的演示简单选择排序的演示一、简单选择排序一、简单选择排
3、序9.3 9.3 选择类排序选择类排序选择类排序选择类排序SelectSort(ET p,int n)/简单选择排序简单选择排序 int i,j,k;int ET p;for(i=0;i=n-2;i=i+1)/在在pi.L.length 中选择中选择key最小的记录最小的记录 k=i;/设设k为为key最小的记录最小的记录 for(j=i+1;j=n-1;j=j+1)if(p j p k)k=j;if(k!=i)d=pi;pi=pk;pk=d;/pipj;return;/SelectSort 1.1.算法描述算法描述算法描述算法描述9.3 9.3 选择类排序选择类排序选择类排序选择类排序2.时
4、间性能分析时间性能分析 对 n 个记录进行简单选择排序，所需进行的 关键字间的比较次数关键字间的比较次数 总计为：时间复杂度为时间复杂度为O(nO(n2 2)序列存储：顺序、链式序列存储：顺序、链式是一种稳定的排序方法是一种稳定的排序方法9.3 9.3 选择类排序选择类排序选择类排序选择类排序二、堆排序二、堆排序堆是满足下列性质的数列r1,r2,，rn：或或1.堆的定义堆的定义:(小顶堆小顶堆)(小根堆）小根堆）(大顶堆大顶堆)(大根堆大根堆)rir2ir2i+1若将该数列视作完全二叉树，若将该数列视作完全二叉树，则则 r r2i2i 是是 r ri i 的左孩子；的左孩子；r r2i+12i
5、+1 是是 r ri i 的右孩子。的右孩子。9.3 9.3 选择类排序选择类排序选择类排序选择类排序小根堆小根堆 8 81616 9 9 1 1 6 6 2 2 11111010 5 5 4 4大根堆大根堆1616 9 9 8 81010 6 6 2 2 1111 1 1 5 5 4 4 1 1 6 6 8 81212 9 91616 2 2 1111 5 5 1 14 4 1 1 9 9 8 81010 6 61616 2 2 1111 5 5 4 4不是堆不是堆不是堆不是堆判断下面各图是不是堆，如果是堆，指出是大堆还判断下面各图是不是堆，如果是堆，指出是大堆还是小堆。是小堆。2.2.堆与
6、完全二叉树关系堆与完全二叉树关系堆与完全二叉树关系堆与完全二叉树关系 若n个元素a1，a2，a3，an满足堆，且让结点按1、2、3、n顺序编号，根据完全二叉树的性质（若i为根结点，则左孩子为2i，右孩子为2i+1）可知，一个堆对应着一颗完全二叉树。堆排序实际是将元素初始序列组成一棵完全二叉树，包含建立初始堆（使排序码变成能符合堆的定义的完全二叉树）和利用堆进行排序两个阶段。9.3 9.3 选择类排序选择类排序选择类排序选择类排序判断序列(80,75,40,62,73,35,28,50,38,25,47,15)是不是堆？18075406273283550382547153245678910111
7、29.3 9.3 选择类排序选择类排序选择类排序选择类排序将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序。3.3.堆排序堆排序8075406273283550382547 159.3 9.3 选择类排序选择类排序选择类排序选择类排序示例示例1：建大顶堆 98,81,49,73,36,27,40,55,64,12 12,81,49,73,36,27,40,55,64,98 交换 98 和 12重新调整为大顶堆 81,73,49,64,36,27,40,55,
8、12,98 40,55,49,73,12,27,98,81,64,36 经过筛选9.3 9.3 选择类排序选择类排序选择类排序选择类排序13273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13 273849502765769713输出：13 276549502738769713输出：13 27 38示例示例2：4965502738769713输出：13 27 387665502738499713输出：13 27 38 495065762738499713输出：13 27 38 49976576
9、2738495013输出：13 27 38 49 506597762738495013输出：13 27 38 49 509765762738495013输出：13 27 38 49 50 659.3 9.3 选择类排序选择类排序选择类排序选择类排序7665972738495013输出：13 27 38 49 50 659765762738495013输出：13 27 38 49 50 65 769765762738495013输出：13 27 38 49 50 65 76 97堆排序的演示堆排序的演示9.3 9.3 选择类排序选择类排序选择类排序选择类排序3.堆排序需解决的两个问题：如何由一个
10、无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？4.第二个问题解决方法筛选方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。9.3 9.3 选择类排序选择类排序选择类排序选择类排序5.将无序序列建堆方法：从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选。8075406273283550382547 15建堆是一个从下往上进行建堆是一个从下往上进行“筛选筛选
11、”的过程。的过程。9.3 9.3 选择类排序选择类排序选择类排序选择类排序示例3：将下列元素（49，38，65，97，76，13，27，50）建堆。49653827137697504965382713765097491338276576509749133827657650971327384965765097 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 50509713653813274949133827657650976.堆排序的性能分析堆排序的性能分析时间复杂度：最坏情况下T(n)=O(nlogn)空间复杂度：S(n)=O(1)堆排序的性能：堆排序是不稳定的；堆排序适用于n 较大的情况。9.3 9.3 选择类排序选择类排序选择类排序选择类排序