设线性表中每个元素有两个数据项 k1 和 k2，现对线性表按以下规则进行排序：先看数据项 k1，k1 值小的元素在前，大的在后；在 k1 值相同的情况下，再看 k2，k2 值小的在前，大的在后。满足这种要求的排序方法是（ ）。

A. 先按 k1 进行直接插入排序，再按 k2 进行简单选择排序 B. 先按 k2 进行直接插入排序，再按 k1 进行简单选择排序 C. 先按 k1 进行简单选择排序，再按 k2 进行直接插入排序 D. 先按 k2 进行直接选择排序，再按 k1 进行直接插入排序

插入排序

[tag_link]

正确答案：D

该排序要求为先按k1排序，k1相同时再按k2排序，属于多关键字排序。

为实现此类排序，通常需先按次要关键字（k2）排序，再按主要关键字（k1）进行稳定排序，从而在k1相同的情况下保持k2的顺序。

分析各选项：A先按k1进行直接插入排序（稳定），再按k2进行简单选择排序（不稳定），第二次不稳定排序可能破坏已排好的k1顺序，不满足要求； B先按k2进行直接插入排序（稳定），再按k1进行简单选择排序（不稳定），第二次不稳定排序可能打乱k1相同时的k2顺序，不符合要求； C先按k1进行简单选择排序（不稳定），再按k2进行直接插入排序（稳定），第一次不稳定排序导致k1顺序混乱，第二次稳定排序按k2进行，最终序列主要按k2排序，而非先k1后k2，同样不满足； D先按k2进行直接选择排序（不稳定），再按k1进行直接插入排序（稳定），第一次按k2排序后序列整体k2有序，第二次稳定排序按k1进行，能保证k1有序的同时，对k1相同的元素保持第一次排序后的k2顺序，从而实现先k1后k2的排序要求，故D正确。