数据结构第章排序2选择排序归并排序基数排序.pptxVIP

数据结构 Data Structures;第10章 内部排序;选择排序 ;简单选择排序 ;简单选择排序 ;简单选择排序算法描述 ;简单选择排序算法分析 ;树形选择排序 (又称锦标赛排序 ) ;;第二趟：;令其Tag＝0,不参与比较;;;;;树形选择排序算法 ;锦标赛排序的算法 void TournamentSort ( Type a[ ], int n ) {　int bottomRowSize = PowerOfTwo ( n ); //乘幂值 计算满足＞＝n的2的最小次幂的数　int TreeSize = 2*bottomRowSize-1; //总结点个数　int loadindex = bottomRowSize-1; //内结点个数　DataNode tree[TreeSize];　int j = 0; //从 a 向胜者树外结点复制数据　for ( int i = loadindex; i TreeSize; i++) {　　tree[i].index = i; 　　if ( j n ) {　　　 tree[i].active = 1;　　　 tree[i].data = a[j++];　　} 　　else tree[i].active = 0; 　}　i = loadindex; //进行初始比较选择最小的项　while ( i ) {　　j = i;　　while ( j 2*i ) { 　　　if ( !tree[j+1].active||tree[j].data tree[j+1].data ) //胜者送入双亲　　　　tree[(j-1)/2] = tree[j]; 　　　else　　　　tree[(j-1)/2] = tree[j+1];　　　j += 2;　　}　　i = (i-1)/2; // i 退到双亲, 直到 i==0为止　};锦标赛排序中的调整算法 void UpdateTree ( DataNode *tree, int i ) {　if ( i %2 == 0 )　　tree[(i-1)/2] = tree[i-1]; //i偶数, 对手左结点　else　　tree[(i-1)/2] = tree[i+1]; //i奇数, 对手右结点　i = (i-1) / 2; //向上调整 　while ( i ) { //直到 i==0　　if ( i %2 == 0) 　　　j = i-1;　　else 　　　j = i+1;　　if ( !tree[i].active || !tree[j].active )　　　if ( tree[i].active )　　　　tree[(i-1)/2] = tree[i]; //i可参选, i上　　　else 　　　　tree[(i-1)/2] = tree[j]; //否则, j上　　else //两方都可参选 　　　if ( tree[i].data tree[j].data ) 　　　　tree[(i-1)/2] = tree[i]; //关键码小者上　　　else 　　　　tree[(i-1)/2] = tree[j];　　i = (i-1) / 2; // i上升到双亲　}};树形选择排序算法分析 ;堆排序 ;堆排序 ;怎样建堆？ ;怎样??堆？ ;怎样建堆？ ;怎样建堆？ ;怎样建堆？ ;怎样进行堆排序？ ;对建好的大根堆进行排序 ;;;;;堆排序算法 ;附1：基于初始堆进行堆排序的算法步骤 ;rc = H.r[s]; j = 2s; ;堆排序的效率分析 ;堆排序的效率分析 ;归并排序 ;归并排序 ;归并排序 ;21;一趟归并排序算法 (两路有序并为一路) ;递归形式的两路归并排序算法 ;归并排序算法分析 ;基数排序 ;基数排序 ;基数排序 ;基数排序 ;基数排序 ;基数排序 ;基数排序 ;基数排序 ;基数排序 ;例：T=（02，77，70，54，64，21，55，11），用LSD排序。 分析： ①各关键字可视为2元组；②每位的取值范围是：0-9；即基数radix ＝10 。因此，特设置10个队列，并编号为0-9。;0 1 2 3 4 5 6 7 8 9;基数排序 ; 针对 d 元组中的每一位分量，把原始链表中的所有记录, 按Kij的取值，让 j = d, d-1, …, 1， ① 先“分配”到radix个链队列中去； ② 然后再按各链队列的顺序，依次把记录从链队列中“收集”起来； ③ 分别用这种“分配”、“收集”的运算逐趟进行排序； ④ 在最后一趟“分配”、“收