33.不是。因为当序列已有序时,快速排序将退化成冒泡排序,时间复杂度为0(n2)。当待 排序序列无序,使每次划分完成后,枢轴两侧子文件长度相当,此时快速排序性能最好。 34.初始序列:[28],07,39,10,65,14,61,17,50,21 21移动: 21,07,39,10,65,14,61,17,50,[ 39移动:21,07,[],10,65,14,61,17,50,39 21,07,17,10,65,14,61,[],50,39 移动:21,07,17,10,[],14,61,65,50,39 14移动 21,07,17,10,14,[28],61,65,50,39 类似本题的另外叙述题的解答: (1):快速排序思想:首先将待排序记录序列中的所有记录作为当前待排序区域,以第一个 记录的关键字作为枢轴(或支点)( pivot),凡其关键字不大于枢轴的记录均移动至该记录 之前,凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后,记录的无序序 列R[s..t]将分割成两部分:R[s.i-1]和R[i+1..t],且R[j].key≤R[i].key≤R[k].key(s ≤ji,i≮k≤t),然后再递归地将R[s.i-1]和R[i+1..t]进行快速排序。快速排序在记录有 序时蜕变为冒泡排序,可用“三者取中”法改善其性能,避免最坏情况的出现。具体排序实 例不再解答 35.(1)不可以,若m+1到n之间关键字都大于m的关键字时,<=k可将j定位到m上,若 为<k则j将定位到m-1上,将出界线,会造成错误。 (2)不稳定,例如2,1,2′,(m=1,n=3)对2,1,2排序,完成会变成1,2’,2 (3)各次调用 sorth的结果如下: 次调用m=1,n=10 4,18,22, 二次调用m=7,n=1011,3,16,4,18,22,40,30,58,60j=9(右部) 次调用m=10,n=10不变,返回m=7,n=811,3,16,4,18,22,30,40,58,60j=8 四次调用m=9,n=8不变,返回m=7,n=7返回m=1,n=5 4,3,11,16,18,22,30,40,58,60j=3(左部) 五次调用m=1,n=23,4,11,16,18,22,30,40,58,60j=2 六次调用m=1,n=1不变,返回m3,n=2返回m4,n=5 3,4,11,16,18,22,30,40,58,60j=4 七次调用m=4,n=3不变,返回注:一次划分后,左、右两部分调用算两次) 4)最大栈空间用量为0(10gn) 36.在具有n个元素的集合中找第k(1≤k≤n)个最小元素,应使用快速排序方法。其基 本思想如下:设n个元素的集合用一维数组表示,其第一个元素的下标为1,最后一个元素 下标为n。以第一个元素为“枢轴”,经过快速排序的一次划分,找到“枢轴”的位置i,若 ik,则该位置的元素即为所求;若ik,则在1至i-1间继续进行快速排序的划分;若i<k, 则在i+1至n间继续进行快速排序的划分。这种划分一直进行到i为止,第i位置上的元 素就是第k(1≤k≤n)个最小元素 37.快速排序各次调用结果 一次调用:18,36,77,42,23,65,84,10,59,37,61,98 二次调用:10,18,77,42,23,65,84,36,59,37,61,98 三次调用:10,18,61,42,23,65,37,36,59,77,84,98 归并排序各次调用结果: 次调用36,98,42,77,23,65,10,84,37,59,18,61,(子文件长度为1,合并后子文件长 度为2) 二次调用36,42,77,98,10,23,65,84,18,37,59,61(子文件长度为2,合并后子文件长33. 不是。因为当序列已有序时，快速排序将退化成冒泡排序，时间复杂度为 O(n2 )。当待 排序序列无序，使每次划分完成后，枢轴两侧子文件长度相当，此时快速排序性能最好。 34. 初 始 序 列 ： [28],07,39,10,65,14,61,17,50,21 21 移动： 21,07,39,10,65,14,61,17,50,[] 39 移动： 21,07,[],10,65,14,61,17,50,39 17 移动： 21,07,17,10,65,14,61,[],50,39 65 移动： 21,07,17,10,[],14,61,65,50,39 14 移动： 21,07,17,10,14,[28],61,65,50,39 类似本题的另外叙述题的解答： （1）：快速排序思想：首先将待排序记录序列中的所有记录作为当前待排序区域，以第一个 记录的关键字作为枢轴（或支点）（pivot），凡其关键字不大于枢轴的记录均移动至该记录 之前，凡关键字不小于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序 列 R[s..t]将分割成两部分：R[s..i-1]和 R[i+1..t],且 R[j].key≤R[i].key≤R[k].key(s ≤j<i,i<k≤t),然后再递归地将 R[s..i-1]和 R[i+1..t]进行快速排序。快速排序在记录有 序时蜕变为冒泡排序，可用“三者取中”法改善其性能，避免最坏情况的出现。具体排序实 例不再解答。 35．（1）不可以，若 m+1 到 n 之间关键字都大于 m 的关键字时,<=k 可将 j 定位到 m 上，若 为<k 则 j 将定位到 m-1 上，将出界线，会造成错误。 （2）不稳定，例如 2，1，2´，（m=1,n=3）对 2，1，2´排序，完成会变成 1，2´，2。 （3）各次调用 qsort1 的结果如下： 一次调用 m=1,n=10 11,3,16,4,18,22,58,60,40,30 j=6 二次调用 m=7,n=10 11,3,16,4,18,22,40,30,58,60 j=9 (右部) 三次调用 m=10,n=10 不变，返回 m=7,n=8 11,3,16,4,18,22,30,40,58,60 j=8 四次调用 m=9,n=8 不 变 ， 返 回 m=7,n=7 返 回 m=1,n=5 4,3,11,16,18,22,30,40,58,60 j=3（左部） 五次调用 m=1,n=2 3,4,11,16,18,22,30,40,58,60 j=2 六次调用 m=1,n=1 不变，返回 m=3,n=2 返回 m=4,n=5 3,4,11,16,18,22,30,40,58,60 j=4 七次调用 m=4,n=3 不变，返回 （注：一次划分后，左、右两部分调用算两次） （4）最大栈空间用量为 O(logn)。 36. 在具有 n 个元素的集合中找第 k（1≤k≤n）个最小元素，应使用快速排序方法。其基 本思想如下：设 n 个元素的集合用一维数组表示，其第一个元素的下标为 1，最后一个元素 下标为 n。以第一个元素为“枢轴”，经过快速排序的一次划分，找到“枢轴”的位置 i，若 i=k，则该位置的元素即为所求；若 i>k，则在 1 至 i-1 间继续进行快速排序的划分；若 i<k， 则在 i+1 至 n 间继续进行快速排序的划分。这种划分一直进行到 i=k 为止，第 i 位置上的元 素就是第 k（1≤k≤n）个最小元素。 37. 快速排序各次调用结果： 一次调用：18,36,77,42,23,65,84,10,59,37,61,98 二次调用：10,18,77,42,23,65,84,36,59,37,61,98 三次调用：10,18,61,42,23,65,37,36,59,77,84,98 归并排序各次调用结果： 一次调用 36,98,42,77,23,65,10,84,37,59,18,61, (子文件长度为 1，合并后子文件长 度为 2) 二次调用 36,42,77,98,10,23,65,84,18,37,59,61 (子文件长度为 2，合并后子文件长