●下面算法是实现对n个整数的序列进行选择排序,其中序列的"长度"n为问题的规模。该算法的时间复杂

Question

●下面算法是实现对n个整数的序列进行选择排序，其中序列的"长度"n为问题的规模。该算法的时间复杂度为 (23) 。

void select_sort(int a[]，int n)

{

//将a中整数序列重新排列成从小到大有序的整数序列

for(i=0；i<n-1；++i){

j=i；

for(k=i+1；k<n；++k)

if(a[k]<a[j])j=k；

if(j!=i){w=a[j]；a[j]=a[i]；a[i]=w；}

}//select- sort

(23) A．O(n3)

B．O(n2)

C．O(n)

D．O(n4)

Answer 1

正确答案：B

【解析】算法中的控制结构是两重循环，所以基本操作是在内层循环中的"比较"，它的重复执行次数是：

 
对时间复杂度而言，只需要取最高项，并忽略常数系数。