++++++++++

冒泡排序
　

“冒泡”是什么意思？湖底有时会冒出一个气泡，气泡刚在湖底时，是很小的，在向上浮的过程中，才一点地慢慢变大。学过高中的物理的人，应该不难解释这一现象。冒泡排序的过程有点类似这个过程，每前进一步，值就大一点。

　

排序当然有两个方向，一种是从小排到大，一种是从大排到小。大多数教科书里都讲第一种，我们也如此。这样一来，冒泡排序法就改为“沉泡法”了，较大值一点点跑到数组中的末尾。

　

一般教科书里也会说，冒泡排序法是人们最熟悉，及最直观的排序法，我可不这样认为。或许老外在生活中用的是这种最笨的排序法？我猜想，大家在生活中99%使用后面要讲的“选择”排序法。

　

冒泡排序是这么一个过程(从小到大):

　

1、比较相邻的两个元素，如果后面的比前面小，就对调二者。反复比较，到最后两个元素。结果，最大值就跑到了最末位置。

2、反复第一步，直到所有较大值都跑到靠后的位置。

　

看一眼例子：

　

2，5，1，4，3

　

第一遍：

·比较第一对相邻元素：2，5，发现后面的5并不比2小，所以不做处理。 序列保持不变：2，5，1，4，3

·继续比较后两对元素：5，1，发现后面的1比前面的5小，所以对调二者。现在，序列变为：2，1，5，4，3

·继续比较后两对元素：5，4……对调，于是：2，1，4，5，3

·继续比较后两对元素：5，3……对调，于是：2，1，4，3，5 <----- OK,现在最大值5跑到最尾处了。

　

大泡泡“5”浮出来了，但前面的2,1,4,3,还是没有排好，没事，再来一遍，不过，由于最后一个元素肯定是最大值了，所以我们这回只排到倒数第二个即可。

　

第二遍：

·比较第一对相邻元素：2，1，发现1比2小，所以对调：1,2,4,3,5

·继续比较后两对元素：2，4，不用处理，因为后面的数比较大。序列还是：1,2,4,3,5

·继续 4，3，对调：1,2,3,4,5。

　

前面说，5 不用再参加比较了。现在的序列是1，2，3，4，5。接下来，我们再来一遍：

　

第三遍：

·比较第一对相邻元素：1，2：不用对调。

……等等……

有人说，现在已经是1，2，3，4，5了，完全是排好序了啊，何必再来进行呢？我们确实是看出前面1，2，3也井然有序了，但对于程序来说，它只能明确地知道自己已经排好了两个数：4，5，并不知道的1，2，3凑巧也排好了。所以它必须再排两次，直到确认把3和2都已推到合适的位置上。最后剩一个数是1，因为只有一个数，没得比，所以这才宣告排序结束。

　

那么到底要排几遍？看一看前面的“第一遍”、“第二遍”的过程你可发现，每进行一遍，可以明确地将一个当前的最大值推到末尾，所以如果排 Count 个数，则应排 Count 遍。当然，最后一遍是空走，因为仅剩一个元素，没得比较。

　

下面就动手写冒泡排序法的函数。写成函数是因为我们希望这个排序法可处理任意个元素的数组。

　

//冒泡排序(从小到大)：

//num: 要接受排序的数组

//count : 该数组的元素个数

void bubble(int num[],int count)

{

    int tmp;

　

    //要排Count个数，则应排Count遍：

    for (int i = 0; i < count; i++)

    {

       for(int j = 0; j < count - i - 1; j++)

       {

           //比较相邻的两个数：

           if(num[j+1] < num[j])

           {

               //对调两个数，需要有"第三者"参以

               tmp = num[j+1];

               num[j+1] = num[j];

               num[j] = tmp;

           }

       }

    }      

}

　

注意在内层循环中j的结束值是 count - i - 1。 要理解这段代码，明白为什么结束在count - i -1？如果你忘了如何在CB进行代码调试，如果设置断点，如何单步运行，如何观察变量的值，那么你需要“严重”复习前面有关“调试”的章节；如果你一直是高度着每一章的程序到现在，那么你可以继续下面的内容。

　

排序函数写出一个了，如何调试这个函数？在CB里新建一空白控制台程序，然后在主函数里，让我们写一些代码来调用这个函数，并且观察排序结果。

　

#include <iostream.h>

……

void bubble(int num[],int count)

{

  ……

}

　

int main() //我实在有些懒得写main里两个参数，反正它们暂时对我们都没有用，

           //反正CB会为你自动生成，所以从此刻起，我不写了,除非有必要。

