习题解答
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 -