原:排序算法:冒泡排序
作者 斯人 | 发布于 2012 年 2 月 23 日

在排序算法里面,冒泡排序是非常常见的一种算法 它的时间复杂度为 O(N^2)
冒泡排序的概念:
依次比较相邻的两个数,小的放前面,大的放后面

 *
/*
 * =====================================================================================
 *
 *       Filename:  bubble.cpp
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  02/23/12 00:32:55
 *       Revision:  none
 *       Compiler:  g++
 *
 *         Author:  SiRen (), siren_0203@163.com
 *           Blog:  imsiren.com   
 *
 * =====================================================================================
 */
#include <stdio.h>
int data[10]={80,30,10,20,40,30,90,70,100,60};
int *bubble(int *data,int len){
        int o=0,i=0;
        int n,tmp;
        for(o=len-1;o>=0;o--){
                for(n=0;n<o;n++){
                        tmp=data[n];    
                        if(tmp>data[n+1]){
                                data[n]=data[n+1];
                                data[n+1]=tmp;
                        }   
                }   
        }   
        printf("bubbled:\n");
        for(int i=0;i<len-1;i++)
                printf("%d\n",data[i]);
}
int main(int argc,char *argv[]){
    
        bubble(data,10);
        return 0;
}


输出结果
10
20
30
30
40
60
70
80
90
那么怎么优化一下???
我们想象一下,在第一次外层循环的时候,内层循环会从第0个依次比较到第8个数也就是从80到100依次比较,
那么如果内循环比较完之后 没有交换数据..是不是就证明数据已经是排好序的???这样就能减少循环次数,提高排序速度.
如果有交换数据 那就证明数据还不是完全排好后的数据..
看下代码

 *
/*
 * =====================================================================================
 *
 *       Filename:  bubble.cpp
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  02/23/12 00:32:55
 *       Revision:  none
 *       Compiler:  g++
 *
 *         Author:  SiRen (), siren_0203@163.com
 *           Blog:  imsiren.com   
 *
 * =====================================================================================
 */
#include <stdio.h>
int data[10]={80,30,10,20,40,30,90,70,100,60};
int *bubble(int *data,int len){
        int o=0,i=0;
        int n,tmp;
        int flag=1;
        for(o=len-1;o>=0 && flag;o--){
                flag=0;//先初始化为0
                for(n=0;n<o;n++){
                        tmp=data[n];    
                        if(tmp>data[n+1]){
                                data[n]=data[n+1];
                                data[n+1]=tmp;
                                //标记已交换
                                flag=1;
                        }   
                }   
        }   
        printf("bubbled:\n");
        for(int i=0;i<len-1;i++)
                printf("%d\n",data[i]);
}
int main(int argc,char *argv[]){
    
        bubble(data,10);
        return 0;
}
原文出处:http://www.imsiren.com/archives/237