三种冒泡排序
冒泡排序的定义：
设数组长度为N。
1)比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换；
2)这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置，N=N-1；
3)如果N不为0就重复前面二步，否则排序完成。
1.最简单的按照定义的冒泡排序
void BubbleSort1(int a[],int n)
{
for(int i=n;i>0;i--)
{
for(int j=1;j<i;j++)
{
if(a[j-1]>a[j])
{
swap(a[j-1],a[j]);
}
}
}
}
2.优化过的冒泡排序，我们一般说的应该是这个冒泡排序。因为这个比上面的时间复杂度要好，因为很有可能几轮之后就已经是全排好了的，这时后面的循环都是不必要的，所以加一个标志变量flag，每轮排序前让flag置零，如果本轮排序有交换，就flag=1，如果本轮没有交换，说明已经排好了，flag还是0.下一轮被终止，排序完成。
void BubbleSort2(int a[],int n)
{
bool flag=1;
for(int i=n;flag;i--)
{
flag=0;
for(int j=1;j<i;j++)
{
if(a[j-1]>a[j])
{
swap(a[j-1],a[j]);
flag=1;
}
}
}
}
3.更加优化的冒泡排序。如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。
void BubbleSort3(int a[],int n)
{
int flag=n;
for(int i;flag;)
{
i=flag;
flag=0;
for(int j=1;j<i;j++)
{
if(a[j-1]>a[j])
{
swap(a[j-1],a[j]);
flag=j;
}
}
}
}
本文参考
MoreWindows Blog的http://blog.csdn.net/morewindows/article/details/6657829完成，只是叙述和代码稍加修改
版权声明：本文为博主原创文章，未经博主允许不得转载。