16.(1)此为直接插入排序算法,该算法稳定。 (2)r[0]的作用是监视哨,兔去每次检测文件是否到尾,提高了排序效率 采用x.key<=r[j].key描述算法后,算法变为不稳定排序,但能正常工作。 17.(1)横线内容:①m②1③0 (2)flag起标志作用。若未发生交换,表明待排序列已有序,无需进行下趟排序 (3)最大比较次数n(n-1)/2,最大移动次数3n(n-1)/2 (4)稳定 18.(1)①499②A[j>A[j+1]③b:=true(②2)冒泡排序(3)499次比较,0次交换 (4)n(n-1)/2次比较,n(n-1)/2次交换(相当3n(n-1)/2次移动),本题中n=500,故 有124750次比较和交换(相当373250次移动)。 19.答:此排序为双向起泡排序:从前向后一趟排序下来得到一个最大值,若其中发生交换, 则再从后向前一趟排序,得到一个最小值 12,23,35,16,25,36,19,21,16,47 二趟:12,16,23,35,16,25,36,19,21,47 12,16,23,16,25,35,19,21,36,47 四趟:12,16,16,23,19,25,35,21,36,47五趟:12,16,16,19,23,25,21,35,36,47 六趟:12,16,16,19,21,23,25,35,36,47 七趟: 12,16,16,19,21,23,25,35,36,47 .对冒泡算法而言,初始序列为反序时交换次数最多。若要求从大到小排序,则表现为初 始是上升序 21.证明:起泡排序思想是相邻两个记录的关键字比较,若反序则交换,一趟排序完成得到 一个极值。由题假设知R在R之前且K>R1,即说明R和R1是反序;设对于R之前全部记录 1—R-(其中包括K)中关键字最大为Kmax,则Kmax≥Kj,故经过起泡排序前i-2次后,R1 的关键字一定为Kmax,又因Kmax≥K>R,故R1和R为反序,由此可知R-1和R必定交换 证毕 22.采用直接插入排序算法,因为记录序列已基本有序,直接插入排序比较次数少,且由于 少量次序不对的记录与正确位置不远,使直接插入排序记录移动次数也相对较少,故选直接 插入排序算法。 23.各带标号语句的频度:(1)n (3)(n+2)(n-1)/2 (4)n(n-1)/2 (5)n-1 时间复杂度0(n2),属于直接选择排序 24 6,13,28,39,41,72,85,20 r=7↑ 20<39i=1↑m2↑r=3↑ i=3r=3m=3 r=2i=3 将r+1(即第3个)后的元素向后移动,并将20放入r+1处,结果为 6,13,20,28,39,41,72,85 (1)使用二分法插入排序所要进行的比较次数,与待排序的记录的初始状态无关。不 论待排序序列是否有序,已形成的部分子序列是有序的。二分法插入首先査找插入位置,插 入位置是判定树查找失败的位置。失败位置只能在判定树的最下两层上。 (2)一些特殊情况下,二分法插入排序要比直接插入排序要执行更多的比较。例如,16. (1)此为直接插入排序算法，该算法稳定。 (2)r[O]的作用是监视哨，免去每次检测文件是否到尾，提高了排序效率。 采用 x.key<=r[j].key 描述算法后，算法变为不稳定排序，但能正常工作。 17. (1) 横线内容:①m ②1 ③0 ④1 (2)flag 起标志作用。若未发生交换，表明待排序列已有序，无需进行下趟排序。 (3)最大比较次数 n(n-1)/2，最大移动次数 3n(n-1)/2 (4)稳定 18. (1) ①499 ②A[j]>A[j+1] ③b:=true (2)冒泡排序 (3)499次比较,0次交换 (4) n(n-1)/2 次比较，n(n-1)/2 次交换（相当 3n(n-1)/2 次移动），本题中 n=500,故 有 124750 次比较和交换（相当 373250 次移动）。 19. 答：此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换， 则再从后向前一趟排序，得到一个最小值。 一趟： 12,23,35,16,25,36,19,21,16,47 二趟：12,16,23,35,16,25,36,19,21,47 三趟： 12,16,23,16,25,35,19,21,36,47 四趟：12,16,16,23,19,25,35,21,36,47 五趟：12,16,16,19,23,25,21,35,36,47 六趟： 12,16,16,19,21,23,25,35,36,47 七趟： 12,16,16,19,21,23,25,35,36,47 20. 对冒泡算法而言，初始序列为反序时交换次数最多。若要求从大到小排序，则表现为初 始是上升序。 21. 证明：起泡排序思想是相邻两个记录的关键字比较，若反序则交换，一趟排序完成得到 一个极值。由题假设知 Rj 在 Ri 之前且 Kj>Ri，即说明 Rj和 Ri 是反序；设对于 Ri 之前全部记录 1—Ri-1(其中包括 Kj)中关键字最大为 Kmax，则 Kmax≥Kj，故经过起泡排序前 i-2 次后，Ri-1 的关键字一定为 Kmax，又因 Kmax≥Kj>Ri，故 Ri-1和 Ri 为反序，由此可知 Ri-1和 Ri 必定交换， 证毕。 22.采用直接插入排序算法，因为记录序列已基本有序，直接插入排序比较次数少，且由于 少量次序不对的记录与正确位置不远，使直接插入排序记录移动次数也相对较少，故选直接 插入排序算法。 23. 各带标号语句的 频度：(1)n (2)n-1 (3)(n+2)(n-1)/2 (4)n(n-1)/2 (5)n-1 时间复杂度 O(n²), 属于直接选择排序。 24. 6, 13, 28, 39, 41, 72, 85, 20 i=1↑ m=4↑ r=7↑ 20<39 i=1↑m=2↑r=3↑ 20>13 i=3 r=3 m=3 20<28 r=2 i=3 将 r+1( 即 第 3 个 ) 后 的 元 素 向 后 移 动 ， 并 将 20 放 入 r+1 处 ， 结 果 为 6,13,20,28,39,41,72,85。 （1）使用二分法插入排序所要进行的比较次数，与待排序的记录的初始状态无关。不 论待排序序列是否有序，已形成的部分子序列是有序的。二分法插入首先查找插入位置，插 入位置是判定树查找失败的位置。失败位置只能在判定树的最下两层上。 （2）一些特殊情况下，二分法插入排序要比直接插入排序要执行更多的比较。例如