课本P16关于冒泡排序:
void bubble_sort(int a[ ], int n){
//将a中整数序列重新排序成自小至大有序的整数序列
for(i = n - 1, change = TRUE; i > 1 && change; --i){ //应为i > 0
change = FALSE;
for(j = 0; j < i; ++j)
if(a[j] < a[j + 1]){ a[j] 互换 a[j + 1]; change = TRUE }
}
}//bubble_sort
我是在计算语句频度的时候发现的:
2 + 3 + 4 +..... + (n-1) = (n+1)(n-2)/2,与课本结果不一致
上机测试(注意:测试数组中的数为逆序),结果:第一个数比第二个数大
应该改为i > 0:
1 + 2 + 3 +.....+ (n-1),利用等差数列公式计算后得到:n(n-1)/2
(在 1 + 2 + 3 + .....+ (n-1)最前面加0便于利用公式计算)
附:时间复杂度的计算方法:
for(i = 0 ; i < n; i++)
for(j = 0; j < n; j++)
x++;
基本操作为:x++;它执行的次数(语句频度)为:n个n相加的和,即n + n + .... + n = n*n