非序 540、3、、头197如9向相反方向移动 4875、7199如19向相反方向移动 919如9向最终方向移动 34 如13向相反方向移动 6791157 1319344875如13向最终方向移动 6791113543344875如4向相反方向移动 679111319 38344875 679111319345740384875 9-4试修改起泡排序算法,在正反两个方向交替进行扫描,即第一趟把排序码最大的对象放 到序列的最后,第二趟把排序码最小的对象放到序列的最前面。如此反复进行 【解答1】 template <class Type> void dataList<Type> : shaker Sort(i 奇数趟对表 Vector从前向后,比较相邻的排序码,遇到逆序即交换,直到把参加比较排序码序列 ∥中最大的排序码移到序列尾部。偶数趟从后向前,比较相邻的排序码,遇到逆序即交换,直到把 ∥参加比较排序码序列中最小的排序码移到序列前端。 int i=l, j; int exchange; while( i<currentsize )i 起泡排序趟数不超过n-1 exchange = 0: ∥假定元素未交换 for(=CurrentSize-i;j>=i;j--) ∥逆向起泡 if( Vector[j-1>Vector])t ∥发生逆序 Swap( VectorJj-1] Vector]); ∥交换,最小排序码放在 Vector[1处 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; ∥交换,最大排序码放在 ector处 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