<谭> 例7.3
用起泡法对10个数排序(由小到大)
若有n个数。第一次将第1和第2个数比较，若第1个数大于第2个数，刚两数对调，否则不操作。第二次将第2和第3个数比较，如上操作，刚经过n-1次这样的操作，最大的数排到了最后（即所谓的沉底）。以上为第一趟操作的结果。第二趟要对余下的n-1个数作同样的操作（因为最大的数已排到最后，不必考虑）。第二趟中要作n-2次比较……依次类推可得出结论：n个数排序，要进行n-1趟比较。第一趟中比较n-1次，第 i 趟中比较 n-i 次。
#include <stdio.h>
int main()
{
int a[11]; /* 为了符合习惯, 第0号元素不用 */
int i, j, cup;
printf("Input 10 numbers:\n");
for(i = 1; i < 11; i++)
scanf("%d", &a[i]);
for(i = 1; i <= 9; i++) /* 趟数 */
for(j = 1; j <= 10 - i; j++) /* 每趟要比较数 */
if(a[j] > a[j+1]) /* 前面数大于后面数刚对调 */
{
cup = a[j];
a[j] = a[j+1];
a[j+1] = cup;
}
printf("The sorted numbers:\n");
for(i = 1; i <11; i++)
printf("%d ", a[i]);
return 0;
}
运行结果:
=============================================
Input 10 numbers:
4 23 68 -29 9 10 -500 799 88 -4↙
The sorted numbers:
-500 -29 -4 4 9 10 23 68 88 799
=============================================
★ 其执行过程分析:
第1趟:
第1次: 4 23 68 -29 9 10 -500 799 88 -4
第2次: 4 23 68 -29 9 10 -500 799 88 -4
第3次: 4 23 -29 68 9 10 -500 799 88 -4
第4次: 4 23 -29 9 68 10 -500 799 88 -4
第5次: 4 23 -29 9 10 68 -500 799 88 -4
第6次: 4 23 -29 9 10 -500 68 799 88 -4
第7次: 4 23 -29 9 10 -500 68 799 88 -4
第8次: 4 23 -29 9 10 -500 68 88 799 -4
第9次: 4 23 -29 9 10 -500 68 88 -4 799
第2趟:
第1次: 4 23 9 -29 -500 10 68 -4 88 799
第2次: 4 23 -29 9 10 -500 68 88 -4 799
第3次: 4 23 9 -29 10 -500 68 88 -4 799
第4次: 4 23 9 -29 10 -500 68 88 -4 799
第5次: 4 23 9 -29 -500 10 68 88 -4 799
第6次: 4 23 9 -29 -500 10 68 88 -4 799
第7次: 4 23 9 -29 -500 10 68 88 -4 799
第8次: 4 23 9 -29 -500 10 68 -4 88 799
……
第9趟:
第1次: -500 -29 -4 4 9 10 23 68 88 799
★ 为验证以上推论,改写程序如下:
#include <stdio.h>
int main()
{
int a[11];
int i, j, k, cup;
printf("Input 10 numbers:\n");
for(i = 1; i < 11; i++)
scanf("%d", &a[i]);
for(i = 1; i <= 9; i++)
{
printf("i=%d: \n\n", i);
for(j = 1; j <= 10 - i; j++)
{
if(a[j] > a[j+1])
{
cup = a[j];
a[j] = a[j+1];
a[j+1] = cup;
}
printf(" j=%d: ", j);
for(k = 1; k < 11; k++)
printf("%5d ", a[k]);
printf("\n");
}
printf("\n\n");
}
return 0;
}
运行结果:
=========================================================================
Input 10 numbers:
4 23 68 -29 9 10 -500 799 88 -4↙
i=1:
j=1: 4 23 68 -29 9 10 -500 799 88 -4
j=2: 4 23 68 -29 9 10 -500 799 88 -4
j=3: 4 23 -29 68 9 10 -500 799 88 -4
j=4: 4 23 -29 9 68 10 -500 799 88 -4
j=5: 4 23 -29 9 10 68 -500 799 88 -4
j=6: 4 23 -29 9 10 -500 68 799 88 -4
j=7: 4 23 -29 9 10 -500 68 799 88 -4
j=8: 4 23 -29 9 10 -500 68 88 799 -4
j=9: 4 23 -29 9 10 -500 68 88 -4 799
i=2:
j=1: 4 23 -29 9 10 -500 68 88 -4 799
j=2: 4 -29 23 9 10 -500 68 88 -4 799
j=3: 4 -29 9 23 10 -500 68 88 -4 799
j=4: 4 -29 9 10 23 -500 68 88 -4 799
j=5: 4 -29 9 10 -500 23 68 88 -4 799
j=6: 4 -29 9 10 -500 23 68 88 -4 799
j=7: 4 -29 9 10 -500 23 68 88 -4 799
j=8: 4 -29 9 10 -500 23 68 -4 88 799
i=3:
j=1: -29 4 9 10 -500 23 68 -4 88 799
j=2: -29 4 9 10 -500 23 68 -4 88 799
j=3: -29 4 9 10 -500 23 68 -4 88 799
j=4: -29 4 9 -500 10 23 68 -4 88 799
j=5: -29 4 9 -500 10 23 68 -4 88 799
j=6: -29 4 9 -500 10 23 68 -4 88 799
j=7: -29 4 9 -500 10 23 -4 68 88 799
i=4:
j=1: -29 4 9 -500 10 23 -4 68 88 799
j=2: -29 4 9 -500 10 23 -4 68 88 799
j=3: -29 4 -500 9 10 23 -4 68 88 799
j=4: -29 4 -500 9 10 23 -4 68 88 799
j=5: -29 4 -500 9 10 23 -4 68 88 799
j=6: -29 4 -500 9 10 -4 23 68 88 799
i=5:
j=1: -29 4 -500 9 10 -4 23 68 88 799
j=2: -29 -500 4 9 10 -4 23 68 88 799
j=3: -29 -500 4 9 10 -4 23 68 88 799
j=4: -29 -500 4 9 10 -4 23 68 88 799
j=5: -29 -500 4 9 -4 10 23 68 88 799
i=6:
j=1: -500 -29 4 9 -4 10 23 68 88 799
j=2: -500 -29 4 9 -4 10 23 68 88 799
j=3: -500 -29 4 9 -4 10 23 68 88 799
j=4: -500 -29 4 -4 9 10 23 68 88 799
i=7:
j=1: -500 -29 4 -4 9 10 23 68 88 799
j=2: -500 -29 4 -4 9 10 23 68 88 799
j=3: -500 -29 -4 4 9 10 23 68 88 799
i=8:
j=1: -500 -29 -4 4 9 10 23 68 88 799
j=2: -500 -29 -4 4 9 10 23 68 88 799
i=9:
j=1: -500 -29 -4 4 9 10 23 68 88 799
=========================================================================
★ 可见对于该组数据实际上在i=7, j=3 时已经得到最终结果。
评论