题11

题11

题目

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

分析

A:我选到了C选项
因为是比K1小的在前，所以应该先对K1进行排序，选小这个行为我记得是简单选择排序
而K1相同，看K2，也就是K2形成了基准，其他的来往前或者往后，这就是插入排序

解

D

• 本题思路来自基数排序的 LSD
• 首先应确定 的排序顺序
• 若先排 再排 ,则排序结果不符合题意
  • 排除 和
• 再考虑排序的稳定性
  • 当 排好序后,再对 排序
  • 若对 排序采用的方法是不稳定的,则对于 相同而 不同的元素可能会改变相对次序
  • 从而不一定能满足题设要求
• 直接插入排序是稳定的, 而简单选择排序是不稳定的
• 只能选 D