数据结构考研分类复习真题 第十章 答案[16]

初始序列[] 移动[]

移动[] 移动[]

移动[] 移动[]

类似本题的另外叙述题的解答

()快速排序思想首先将待排序记录序列中的所有记录作为当前待排序区域以第一个记录的关键字作为枢轴(或支点)(pivot)凡其关键字不大于枢轴的记录均移动至该记录之前凡关键字不小于枢轴的记录均移动至该记录之后致使一趟排序之后记录的无序序列R[st]将分割成两部分R[si]和R[i+t]且R[j]key≤R[i]key≤R[k]key(s≤j<ii<k≤t)然后再递归地将R[si]和R[i+t]进行快速排序快速排序在记录有序时蜕变为冒泡排序可用三者取中法改善其性能避免最坏情况的出现具体排序实例不再解答

．()不可以若m+到n之间关键字都大于m的关键字时<=k可将j定位到m上若为<k则j将定位到m上将出界线会造成错误

()不稳定例如´(m=n=)对´排序完成会变成´

()各次调用qsort的结果如下

一次调用m=n= j=

二次调用m=n= j= (右部)

三次调用m=n= 不变返回 m=n= j=

四次调用m=n= 不变返回 m=n= 返回 m=n= j=(左部)

五次调用m=n= j=

六次调用m=n= 不变返回 m=n= 返回m=n= j=

七次调用m=n= 不变返回 (注一次划分后左右两部分调用算两次)

()最大栈空间用量为O(logn)

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []