八排序练习题答案
排序 练习题（八） 参考答案 习题解答 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
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]);
}