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

admin2018-07-17 78

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

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

答案D

解析考查基数排序的特性、排序算法的稳定性。本题思路来自基数排序的LSD，首先应确定k1，k2的排序顺序，若先排k1再排k2，则排序结果不符合题意，排除AC。再考虑算法的稳定性，当k2排好序后，再对k1排序，若对k1排序采用的算法是不稳定的，则对于k1相同、而k2不同的元素可能会改变相对次序，从而不一定能满足题设要求。直接插入排序算法是稳定的，而简单选择排序算法是不稳定的。
注意：大部分的简单排序方法都是稳定的，除了简单选择排序，复杂的排序方法通常都是不稳定的。不稳定的排序方法有：简单选择排序、希尔排序、快速排序和堆排序。平均时间复杂度为O(nlog₂n)的稳定排序算法只有归并排序。对于不稳定的排序方法，只要举出一个不稳定的实例即可。

转载请注明原文地址:https://kaotiyun.com/show/cyRi777K

本试题收录于：计算机408题库学硕统考专业分类

0

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)