非序 为两个子区间,然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间 保存另一个子区间的上界和下界,待该区间处理完成后再从栈中取出另一子区间的边界, 其进行处理。这个功能利用队列也可以实现,只不过是处理子区间的顺序有所变动而已。 99试设计一个算法,使得在On)的时间内重排数组将所有取负值的排序码排在所有取正 值(非负值)的排序码之前 【解答】 template<class Type> void reArrange( dataList<Type>&L) ∥数组元素类型Type只可能取int或noat nt i=0,j=Llength 0-1; while(i=j)t while([]- getKey()<0)i++; hile(logetKey()>=0)j- swap([,Lo]); 9-10奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i扫描,第二趟 对序列中的所有偶数项i扫描。若A[>A[i+1],则交换它们。第三趟有对所有的奇数项, 第四趟对所有的偶数项,…,如此反复,直到整个序列全部排好序为止。 (1)这种排序方法结束的条件是什么? (2)写出奇偶交换排序的算法 (3)当待排序排序码序列的初始排列是从小到大有序,或从大到小有序时,在奇偶交换 排序过程中的排序码比较次数是多少? 【解答】 (1)设有一个布尔变量 exchange,判断在每一次做过一趟奇数项扫描和一趟偶数项扫描 后是否有过交换。若 exchange=1,表示刚才有过交换,还需继续做下一趟奇数项扫描和 趟偶数项扫描;若 exchange=0,表示刚才没有交换,可以结束排序 (2)奇偶排序的算法 emplate<Type> void dataList<Type>: odd-even Sort (i int i, exchange do i exchange =0: for (i=l; i< CurrentSize; i+=2) ∥扫描所有奇数项 if( Vector> Vector[i+ID)t ∥相邻两项比较,发生逆序 ∥作交换标记 swap( Vector, Vector+1);W交换 for(i=0 ∥扫描所有偶数项 f( Vector[> Vector[i+1)& ∥相邻两项比较,发生逆序 ∥作交换标记 swap( Vector, Vector[i+1]) ∥交换 i while( exchange I=0);第 9 章 排序 9 为两个子区间，然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时， 保存另一个子区间的上界和下界，待该区间处理完成后再从栈中取出另一子区间的边界，对 其进行处理。这个功能利用队列也可以实现，只不过是处理子区间的顺序有所变动而已。 9-9 试设计一个算法, 使得在 O(n)的时间内重排数组, 将所有取负值的排序码排在所有取正 值(非负值)的排序码之前。 【解答】 template<class Type> void reArrange ( dataList<Type>& L ) { //数组元素类型 Type 只可能取 int 或 float int i = 0, j = L.length () – 1; while ( i != j ) { while ( L[i].getKey( ) < 0 ) i++; while ( L[j].getKey( ) >= 0 ) j--; swap ( L[i], L[j] ); i++; j--; } } 9-10 奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项 i 扫描，第二趟 对序列中的所有偶数项 i 扫描。若 A[i] > A[i+1]，则交换它们。第三趟有对所有的奇数项， 第四趟对所有的偶数项，…，如此反复，直到整个序列全部排好序为止。 (1) 这种排序方法结束的条件是什么？ (2) 写出奇偶交换排序的算法。 (3) 当待排序排序码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换 排序过程中的排序码比较次数是多少？ 【解答】 (1) 设有一个布尔变量 exchange，判断在每一次做过一趟奇数项扫描和一趟偶数项扫描 后是否有过交换。若 exchange = 1，表示刚才有过交换，还需继续做下一趟奇数项扫描和一 趟偶数项扫描；若 exchange = 0，表示刚才没有交换，可以结束排序。 (2) 奇偶排序的算法 template<Type> void dataList<Type> :: odd-evenSort ( ) { int i, exchange; do { exchange = 0; for ( i = 1; i < CurrentSize; i += 2 ) //扫描所有奇数项 if ( Vector[i] > Vector[i+1] ) { //相邻两项比较, 发生逆序 exchange = 1; //作交换标记 swap ( Vector[i], Vector[i+1] ); //交换 } for ( i = 0; i < CurrentSize; i += 2 ) //扫描所有偶数项 if ( Vector[i] > Vector[i+1] ) { //相邻两项比较, 发生逆序 exchange = 1; //作交换标记 swap ( Vector[i], Vector[i+1] ); //交换 } } while ( exchange != 0 );