有意思的算法（一）----冒泡排序

冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把他们交换过来。

下面举一个具体的例子来介绍一下冒泡排序。

这里写图片描述

有12，35，99，18，76五个数进行从大到小的排序，既然是从大到小排序，也就是说越小的越靠后，可不要把这句当成废话，这可是最关键的地方！

首先比较第1位和第2位的数字，第1位是12，第2位是35，12<35，根据越小的越靠后的原则，交换两个数，交换之后的顺序是：35，12，99，18，76。

按照刚才的说法，依次比较第2位和第3位，第3位和第4位，第4位和第5位，结果分别如下：

12，35，99，18，76 35，12，99，18，76 35，99，12，18，76 35，99，18，12，76 35，99，18，76，12

经过4次比较，最小的一个数已经就位了（注意12的移动过程），很有意思，咱们这么来看12的移动过程，看了下面的图片你就会更明白：

这里写图片描述

整个过程就如同是一个气泡，一步一步往后“翻滚”，直到最后一位，所以这个排序有一个很好听的名字“冒泡排序”。

可以这么说，我们的排序只将5个书中最小的一个归位了，没将一个数归位我们称其为“一趟”

下面接着上面的“第一趟”，开始“第二趟”，在第二趟中有一点需要注意的是，由于最小的一位已经归位了，我们只需要找出第二小的数来就可以了，也就是说在本趟中，只需比较到第3位和第4位就可以了，第5位已经是最小的了，就不需要比较了。

“第三趟”的结果是：

99，76，35，18，12

到了最后一趟“第四趟”。有的人就要问了，这还用比较么，这结果不已经出来了么？当然，这里纯属巧合，要是用别的数试一试可能就不是了。

冒泡排序的原理：每一趟只能确定将一个数归位。即第一趟只能将第末位（第5位）上的数归位，第二趟只能将倒数第2位上的数（第4位）归位，第三趟只能将倒数第3位上的数（第3位）归位，可是现在前面还有两个位置上的数没有归位，所以依然要进行“第四趟”

下面咱们总结一下：如果有n个数进行排序，只需将n-1个数归位，也就是说要进行n-1趟操作。而“每一趟”都需要从第一位开始进行相邻的两个数的比较，将较小的一个数放在后面，比较完毕后诺以为继续比较下面两个相邻数的大小，重复此步骤，知道最后一个尚未归位的数，已经归位的书就不需要在进行比较了。

下面是具体的实现代码：

#include <stdio.h>
int main()
{
    int a[100],i,j,t,n;
    scanf("%d",&n);  '''输入一个数n,表示接下来又n个数'''
    for(i=1;i<=n;i++)  '''循环读入n个数到数组a中'''
        scanf("%d",&a[i]);

    '''冒泡排序的核心部分'''
    for(i=1;i<=n-1;i++)    '''n个数排序，只用进行n-1趟'''
    {
        for(j=1;j<=n-i;j++)  '''从第1位开始比较知道最有一个尚未归位的数，想一想为什么到n-i就可以了'''
        {
            if(a[j]<a[j+1])   '''比较两个数的大小'''
            {t=a[j];a[j]=a[j+i];a[j+i]=t;}
        }
    }

    for(i=1;i<=n;i++)  '''输出结果'''
        printf("%d ",a[i]);

    getchar();getchar();
    return 0;
}

冒泡排序的核心部分是双重嵌套循环。不难看出冒泡排序的时间复杂度是O(N2)O(N^2)。

转载请注明出处：http://blog.csdn.net/zlts000/article/details/49515505