数据结构_选择排序_C.ppt

* 堆排序算法 ?void HeapSort (HeapType H){ //对顺序表H进行堆排序。????for(i=H.length/2;i0;--i) //把H.r[1..length]建成大顶堆 ????????HeapAdjust(H,i,H.length);????for(i=H.length; i1; --i){ //将堆顶记录和当前未经排 //序子序列H.r.[1..i]中最后一个记录相互交换????????H.r[1]--- H.r[i]；?????????HeapAdjust(H,1,i-1); //将H.R[1..i-1]重新调整为大顶堆 ????}?} //HeapSort 4）堆排序的效率分析 在整个堆排序中，共需要进行 n+?n/2? -1 次筛选运算，每次筛选运算进行双亲和孩子或兄弟结点的排序码的比较和移动次数都不会超过完全二叉树的深度。故每次筛选运算的时间复杂度为O(log2n)，则整个堆排序过程的时间复杂度为O(nlog2n) 。 堆排序在最坏情况下，时间复杂度也为O(nlog2n)。相对于快速排序，这是堆排序的最大优点。此外，堆排序仅需一个记录大小辅助存储空间供交换使用。 由于存在着不相邻元素之间的互换，因此，堆排序是一种不稳定的排序方法。 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 第10章 内部排序 10.1 排序的基本概念 10.2 插入排序 10.3 交换排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较 10.4 选择排序 基本思想： 第i趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中的第i个记录。 1.简单选择排序 2.树形选择排序 3.堆排序 1）简单选择排序的基本思想 通过 n-i 次关键字间的比较，从无序序列[i..n]的 n-i+1 记录中选出关键字最小的记录加入有序序列（即作为有序序列中的第i个记录）。 1.简单选择排序 首先从1- - n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2 个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。 初态 8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 8 3 9 1 6 k i j i j i k 1 3 9 8 6 互换 i j 1 3 9 8 6 i j 1 3 9 8 6 i j 第一趟 第二趟 1 3 9 8 6 i j 第三趟 示例： i j k k j k 2）简单选择排序算法描述 void SelectSort (Elem R[ ], int n ) { // 对记录序列R[1..n]作简单选择排序 for (i=1; in; ++i) { //选择第i小记录换到位置i k = SelectMinKey( R, i ); if ( i != k ) R[i]←→R[k]; } } // SelectSort 3）简单选择排序算法分析 由于存在着不相邻元素之间的互换，因此，简单选择排序是“不稳定的” 。 算法实现共需要进行 n-1 次选择，每次选择需要进行n-i次比较（1≤i≤n-1），而每次交换最多需3次移动，因此，总的比较次数 C = n(n-1)/2，总的移动次数 M = 3(n-1)。故其时间复杂度为O(n2)。 选择排序的主要操作是进行关键字间的比较，因此改进选择排序应从如何减少 “比较” 考虑。 显然，在n个关键字中选出最小值，至少进行n-1次比较，然而，继续在剩余的n-1个关键字中选择次小值，是否一定要进行n-2次比较呢？ 如果能利用前n-1次比较所得信息，就可减少以后各趟选择排序中所用的比较次数。 实际上，体育比赛中的锦标赛便是一种选择排序 例 锦标赛 在8个运动员中决出前3名至多需要11场比