如下一段代码对一个数组做原地桶排序，请大家帮忙分析下其算法复杂度是O（N）还是O（N2）？内层while循环的算法复杂度如何分析？
#include <iostream>
using namespace std;
int main(){
int a[10] = {3,2,4,9,6,1,0,8,7,-1};
int temp;
int temp_val;
for(int i = 0; i < 10; i++){
if(a[i] != i){
temp_val = temp = a[a[i]];//临时变量先存储需要更换的值
a[a[i]] = a[i];
a[i] = temp;
}
while(a[temp_val] != temp_val){
temp = a[temp_val];
a[temp_val] = temp_val;
temp_val = temp;
if(temp_val == -1) break;
}
}
for(int j = 0; j < 10; j++){
cout<<a[j]<<endl;
if(a[j] != j) cout<<"the miss number is"<<j<<endl;
}
return 0;
} |
楼主
标题置顶
标题高亮