{

    int values[] = {2,5,1,4,3};

    int count = sizeof(values[]) / sizeof(values[0]);

    bubble(value,sizeof);

}

　

你要做的工作是单步跟踪上面的代码，看看整个流程是不是像我前面不厌其烦的写的“第一遍第二遍第三遍”所描述的。

　

完成上面的工作了吗？全部过程下来，只花20分钟应该算是速度快或者不认真的了（天知道你是哪一种？天知道你到底是不是没有完成就来骗我？）。现在让这个程序有点输出。我们加一个小小的函数：

　

//输出数组的元素值

//num :待输出的数组

//count:元素个数

void printArray(int num[],int count)

{

  for(int i = 0; i < count; i++)

  {

     count << num[i] << ",";

  }

　

  cout << endl;

}

　

把这个函数加到main()函数头之前，然后我们用它来输出：

int main() //我实在有些懒得写main里两个参数，反正它们暂时对我们都没有用，

           //反正CB会为你自动生成，所以从此刻起，我不写了,除非有必要。

{

    int values[] = {2,5,1,4,3};

    int count = sizeof(values[]) / sizeof(values[0]);

    

    cout << "排序之前：" << endl;

    printArray(values,count);

　

    //冒泡排序：

    bubble(value,sizeof);

　

    cout << "排序之后:"  << endl;

    printArray(values,count);

　

    system("PAUSE");

}

　

后面要讲的其它排序法也将用这个printArray()来作输出。

　

冒泡排序是效率最差劲的方法（速度慢），不过若论起不另外占用内存，则它当属第一。在交换元素中使用了一个临时变量（第三者），还有两个循环因子i和j，这些都属于必须品，其它的它一个变量也没多占。

　

我们现在讲讲如何避免数据其实已经排好，程序仍然空转的的局面。

首先要肯定一点，至少一遍的空转是不可避免的，这包括让人来排，因为你要发现结果已是1，2，3，4，5了，你也是用眼睛从头到尾抄了一遍（如果你视力不好，说不定还要扫两遍呢）。

接下来一点，我们来看看除了第一遍空转，后面的是否可以避免。冒泡排序法的空转意味着什么？因为算法是拿相邻的两个比较，一发现次序不合“从小到大”的目的（小的在大的后头），就进行对调。所以如果这个对调一次也没有进行，那就说明后面的元素必然是已经完全有序了，可以放心地结束。

　

让我们来加个变量，用于标志刚刚完成的这一遍是否空转，如果是空转，就让代码跳出循环。

　

//冒泡排序(从小到大，且加了空转判断)：

void bubble(int num[],int count)

{

    int tmp;

    bool swapped;  //有交换吗？

　

    //要排Count个数，则应排Count遍：

    for (int i = 0; i < count; i++)

    {

       //第一遍开始之前，我们都假充本遍可能没有交换（空转）：

       swapped = false;

　

       for(int j = 0; j < count - i - 1; j++)

       {

           //比较相邻的两个数：

           if(num[j+1] < num[j])  //后面的数小于前面的数

           {

               swapped = true;  //还是有交换

             

               //对调两个数，需要有"第三者"参以

               tmp = num[j+1];

               num[j+1] = num[j];

               num[j] = tmp;

           }

       }

       

       if (!swapped)

          break;

    }      

}

　

加了swapped标志，这个算法也快不了多少，甚至会慢也有可能。冒泡排序还有一些其它的改进的可能，但同样作用不大，并且会让其丧失仅有优点“代码简单直观”。所以我个人认为真有需要使用冒泡排序时，仅用最原汁原味的“泡”就好。必竟，你选择了冒泡算法，就说明你对本次排序的速度并无多高的要求。

　

对于n个元素，原汁原味的“冒泡排序”算法要做的比较次数是固定的： （n  - 1）* n/2 次的比较。

交换次数呢？如果一开始就是排好序的数据，则交换次数为0。

一般情况下为 3 * (n - 1) * n / 4;最惨时（逆序）为3 *  (n - 1) * n / 2。

　

冒完泡以后——情不自禁看一眼窗台罐头瓶里那只胖金鱼——让我们开始中国人最直观的选择排序法吧。对了，补一句，如果你看到有人在说“上推排序”，那么你要知道，“上推排序”是“冒泡排序”的另一种叫法，惟一的区别是：它不会让我们联想到金鱼。

从哪里粘得，我的意思是哪里有讲算法的

讲得怎么样？

我晕好复杂哦看不懂耶