问题 单项选择题

以下关于排序算法的叙述中,正确的是()

A.冒泡排序法中,元素的交换次数与元素的比较次数一定相同

B.冒泡排序法中,元素的交换次数不少于元素的比较次数

C.简单选择排序中,关键字相同的记录在排序前后的相对位置一定不变

D.简单选择排序中,关键字相同的记录在排序前后的相对位置可能交换

答案

参考答案:D

解析:

本题考查算法方面的基础知识。

冒泡排序法的基本思路是:将相邻位置的关键字进行比较,若为逆序则交换之。重复该过程,直到序列已排好序。显然,在这个过程中,元素间的比较次数应大于等于交换次数。

简单选择排序的思路是:第一趟在n个记录中选取最小记录,将其与序列的第一个元素交换,第二趟在n-1个记录中选取最小记录,将其与序列的第二个元素交换,第i趟在n-i+1个记录中选取最小的记录,将其与序列的第i个元素交换,直到序列的第n个元素为止。在这个过程中,关键字相同的两个记录在排序前后的相对位置可能发生变化。例如,序列为(30,30,12)时,选择排序法需要将第一个元素30与最后一个元素12进行交换,这样就使得两个30的相对位置改变了。

单项选择题 A1/A2型题
单项选择题