冒泡排序C++实现

算法描述：

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

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

第一种：

#include

#include

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;iarray[j+1])

{

exch(array,j,j+1);

flag=j;

}

}

/*if(mod%2==0)

{

for(int j=0;jarray[j+1])

{

exch(array,j,j+1);

flag=j;

}

}

mod++;

}

else

{

for(int j=Num-1;j>0;j--)

{

if(array[j]

第二种：#include

#include

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;iarray[j+1])

{

exch(array,j,j+1);

flag=j;

}

}*/

if(mod%2==0)

{

for(int j=0;jarray[j+1])

{

exch(array,j,j+1);

flag=j;

}

}

mod++;

}

else

{

for(int j=Num-1;j>0;j--)

{

if(array[j]

一般情况下交替进行冒泡排序要优于单方向的冒泡。对于长度为N的数组，最好情况下比较N-1次，交换0次;最坏情况下比较N(N-1)/2次，交换N(N-1)/2次。