八排序 练习题答案

排序 练习题（八） 参考答案

习题解答 2010-06-25 15:15:45 阅读33 评论0 字号：大中小

一、【答案】

在内部排序方法中，选择排序、堆排序、归并排序、基数排序的效率与原始待排序数据的排列顺序基本上无关，而快速排序适合于原始待排序数据完全无序，不适合于数据基本有序的情况。直接插入排序和Shell排序虽然平均效率不高，但当原始待排序数据基本有序时效率较高，考虑到要选择比较和移动次数少的排序方法，可选择直接插入排序或Shell排序。如还需考虑稳定性或简单性，就只能选择直接插入

排序。

二、【答案】

对序列{50，30，60，80，70，20，40}进行冒泡排序时，第一趟排序结果为：

{20，50，30，60，80，70，40} 元素30往它最终位置的相反方向移动了。

快速排序不可能出现这种现象。因为在每一趟排序过程中，以枢轴为基准，比它小的元素往前移，比它大的元素往后移。但可能出现局部的波动现象，比如对序列{50，40，90，10，20，35}进行一趟快速排序的结果为：{35，40，20，10，50，90}，元素35移过了最终位置，在后面某趟排序过程中需要往后

移。

三、【答案】

（1）当步长d=5时，序列变为：

（5，12，20，4，l，30，44，66，31，8，100，80，150，61，200）

（2）当步长d=3时，序列变为：

（4，1，20，4，l2，30，8，61，31，44，66，80，150，100，200）

（3）当步长d=1时，序列变为：

（1，4，5，8，12，20，30，31，44，61，66，80，100，150，200）

四、【解答】

（1）快速排序第一次分割的结果为： {2，0，5，3，4} 6 {8，7，9，10}

（2）建堆及调整的结果，如图所示。

大根堆及选出最大关键字

若以3为基数，则数组A的10个元素依次变为{20，2，30，21，10，22，11，12，0，31}，第一次分配（LSD排序）和收集后的结果为：{20，30，10，0，21，11，31，2，22，12}，即{6，9，3，0，

7，4，10，2，8，5}。

五、【解答】

（1）快速排序第一趟后的状态：{20，38，10} 49 {75，90，66}。 快速排序第二趟后的状态：{10} 20 {38} 49 {75，90，66}。 （2）把关键字集合key调整成堆顶元素取最小值的堆，如图所示。

小根堆

（3） 能用队列代替栈。

使用栈保存子序列首、尾记录的地址（下标），其目的是为了处理某个子序列时，能知道其首、尾记录的地址，这样才能对该子序列进行快速排序。但这与处理子序列的先后没有什么关系，仅起保存作

用。因此，用队列也可起到栈的作用，故可取代。

（4） 归并排序要求的内存容量最多。

六、 【分析】

· 试题主要考核有关快速排序的基本思想，要求熟悉快速排序的主要特点和算法的主要步骤。 · 算法思想：设查找区间是low～high，一趟快速排序后，得到划分位置low，若low=k，则问题解决；若low>k，则在前面的子序列范围内查找；若low

【解答】

int QuickSort_Find(SqList &R, int first, int last, int k)

{

int low=first, high=last; KeyType pivotKey; R.r[0] = R.r[first]; pivotKey = R.r[first].key; while(low < high){

while(low=pivotKey)

high--; R.r[low] = R.r[high];

while(low

low++; R.r[high] = R.r[low];

}

R.r[low] = R.r[0]; if(low-first+1 == k) return low; else if(low-first+1 > k)

return QuickSort_Find(R, first, low-1, k);

else

return QuickSort_Find(R, low+1, last,k-low+first-1);

}

void FindValue(SqList &R, int k)

{ int location;

location = QuickSort_Find(R, 1, R.length, k);

printf(R.r[location]);

}