第9章排序 输出20,调整胜者树 排序码比较 次数=0 输出28,调整胜者树 排序码比较 次数=2 输出30,排序完成 排序码比较 次数=0 包圖回函回应鹵口亡 7)堆排序 第一步,形成初始的最大堆(略),第二步,做堆排序 初始排列,不是最大堆 形成初始最大堆 交换0与9对象
第 9 章 排序 6 (7) 堆排序 第一步，形成初始的最大堆 (略)，第二步，做堆排序。 初始排列，不是最大堆 形成初始最大堆 交换 0 # 与 9 # 对象 12 2 16 30 28 10 16* 20 6 18 12 30 28 20 18 输出 20，调整胜者树 12 2 16 30 28 10 16* 20 6 18 12 30 18 18 18 30 28 20 排序码比较 次数 = 0。 20 20 20 输出 28，调整胜者树 12 2 16 30 28 10 16* 20 6 18 12 30 18 18 18 30 28 20 排序码比较 次数 = 2。 28 28 28 输出 30，排序完成 12 2 16 30 28 10 16* 20 6 18 12 30 18 18 18 30 28 20 排序码比较 次数 = 0。 28 30 30 12 2 16 30 28 10 16* 20 6 18 30 28 16 20 18 10 16* 2 6 12 12 28 16 20 18 10 16* 2 6 30 28 20 16 12 18 10 16* 20 16 12 18 10 16* 28 20 18 16 12 6 10 16*
第9章排序 从0#到8#重新形成堆交换0#与8#对象从0#到7#重新形成堆 (o(8 交换0#与7#对象从O#到6#重新形成堆 换0#与6#对象 710 从O#到5#重新形成堆 交换0#与5#对象 从0#到4#重新形成堆 交换0#与4#对象 从0#到3#重新形成堆 换0#与3#对象 从0#到2#重新形成堆交换O#与2#对象从0#到1#重新形成堆 交换0#与1#对象 从0#到1#重新形成堆,得到结果 7
第 9 章 排序 7 从 0# 到 8# 重新形成堆 交换 0# 与 8# 对象 从 0# 到 7# 重新形成堆 交换 0# 与 7# 对象 从 0# 到 6# 重新形成堆 交换 0# 与 6# 对象 从 0# 到 5# 重新形成堆 交换 0# 与 5# 对象 从 0# 到 4# 重新形成堆 交换 0# 与 4# 对象 从 0# 到 3# 重新形成堆 交换 0# 与 3# 对象 从 0# 到 2# 重新形成堆 交换 0# 与 2# 对象 从 0# 到 1# 重新形成堆 交换 0# 与 1# 对象 从 0# 到 1# 重新形成堆，得到结果 2 6 30 6 2 30 2 28 30 2 18 16 12 6 10 16* 20 28 30 18 12 16 2 6 10 16* 20 28 30 12 16 2 6 10 16* 20 28 30 18 10 12 16 2 6 16* 20 28 30 10 12 16 2 6 16* 20 28 30 18 18 16 12 10 2 6 16* 20 28 30 18 6 12 10 2 16 16* 20 28 30 18 12 6 10 2 16 16* 20 28 30 18 2 6 10 12 16 16* 20 28 30 18 10 6 2 12 16 16* 20 28 30 18 2 6 10 12 16 16* 20 28 30 18 6 2 10 12 16 16* 20 28 30 18 2 6 10 12 16 16* 20 28 30 18 2 6 10 12 16 16* 20 28 30 18
第9章排序 (8)二路归并排序 采用迭代的方法进行归并排序。设待排序的数据对象有n个。首先把每一个待排序的数 据对象看作是长度为的初始归并项,然后进行两两归并,形成长度为2的归并项,再对它们 两两归并,形成长度为4的归并项,如此一趟一趟做下去,最后得到长度为n的归并结果。 排序码比较5次 21216301028 排序码比较6次 1216301[01620281[618 排序码比较7次 210121616202830 排序码比较9次 2610121616·182 (9)基数排序 12}[2}[16}[30}[28}[0}[16}-[20}-6}□18 按最低位分配 r[]r[2]rB]4]f]r]r7r[8r9 16 [o f 1 f2 f3 f4 f5 f6 f7 f8 f9 收集[30}[10[20}-[12}[2}[16}-[16}[6}[28}[8 按最高位分配 r[o r[ 2]r[r4]rr6]t[7r8]r19 0]t1 2]134]ff6]7f8]9 收集[2[6[10[12[6}[16-}[18}[20-28}[30 9-3在起泡排序过程中,什么情况下排序码会朝向与排序相反的方向移动,试举例说明。在 快速排序过程中有这种现象吗? 【解答】 如果在待排序序列的后面的若干排序码比前面的排序码小,则在起泡排序的过程中,排 序码可能向与最终它应移向的位置相反的方向移动。例如
第 9 章 排序 8 (8) 二路归并排序 采用迭代的方法进行归并排序。设待排序的数据对象有 n 个。首先把每一个待排序的数 据对象看作是长度为的初始归并项，然后进行两两归并，形成长度为 2 的归并项，再对它们 两两归并，形成长度为 4 的归并项，如此一趟一趟做下去，最后得到长度为 n 的归并结果。 (9) 基数排序 收集 按最高位分配 收集 9-3 在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在 快速排序过程中有这种现象吗？ 【解答】 如果在待排序序列的后面的若干排序码比前面的排序码小，则在起泡排序的过程中，排 序码可能向与最终它应移向的位置相反的方向移动。例如， 12 2 16 30 28 10 16* 20 6 18 2 12 16 30 10 28 16* 20 12 6 18 2 12 16 30 10 16* 20 28 6 18 2 10 12 16 16 6 18 * 20 28 30 2 6 10 12 16 16* 18 20 28 30 12 2 16 30 28 10 16* 20 6 18 按最低位分配 r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 12 2 30 16 28 10 16* 20 6 18 30 10 20 12 2 16 16* 6 28 18 r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 18 16* 16 12 2 10 20 30 6 28 16* 2 6 10 12 16 18 20 28 30 排序码比较 5 次 排序码比较 6 次 排序码比较 7 次 排序码比较 9 次
第9章排序 540、3、、头197如9向相反方向移动 75.7 如19 向相反方向 移动 919如9向最终方向移动 13344719如13向相反方向移动 向最 终方向移动 6791113543344875如4向相反方向移动 679111319 38344875 679111319345740384875 9-4试修改起泡排序算法,在正反两个方向交替进行扫描,即第一趟把排序码最大的对象放 到序列的最后,第二趟把排序码最小的对象放到序列的最前面。如此反复进行 【解答1】 template <class Type> void dataList<Type> : shaker Sort(i 奇数趟对表 Vector从前向后,比较相邻的排序码,遇到逆序即交换,直到把参加比较排序码序列 ∥中最大的排序码移到序列尾部。偶数趟从后向前,比较相邻的排序码,遇到逆序即交换,直到把 ∥参加比较排序码序列中最小的排序码移到序列前端。 while( i< currents ize)i 起泡排序趟数不超过n-1 exchange = 0: ∥假定元素未交换 for(=CurrentSize-i;j>=i;j--) ∥逆向起泡 if( Vector[j-1>Vector])t ∥发生逆序 Swap( VectorJj-1] Vector]); ∥交换,最小排序码放在 Vector[i-处 exchange =1: ∥做“发生了交换”标志 if( exchange =0)break; m当 exchange为0则停止排序 for (j=1;j<= CurrentSize-i-1; j++) ∥正向起泡 if( Vector> Vector[+1)i Swap( vector[, Vector [+1; ∥交换,最大排序码放在 Vector-订处 exchange =1: ∥做“发生了交换”标志 if( exchange ==0) break; ∥当 exchange为0则停止排序 【解答2】 template <class Type> void dataList<Type>: shaker Sort(t int low=l, high=Currents ize-l, i, j; int exchange; while( low high)( ∥当比较范围多于一个对象时排序 ∥记忆元素交换位置 for (i=lov ∥正向起泡 if( Vector[>Vector[i+1])i ∥发生逆序 Swap( Vector[i], Vector[i+1]); ∥交换 记忆右边最后发生交换的位置j ∥比较范围上界缩小到j
第 9 章 排序 9 57 40 38 11 13 34 48 75 6 19 9 7 如 9 向相反方向移动 6 57 40 38 11 13 34 48 75 7 19 9 如 19 向相反方向移动 6 7 57 40 38 11 13 34 48 75 9 19 如 9 向最终方向移动 6 7 9 57 40 38 11 13 34 48 75 19 如 13 向相反方向移动 6 7 9 11 57 40 38 13 19 34 48 75 如 13 向最终方向移动 6 7 9 11 13 57 40 38 19 34 48 75 如 34 向相反方向移动 6 7 9 11 13 19 57 40 38 34 48 75 6 7 9 11 13 19 34 57 40 38 48 75 9-4 试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把排序码最大的对象放 到序列的最后，第二趟把排序码最小的对象放到序列的最前面。如此反复进行。 【解答 1】 template <class Type> void dataList<Type> :: shaker_Sort ( ) { //奇数趟对表 Vector 从前向后, 比较相邻的排序码, 遇到逆序即交换, 直到把参加比较排序码序列 //中最大的排序码移到序列尾部。偶数趟从后向前, 比较相邻的排序码, 遇到逆序即交换, 直到把 //参加比较排序码序列中最小的排序码移到序列前端。 int i = 1, j; int exchange; while ( i < CurrentSize ) { //起泡排序趟数不超过 n-1 exchange = 0; //假定元素未交换 for ( j = CurrentSize-i; j >= i; j-- ) //逆向起泡 if ( Vector[j-1] > Vector[j] ) { //发生逆序 Swap ( Vector[j-1], Vector[j] ); //交换, 最小排序码放在 Vector[i-1]处 exchange = 1; //做“发生了交换”标志 } if ( exchange == 0 ) break; ////当 exchange 为 0 则停止排序 for ( j = i; j <= CurrentSize-i-1; j++ ) //正向起泡 if ( Vector[j] > Vector[j+1] ) { //发生逆序 Swap ( Vector[j], Vector[j+1] ); //交换, 最大排序码放在 Vector[n-i]处 exchange = 1; //做“发生了交换”标志 } if ( exchange == 0 ) break; //当 exchange 为 0 则停止排序 i++; } } 【解答 2】 template <class Type> void dataList<Type> :: shaker_Sort ( ) { int low = 1, high = CurrentSize-1, i, j; int exchange; while ( low < high ) { //当比较范围多于一个对象时排序 j = low; //记忆元素交换位置 for ( i = low; i < high; i++ ) //正向起泡 if ( Vector[i] > Vector[i+1] ) { //发生逆序 Swap ( Vector[i], Vector[i+1] ); //交换 j = i; //记忆右边最后发生交换的位置 j } high = j; //比较范围上界缩小到 j