试题五(15分,C 语言程序设计)
阅读下列说明和 C 代码,回答问题 1 至问题 3。
【说明】下面代码实现冒泡排序,对整型数组从小到大排序。
void BubbleSort(int arr[],int n){
int i,j,flag;
for(i=0;i < n-1;i++){
flag=0;
for(j=0;j < n-1-i;j++){
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag=1;
}
}
if(flag==0) break;
}
}
【问题2】(5分)简述冒泡排序最好、最坏时间复杂度。
参考答案最好情况(已有序):O (n);最坏情况(逆序):O (n²) 空间复杂度:O (1)
解析:最好情况仅一轮扫描,flag=0 直接退出;最坏需要 n-1 轮完整遍历。