9-1什么是内排序?什么是外排序?什么排序方法是稳定的?什么排序方法是不稳定的? 【解答】 9-2设待排序的关键码序列为{12,2,16,30,2810,16*,20,6,18},试分别写出使用以下排序 方法每趟排序后的结果。并说明做了多少次关键码比较。 1)直接插入排序 (2)希尔排序(增量为5,2,1)(3)起泡排序 (4)快速排序 (5)直接选择排序 (6)锦标赛排序 (7)堆排序 (8)二路归并排序 (9)基数排序 【解答】 9-3在起泡排序过程中,什么情况下关键码会朝向与排序相反的方向移动,试举例说明。在 快速排序过程中有这种现象吗? 【解答】 如果在待排序序列的后面的若干关键码比前面的关键码小,则在起泡排序的过程中,关 键码可能向与最终它应移向的位置相反的方向移动。例如, 队40、3361%7如9向相反方向移动 如19向相反方向移动 919如9向最终方向移动 679574038111334 19如13向相反方向移动 67915740381319344875如13向最终方向移动 67911135740、3819344875如34向相反方向移动 679111319 4038344875 679111319345740384875 679 9-4试修改起泡排序算法,在正反两个方向交替进行扫描,即第一趟把关键码最大的对象放 到序列的最后,第二趟把关键码最小的对象放到序列的最前面。如此反复进行。 【解答】 ∥奇数趟对表 Vector从前向后,比较相邻的关键码,遇到逆序即交换,直到把参加比较关键码序犭 ∥中最大的关键码移到序列尾部。偶数趟从后向前,比较相邻的关键码,遇到逆序即交换,直到把 ∥参加比较关键码序列中最小的关键码移到序列前端。 while(i<CurrentS)( ∥起泡排序趟数不超过n-1 ∥假定元素未交换 for(j=CurrentSie-i;j>=i;j--) ∥逆向起泡 if( Vector[-1>ector)4 ∥发生逆序 Swap( Vector[-1], vector U]); ∥交换,最小关键码放在ecor{i处 ∥做“发生了交换”标志 if( exchange ==0)break; m当 exchange为0则停止排序 for(=i;j<=CurrentSie-i1: j++) ∥正向起泡 Swap( vector[ Vector[+1); ∥交换,最大关键码放在cor[n-处 ∥做“发生了交换”标志9-1 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的? 【解答】 9-2 设待排序的关键码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序 方法每趟排序后的结果。并说明做了多少次关键码比较。 (1) 直接插入排序 (2) 希尔排序(增量为 5,2,1) (3) 起泡排序 (4) 快速排序 (5) 直接选择排序 (6) 锦标赛排序 (7) 堆排序 (8) 二路归并排序 (9) 基数排序 【解答】 9-3 在起泡排序过程中，什么情况下关键码会朝向与排序相反的方向移动，试举例说明。在 快速排序过程中有这种现象吗？ 【解答】 如果在待排序序列的后面的若干关键码比前面的关键码小，则在起泡排序的过程中，关 键码可能向与最终它应移向的位置相反的方向移动。例如， 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 6 7 9 11 13 19 34 9-4 试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把关键码最大的对象放 到序列的最后，第二趟把关键码最小的对象放到序列的最前面。如此反复进行。 【解答】 template <class Type> void dataList<Type> :: shake_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; //做“发生了交换”标志 }