王道数据结构:设线性表中每个元素有两个数据项k1和k2,现对线性表按一下规则进行排序:先看数据项k1,k1值小的元素在前,大的在后

发布时间 2023-09-17 11:43:18作者: as阿水

题目:
设线性表中每个元素有两个数据项k1和k2,现对线性表按一下规则进行排序:先看数据项k1,k1值小的元素在前,大的在后;在k1值相同的情况下,再看k2,k2值小的在前,大的在后。满足这种要求的排序方法是( )
A.先按k1进行直接插入排序,再按k2进行简单选择排序
B.先按k2进行直接插入排序,再按k1进行简单选择排序
C.先按k1进行简单选择排序,再按k2进行直接插入排序
D.先按k2进行简单选择排序,再按k1进行直接插入排序

答案:D

 

分析:

1.首先要明确的是:对k1、k2都要进行排序,这种排序类似结构体排序,例如:学生有学号、成绩,成绩不同时按成绩排序,成绩相同时按学号排序。

2.然后需要明确的是先排k1还是k2。根据题目描述“在k1值相同的情况下,再看k2”,也就是说明k1的  重要性/优先级  比k2高,也就是不能因为k2的排序结果改变了k1。如果先排k1再排k2,有可能会改变k1的顺序,那么就要先排k2再排k1

可以将k1、k2看作基数排序的十位数和个位数,在十位相同的情况下需要比对个位数。

例如序列为:{10,15,20,25}。

a.如果先按k1排序得到{10,15,20,25},再按k2排序得到{10,20,15,25},如果k2是不稳定的算法还可能得到{20,10,25,15}。所以先k1再k2,得不到目标的排序结果。

b.如果先按k2排序得到{10,20,15,25},再按k1排序得到{10,15,20,25},如果k2是不稳定的算法还可能得到{15,10,25,20}。所以先k2再k1,而且要求k1必须是稳定的算法。所以D