《第22讲 选择排序》由会员分享，可在线阅读，更多相关《第22讲 选择排序（13页珍藏版）》请在金锄头文库上搜索。
1、排序过程首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换；再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换；重复上述操作，共进行n-1趟排序后，排序结束。,3. 选择排序(Selection Sort),一、直接选择排序,例,初始： 49 38 65 97 76 13 27 ,i=1,13,49,一趟： 13 38 65 97 76 49 27 ,i=2,27,38,六趟： 13 27 38 49 65 76 97 ,排序结束： 13 27 38 49 65 76 97,void smp_selesort(JD r,int
2、n) int i,j,k; JD x; for(i=1;in;i+) k=i; 找最小值，记录其下标为k for(j=i+1;j=n;j+) if(rj.keyrk.key) k=j; 假如有不同的最小值，则交换 if(i!=k) x=ri; ri=rk; rk=x; ,算法描述,算法评价:记录移动次数最好情况：0最坏情况：3(n-1)比较次数：,时间复杂度: T(n)=O(n),堆的定义：n个元素的序列(k1,k2,kn)，当且仅当满足下列关系时，称之为堆.,例: (96，83，27，38，11，9),例 （13，38，27，50，76，65，49，97）,堆实质上是一棵完全二叉树，堆顶元素
3、（完全二叉树的根）为序列中n个元素的最小值或最大值.,二 、堆排序（Heap Sort）,堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序.,堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？,第二个问题解决方法筛选方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”.,例,算法描述,第一个问题解决方法 从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选.,如何由一个无序序列建成一个堆？,例 含8个元素的无序序列（49，38，65，97，76，13，27，50）,50,97,13,65,38,13,27,49,算法评价时间复杂度：最坏情况下T(n)=O(nlogn)空间复杂度：S(n)=O(1),算法描述,
