试题出自试卷《程序员每日五题10.17》

问题1选项
A.冒泡排序法中，元素的交换次数与元素的比较次数一定相同
B.冒泡排序法中，元素的交换次数不少于元素的比较次数
C.简单选择排序中，关键字相同的两个记录在排序前后的相对位置一定不变
D.简单选择排序中，关键字相同的两个记录在排序前后的相对位置可能交换

D

    本题考查算法方面的基础知识。     冒泡排序法的基本思路是：将相邻位置的关键字进行比较，若为逆序则交换之。重复该过程，直到序列已排好序。显然，在这个过程中，元素间的比较次数应大于等于交换次数。     简单选择排序的思路是：第一趟在n个记录中选取最小记录，将其与序列的第一个元素交换，第二趟在n-1个记录中选取最小记录，将其与序列的第二个元素交换，第i趟在n-i+1个记录中选取最小的记录，将其与序列的第i个元素交换，直到序列的第n个元素为止。在这个过程中，关键字相同的两个记录在排序前后的相对位置可能发生变化。例如，序列为（30，30，12）时，选择排序法需要将第一个元素30与最后一个元素12进行交换，这样就使得两个30的相对位置改变了。