冒泡排序C++实现

算法描述：

从数组开头开始向后遍历，如果a[i]>a[i+1]则交换两个，重复做，直到没有交换的数对。

下面给出整数数组的两种实现，一种是单方向的冒泡（即将大的数字向后交换），第二种是冒泡和下沉交替进行（即一次大数字向后移动，一次小数字向前移动），并比较两个实现的运行时间：

第一种：

#include <iostream>
#include <math.h>
using namespace std;
const int Num=2000;
void exch(int* s,int a,int b)
{
        int mid=s[a];
        s[a]=s[b];
        s[b]=mid;
}
int main()
{
int array[Num];
int flag=1;//记录一趟最后交换的下标
int mod=0;
srand(3);//初始化随机数
for(int i=0;i<Num;i++)//初始化数组0到10000之间
{
        array[i]=rand() % 10001;
}
for(int i=0;i<Num;i++)//输出原数组
{
        printf("%d ",array[i]);
}
while(flag)//冒泡排序
{
        flag=0;
        for(int j=0;j<Num-1;j++)
                {
                        if(array[j]>array[j+1])
                                {
                                        exch(array,j,j+1);
                                        flag=j;
                                }
                }
        /*if(mod%2==0)
        {
             for(int j=0;j<Num-1;j++)
                {
                        if(array[j]>array[j+1])
                                {
                                        exch(array,j,j+1);
                                        flag=j;
                                }
                }
                mod++;
        }
        else
        {
             for(int j=Num-1;j>0;j--)
                {
                        if(array[j]<array[j-1])
                                {
                                        exch(array,j,j-1);
                                        flag=j;
                                }
                }
                mod++;
        }*/

}
printf("\n");
for(int i=0;i<Num;i++)
{
        printf("%d ",array[i]);
}
    return 0;
}

第二种：

#include <iostream>
#include <math.h>
using namespace std;
const int Num=2000;
void exch(int* s,int a,int b)
{
        int mid=s[a];
        s[a]=s[b];
        s[b]=mid;
}
int main()
{
int array[Num];
int flag=1;//记录一趟最后交换的下标
int mod=0;
srand(3);//初始化随机数
for(int i=0;i<Num;i++)//初始化数组0到10000之间
{
        array[i]=rand() % 10001;
}
for(int i=0;i<Num;i++)//输出原数组
{
        printf("%d ",array[i]);
}
while(flag)//冒泡排序
{
        flag=0;
        /*for(int j=0;j<Num-1;j++)
                {
                        if(array[j]>array[j+1])
                                {
                                        exch(array,j,j+1);
                                        flag=j;
                                }
                }*/
        if(mod%2==0)
        {
             for(int j=0;j<Num-1;j++)
                {
                        if(array[j]>array[j+1])
                                {
                                        exch(array,j,j+1);
                                        flag=j;
                                }
                }
                mod++;
        }
        else
        {
             for(int j=Num-1;j>0;j--)
                {
                        if(array[j]<array[j-1])
                                {
                                        exch(array,j,j-1);
                                        flag=j;
                                }
                }
                mod++;
        }

}
printf("\n");
for(int i=0;i<Num;i++)
{
        printf("%d ",array[i]);
}
    return 0;
}

一般情况下交替进行冒泡排序要优于单方向的冒泡。

对于长度为N的数组，最好情况下比较N-1次，交换0次；最坏情况下比较N(N-1)/2次，交换N(N-1)/2次。

冒泡排序C++实现

原文：http://blog.csdn.net/u014594922/article/details/51353835