现在的位置: 首页 > 13 数据结构入门 > 正文

冒泡排序

2013年11月27日 ⁄ 13 数据结构入门 ⁄ 共 213字 ⁄ 字号 小 中 大 ⁄ 冒泡排序已关闭评论

冒泡排序是最基本的排序方法，简单易懂。

冒泡排序流程展示PPT 冒泡排序

冒泡排序流程展示

完成一轮冒泡，6个数共需要比较5次， 所以循环变量 j 的变化范围是 0~4。按照由小到大来排序，如果大数在前，就要交换到后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <stdio.h>
int main()
{
    int a[6]= { 9,8,5,4,2,0 };
    int j, t;
    for ( j=0;  j<5;  j++)
        if (a[j]>a[j+1]) {                         /* 如果大数在前，要交换两个数 */
            t=a[j];  a[j]=a[j+1];  a[j+1]=t;
        }
    for (j=0; j<6; j++)
      printf("%4d", a[j]);
    printf("\n");
    return 0;
}

执行完程序后， a[5]一定是保存的是最大的数。 所以a[5]不需要参与以后的排序。

为了让程序更具通用性， 将上面的代码稍稍改变一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <stdio.h>
int main()
{
    int a[6]= {9,8,5,4,2,0};
    int i, j, t, n=6;
    i=n-1;
    /* 排序开始 */
    for(j=0; j<i; j++)
        if (a[j]>a[j+1]) {
            t=a[j];  a[j]=a[j+1]; a[j+1]=t;
        }
    for (j=0; j<n; j++)
      printf("%4d", a[j]);
    printf("\n");
    /* 输出中间结果，排序结束 */
    return 0;
}

当 i =n-1 时， 执行上面的程序，完成了一轮冒泡排序，使得 a[n-1] 成为最大的一个数， 只需要再对前面的 0..n-2个数进行排序。

当 i 的变化范围从 n-1 一直递减到 1时， 就剩下 a[0] 需要排序。 一个数还需要排序吗？ 当然不需要了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <stdio.h>
int main()
{
    int a[6]= {9,8,5,4,2,0};
    int i, j, t, n=6;
    for (i=n-1; i>0; i--) {
        for(j=0; j<i; j++)
            if (a[j]>a[j+1]) {
                t=a[j]; a[j]=a[j+1]; a[j+1]=t;
            }
        for (j=0; j<n; j++)
            printf("%4d", a[j]);
        printf("\n");
    }
    return 0;
}

内层循环中的代码是从上个程序中原封不动的搬过来的哦。

把数组初始化和输出中间结果的代码去掉， 核心代码如下：

1
2
3
4

    for (i=n-1; i>0; i--) {
        for(j=0; j<i; j++)
            if (a[j]>a[j+1]) 交换a[j]和a[j+1]; 
    }

这个程序中值得注意的是如何交换两个变量的值。
如果要交换变量a和b的值，可以用中间变量t作为过渡。这是非常经典的用法。

t = a; a = b; b = t;

通常每个语句一行。 但这里为了是代码看着更为紧凑，将关系非常密切的3个语句写成一行。

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2011-2014 新思维：C语言程序设计  保留所有权利.   Theme by Robin