关于初学者对冒泡排序算法的错误认识

关于冒泡排序，我觉得是初学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循环的范围，让其从后比较，也就是从下比较依次向上，两两互换。通过加入标志位，考虑到了没有出现元素交换的情况，这样就可以节省交换时间。经过改动的代码，其效率在很大程度上得到了改善和提高。