第十章排序-例题

例题1：已知序列{17，18，60，40，7，32，73，65，85}，请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。

解：依题意，采用冒泡排序法排序的各趟的结果如下：

初始：17，18，60，40，7，32，73，65，85

第1趟：17，18，40，7，32，60，65，73，85

第2趟：17，18，7，32，40，60，65，73，85

第3趟：17，7，18，32，40，60，65，73，85

第4趟：7，17，18，32，40，60，65，73，85

第5趟：7，17，18，32，40，60，65，73，85

第5趟无元素交换，则排序结束。

例题2：已知序列{503，87，512，61，908，170，897，275，652，462}，采用快速排序法对该序列作升序排序时的每一趟的结果。

解：依题意，采用快速排序法排序的各趟的结果如下

初始：503，87，512，61，908，170，897，275，652，462

第1趟：[462，87，275，61，170 ] 503[897，908，652，512 ]

第2趟：[170，87，275，61 ] 462，503 [897，908，652，512 ]

第3趟：[61，87 ]170 [275] 462，503 [897，908，652，512 ]

第4趟：61 [87 ]170 [275] 462，503 [897，908，652，512 ]

第5趟：61，87，170 [275] 462，503 [897，908，652，512 ]

第6趟：61，87，170，275，462，503 [897，908，652，512 ]

第7趟：61，87，170，275，462，503 [512，652] 897 [908 ]

第8趟：61，87，170，275，462，503，512 [652] 897 [908 ]

第9趟：61，87，170，275，462，503，512，652，897 [908 ]

第10趟：61，87，170，275，462，503，512，652，897，908

例题3：已知序列{42，13，24，91，23，16，05，88}，试给出对其建大根堆过程中完全二叉树及其存储结果的变化情况。

解：

依题意，建大根堆过程中完全二叉树及其存储结果的变化情况如图10.1所示。

图10.1大根堆建堆过程图

例题4：已知序列{503，87，512，61，908，170，897，275，652，462}，采用基数排序法对该序列作升序排序时的每一趟的结果。

解：依题意，采用基数排序法排序的各趟的结果如下：

初始：503，87，512，61，908，170，897，275，652，462

第1趟（按个位排序）：170，61，512，652，462，503，275，87，897，908

第2趟（按十为排序）：503，908，512，652，61，462，170，275，87，897

第3趟（按百为排序）：61，87，170，275，462，503，512，652，897，908

例题5：已知序列{10，18，4，3，6，12，1，9，15，8}，请给出采用归并排序法对该序列作升序排序时的每一趟的结果。

解：依题意，采用归并排序法排序的各趟的结果如下：

初始：10，18，4，3，6，12，1，9，15，8

第1趟：[ 10，18 ] [3，4 ] [6，12 ] [1，9 ] [ 8，15]

第2趟：[3，4，10，18 ] [1，6，9，12 ] [ 8，15 ]

第3趟：[1，3，4，6，9，10，12，18 ] [ 8，15 ]

第4趟：[1，3，4，6，8，9，10，12，15，18 ]

第4趟归并完毕，则排序结束。

例题6：设计一个函数修改冒泡排序过程以实现双向冒泡排序。

解：

冒泡排序是从最下面的记录开始，对每两个相邻的关键字进行比较，且使关键字较小的记录换至关键字较大的记录之上，使得经过一趟冒泡排序后，关键字最小的记录到达最上端，接着，再在剩下的记录中找关键字最小的记录，并把它换在第二位置上。依次类推，一直到所有记录都有许为止。双向冒泡排序则是每一趟通过每两个相邻的关键字进行比较，产生最小和最大的元素。实现双向冒泡排序的函数如下：

voiddbubble (sqlistr) {

inti=1, j , b=1;

structrec t; while (b) { b=0;

for ( j=n-i+1; j>=i+1; j--)

if ( r[j].key

t=r[j];

r[j]=r[j-1]; r[j-1]=t;

}

for ( j=i+1; j<=n-i; j++)

if (r[j].key>r[j+1].key ) { b=1; t=r[j];

r[j]=r[j+1];

r[j+1]=t; } i++; } }