关于冒泡排序，我觉得是初学C语言时再也熟悉不过的基本排序算法了，还记得在C语言课上老师“声情并茂”地讲着这个是考试的重点内容。刚开始学的人都以为这是一个再也简单不过的算法了，无非就是两个for循环嵌套嘛！嗯，一开始我也是这样想的，不过随着学习数据结构的深入，我发现了课堂和书本上留下的一个巨大的坑。
先来看你所熟悉的代码，以下称山寨算法：
#include<stdio.h>
void Maopo(int a[], int n)
{
int i, j, temp;
for(i = 0; i<n-1; i++)
{
for(j = i+1; j<n; j++)
{
if(a[i]>a[j])
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
void main(void)
{
int a[10] = {9,7,8,6,1,2,3,5,4,0};
printf("已知数组： ");
for(int k = 0; k<10; k++)
printf("%d",a[k]);
printf("\n");
Maopo(a, 10);
printf("排序之后的数组：");
for(int x = 0; x<10; x++)
printf("%d",a[x]);
printf("\n");
}
嗯，没错，一个循环嵌套就轻松搞定了。懵懂无知的初学者认为这样已经万事大吉了，的确无论是怎样凌乱的序列交给以上程序都能正确排列出来，但是经过以后数据结构的深入学习后，我们还要考虑到一个算法的执行效率。好的算法能事半功倍，坏的算法能事倍功半。
先来看一下冒泡派寻的本质，它的思想是两两比较，然后从下向上比较排序，假设有n个元素，那么每次会发生n-1次的比较。照着以上代码，它并没有实现两两比较的意思。两两比较，即相邻两者互相比较，显然上述代码是死摁着一个元素让其分别与后续元素分别比较，当与后续全部元素都比较完成后。再开始死摁第二个头元素，重复循环。排序效率明显就下降了，依照此代码，我们只要稍微修改几处就能将山寨变成正版行货！
下面看一下正版代码：
#include<stdio.h>
void Maopo(int a[], int n)
{
bool flag;
int i, j, temp;
for(i = 0; i<n-1; i++)
{
flag = 0;
for(j = n-1; j>i; j--)
{
if(a[j-1]>a[j])
{
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
flag = 1;
}
}
}
if(!flag)
return;
}
void main(void)
{
int a[10] = {9,7,8,6,1,2,3,5,4,0};
printf("已知数组： ");
for(int k = 0; k<10; k++)
printf("%d",a[k]);
printf("\n");
Maopo(a, 10);
printf("排序之后的数组：");
for(int x = 0; x<10; x++)
printf("%d",a[x]);
printf("\n");
}
本程序可在C++标准编译器下编译运行。
其运行结果如下：
运行结果.png
看出哪里不一样了吗。其实只是变动了内部for循环的范围，让其从后比较，也就是从下比较依次向上，两两互换。通过加入标志位，考虑到了没有出现元素交换的情况，这样就可以节省交换时间。经过改动的代码，其效率在很大程度上得到了改善和提高。
