第2节、好朋友手牵手——冒泡排序

1、栗子

计数排序思路简单，运算速度也很快，算法复杂度为O(n)，表现非常优秀，但内存占用太大。
就像班上有10个人，却要占用100人的教室。

很多排序算法可以解决内存占用过多个问题，冒泡排序就是其中出色的一种！

顾名思义，冒泡排序就是让轻的泡泡浮上去或者让重的“泡泡”沉入水底。

轻的浮上去，重的沉下去

从头开始，相邻的两个小伙伴比较体重，重的小伙伴一直往队伍后面排，一直到队伍最后。总共有5个小伙伴，重复4次，就可以按照体重顺序排序了！

2、准备工作

冒泡排序动态图

我们同样使用一个一维数组解决这个问题。

1、对数组进行初始化
2、读入数据
3、冒泡排序
4、输出结果

跟之前的计数排序整体思路一致，有木有？最关键的不同是排序过程，核心算法如下：

    for (i = 0;i<8 - 1;i++)//n个数的数列总共扫描n-1次  
    {
        for (j = 0;j<8 - i - 1;j++)//每一趟扫描到a[n-i-2]与a[n-i-1]比较为止结束  
        {
            if (a[j]>a[j + 1])//后一位数比前一位数小的话，就交换两个数的位置（升序）  
            {
                t = a[j + 1];
                a[j + 1] = a[j];
                a[j] = t;
            }
        }
    }

这里需要注意的有两点：

1、外层循环次数为n-1，而不是n，想一想是为什么？好了，是因为最后只剩下一个数字，压根就不用排序了！
2、内层循环次数为n-1-i，每一次外层循环，最后面的都是当前遍历数组中最大的数字，所以不用再比较了。

第一次冒泡完成
第二次冒泡完成

可以清楚地看到，每次冒泡最后一位都是当前最大的那一个，所以没有必要再比较大小了！

3、代码

这里是完整代码，使用C语言

//输入：6 5 3 1 8 7 2 4
//输出：1 2 3 4 5 6 7 8
#include <stdio.h>  

int main()
{
    int a[9], i, j, t;
    //数组初始化为0
    for (i = 0;i < 8;i++)
        a[i] = 0;

    //读入数据
    for (i = 0;i < 8;i++)
    {
        scanf("%d", &a[i]);
    }

    //冒泡排序  
    for (i = 0;i<8 - 1;i++)//n个数的数列总共扫描n-1次  
    {
        for (j = 0;j<8 - i - 1;j++)//每一趟扫描到a[n-i-2]与a[n-i-1]比较为止结束  
        {
            if (a[j]>a[j + 1])//后一位数比前一位数小的话，就交换两个数的位置（升序）  
            {
                t = a[j + 1];
                a[j + 1] = a[j];
                a[j] = t;
            }
        }
    }


    //输出结果
    for (i = 0;i<8;i++)
    {
        printf("%d ", a[i]);
    }

    //等待输入，避免最终结果一闪而过
    getchar();getchar();
    return 0;
}

4、优化

我们只使用一个数组可以存储所有的数字，内存占用小了很多，但运行的时间似乎长了一些（当然，数据量很小的话，几乎感受不出来）。

计数排序排序的过程中，只需要循环一次就好了，还记得内层循环和外层循环吗？这里要循环两次，时间复杂度变成了O(n^2)。

那么，能不能继续优化呢？当然可以！下一节，我们继续优化。