Q4-数据结构
题目
(摘自王道考研数据结构8.4.3习题第三题)
设线性表中每个元素有两个数据项k1和k2,现对线性表按一下规则进行排序：先看数据项k1，k1值小的元素在前，大的在后；在k1值相同的情况下，再看k2，k2值小的在前，大的在后。满足这种要求的排序方法是（ ）
A.先按k1进行直接插入排序，再按k2进行简单选择排序
B.先按k2进行直接插入排序，再按k1进行简单选择排序
C.先按k1进行简单选择排序，再按k2进行直接插入排序
D.先按k2进行简单选择排序，再按k1进行直接插入排序
分析
首先我们要明确题意，这一题的排序是针对k1和k2全体进行的，而不是说我排好k1后，再对每组相同的k1进行k2的排序。
另外特别注意“在k1值相同的情况下，再看k2”这句话。这说明k1排序的优先级要比k2高，如果我们对k1先进行排序，后面对k2进行排序时就会打乱之前k1的排序。所以排序顺序是k2、k1。
接着讨论要用的算法，题中没有给什么特殊的要求，所以我们要满足的只是“数据项k1，k1值小的元素在前，大的在后；在k1值相同的情况下，再看k2，k2值小的在前，大的在后”。而通过以上分析我们知道k2先排序。接着来考虑k1的排序，因为k1的排序优先级要高于k2，所以k1的排序可能会打乱k2已经排好的顺序，这样就不能保证“在k1值相同的情况下，再看k2，k2值小的在前，大的在后”了，所以必须要求k1排序是有序的。
e.g.
k1 选择排序之前
| 标识 | k1 | k2 |
|---|---|---|
| 1 | 50 | 70 |
| 2 | 40 | 70 |
| 3 | 50 | 80 |
| 4 | 40 | 80 |
k1 选择排序之后
| 标识 | k1 | k2 |
|---|---|---|
| 1 | 40 | 70 |
| 2 | 40 | 80 |
| 3 | 50 | 80 |
| 4 | 50 | 70 |
如上表所示，我们发现如果k1排序不稳定，那么对于相同的k1，可能k2不满足“在k1值相同的情况下，再看k2，k2值小的在前，大的在后”。所以k1的排序算法必须稳定。
综上，我们要选一个排序顺序为k2、k1，且k1排序算法要稳定的选项，所以答案为D。
王道解析
本题思路来自基数排序的LSD，首先应确定k1、k2的排序顺序，若先排k1再排k2，则排序结果不符合题意，排除A和C。再考虑算法的稳定性，当k2排好序后，再对k1排序，若对k1排序采用的算法是不稳定的，则对于k1相同而k2不同的元素可能会改变相对次序，从而不 一定能满足题设要求。直接插入排序算法是稳定的，而简单选择排序算法是不稳定的，故只能选D。