单选题
采用简单选择排序,比较次数与移动次数分别为______。
A、
O(n),O(log
2
n)
B、
O(log
2
n),O(n
2
)
C、
O(n
2
),O(n)
D、
O(nlog
2
),O(n)
【正确答案】
C
【答案解析】
简单选择排序的关键字比较次数KCN与对象的初始排列无关。第i趟选择具有最小关键字对象所需的比较次数总是n-i-1次(此处假定整个待排序对象序列有n个对象)。因此,总的关键字比较次数为:
[*]
最坏情况是每一趟都要进行交换,总的对象移动次数为RMN=3(n-1)。
提交答案
关闭