数据结构 第10章 排序3-选择排序

第10章排序数据结构讲义-选择排序10.4选择排序基本思想：在待排记录中依次选择关键字最小的记录作为有序序列的最后一条记录，逐渐缩小范围直至全部记录选择完毕。简单选择排序[4938659776132749]13[38659776492749]1327[659776493849]132738[6597764949]13273849[65977649]1327384949[659776]132738494965[9776]1327384949657697voidSelectSort(SqList&K){//简单选择排序for(i=1;iL.length;++i){//在L.r[i..L.length]中选择key最小的记录k=i;for(j=i+1;j=L.length;j++)if(L.r[j].keyL.r[k].key)k=j;if(k!=i)L.r[i]←→L.r[j];}}//SelectSort特点：1)算法简单,时间复杂度为O(n2)2)序列存储：顺序、链式3)稳定树型选择排序1349383838656597761313132727494938659776132749274938383865659776*27762727491．堆的定义若有n个元素(a1，a2，a3，…，an)，当满足如下条件：ai≤a2iai≥a2i（1）ai≤a2i+1或(2)ai≥a2i+1其中i=1,2,…,n/2，则称此n个元素a1，a2，a3，…，an为一个堆。若将此元素序列按顺序组成一棵完全二叉树，则（1）称为小根堆（二叉树的所有根结点值小于或等于左右孩子的值），（2）称为大根堆（二叉树的所有根结点值大于或等于左右孩子的值）。堆排序小根堆8169162111054大根堆1698106211154168129162115141981061621154不是堆不是堆序列(80,75,40,62,73,35,28,50,38,25,47,15)可以验证它满足堆的条件,因此是一个堆.下图给出其对应的完全二叉树。180754062732835503825471532456789101112堆与完全二叉树堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫~.堆排序需解决的两个问题：–如何由一个无序序列建成一个堆？–如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？第二个问题解决方法——筛选输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”.例13273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13273849502765769713输出：13276549502738769713输出：1327384965502738769713输出：1327387665502738499713输出：132738495065762738499713输出：132738499765762738495013输出：13273849506597762738495013输出：13273849509765762738495013输出：1327384950657665972738495013输出：1327384950659765762738495013输出：132738495065769765762738495013输出：1327384950657697第一个问题解决方法从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选。例：含8个元素的无序序列（49，38，65，97，76，13，27，50）496538271376975049653827137650974913382765765097491338276576509713273849657650974913382765765097算法评价时间复杂度：–最坏情况下T(n)=O(nlogn)空间复杂度：–S(n)=O(1)堆排序是不稳定的；堆排序适用于n较大的情况。作业若一组记录的关键码为（46,79,56,38,40,84），画出利用堆排序的方法建立的初始堆图，以及输出每一个堆顶元素的筛选过程图。