数据结构基数排序问题设线性表中每个元素有两个数据项k1和k2,现对线性表按一下规则进行排序：先看数据项k1，k1值小的元素在前，大的在后；在k1值相同的情况下，再看k2，k2值小的在前，

Question

数据结构基数排序问题
设线性表中每个元素有两个数据项k1和k2,现对线性表按一下规则进行排序：先看数据项k1，k1值小的元素在前，大的在后；在k1值相同的情况下，再看k2，k2值小的在前，大的在后。满足这种要求的排序方法是（ ）
A.先按k1进行直接插入排序，再按k2进行简单选择排序
B.先按k2进行直接插入排序，再按k1进行简单选择排序
C.先按k1进行简单选择排序，再按k2进行直接插入排序
D.先按k2进行简单选择排序，再按k1进行直接插入排序
B和D请问选择哪一个？请举出反例，自己想不明白啊～谢谢大家了

Answer 1

选D，插入排序是稳定排序，选择排序是不稳定排序。 稳定是指相同的两个元素在排序前后，相对位置不发生改变。因此，由于第一趟对k2进行了排序，所以第二趟对k1排序时必须保证使用稳定排序算法，才能保证排序前后，两个值相等的k1不会发生相对位置颠倒，这样也就不会破坏原来k2的排序。
例如第一趟对k2排好序后，线性表为<1,1><2,1><5,2><2,2><4,4>
选用插入排序保证算法稳定，那么<2,1><2,2> 两组数k1相同，在排序后k2相对顺序不变，结果就正确，如果选用选择排序，由于算法不稳定，可能排序后结果成了<2,2><2,1>