习题解答

Bub_Sort1(Ar, n) {

for (i=1; i

/* 这趟发生交换标志 */

for (j=1; j<=n-i; j++) if (Ar[j].key

temp = Ar[j+1]; Ar[j] = Ar[j+1]; Ar[j+1] = temp; flag = 1;

}

if (flag == 0) break; } }

/* 若没有发生交换，就结束算法 */ /* 这趟扫描的范围是从1到n-i */ /* 通过temp进行交换 */

/* 对无序记录序列进行n-1趟扫描 */

2．有待排关键字序列：68、70、67、73、23、67、28、92、18，以图示的方式对它进行快速排序，并说明快速排序是一种不稳定的排序算法。 答：图(a)是快速排序一次划分前的初始状态，图(b)是一次划分完成时的结果，这时关键字68已经到达它的最终位置，其他关键字被分为左、右两个子序列。

下面专门来看左边的待排子序列，它由A[1]=18、A[2]=28、A[3]=67、A[4]=67、A[5]=23组成，对其进行快速排序一次划分前的初始状态如图(c)所示，一次划分完成时的结果，关

- 41 -

习题解答

键字18已经到达它的最终位置，其他关键字只有右子序列，如图(d)所示。图(e)~图(h)表示对右字序列一次划分的过程。从最终结果可以看出，原来在左边的67现在被安排到了右边，如图(h)所示。这表明快速排序不具有稳定性。 3．把直接选择排序算法修改成各关键字最终由大到小排列。 答：修改的算法如下所示。

Sel_sort(Ar, n) {

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

large = i;

/* 用变量large记住当前最大关键字的位置 */

for (j = i+1; j<=n; j++) large = j; if (large != i) {

temp = Ar[i]; Ar[i] = Ar[large]; Ar[large] = temp;

} } }

/* 交换是利用临时变量temp进行的 */

/* large与比较范围首元素下标不同，则交换 */ /* j控制这趟扫描的比较范围 */

/* 如果发现更大者，随时修改large的值 */

/* i控制n-1趟扫描 */

if (Ar[j].key>Ar[large].key)

4．已知待排的关键字序列：70、83、99、65、10、32、7、9，请给出采用直接插入排序方法时每趟的图示过程。 答：采用直接插入排序方法时每趟的图示过程如下。

5．有待排序的关键字序列：18、02、22、15、56、18、88、27、68，请给出采用冒泡排序方法时每趟的图示过程（注意：这里有两个关键字都是18）。 答：采用冒泡排序方法时每趟的图示过程如下。

- 42 -

习题解答

过程性测试1到9

- 43 -