冒泡排序是非常容易理解和实现，以从小到大排序举例：
设数组长度为N。
1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。
2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
3．N=N-1，如果N不为0就重复前面二步，否则排序完成。

按照定义很容易写出代码：

1. //冒泡排序1
   
2. void BubbleSort1(int a[], int n)
   
3. {
   
4.        int i, j;
   
5. 
   
6.        for (i = 0; i < n; i++)
   
7.               for (j = 1; j < n - i; j++)
   
8.                      if (a[j - 1] > a[j])
   
9.                             Swap(a[j - 1], a[j]);
   
10. }

复制代码

下面对其进行优化，设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。

1. //冒泡排序2
   
2. void BubbleSort2(int a[], int n)
   
3. {
   
4.        int j, k;
   
5.        bool flag;
   
6.       
   
7.        k = n;
   
8.        flag = true;
   
9.        while (flag)
   
10.        {
    
11.               flag = false;
    
12.               for (j = 1; j < k; j++)
    
13.                      if (a[j - 1] > a[j])
    
14.                      {
    
15.                             Swap(a[j - 1], a[j]);
    
16.                             flag = true;
    
17.                      }
    
18.               k--;
    
19.        }
    
20. }

复制代码

再做进一步的优化。如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。

1. //冒泡排序3
   
2. void BubbleSort3(int a[], int n)
   
3. {
   
4.        int j, k;
   
5.        int flag;
   
6.       
   
7.        flag = n;
   
8.        while (flag > 0)
   
9.        {
   
10.               k = flag;
    
11.               flag = 0;
    
12.               for (j = 1; j < k; j++)
    
13.                      if (a[j - 1] > a[j])
    
14.                      {
    
15.                             Swap(a[j - 1], a[j]);
    
16.                             flag = j;
    
17.                      }
    
18.        }
    
19. }

复制代码

the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems  --- by Donald Knuth
                        

fantacyleo 发表于 2015-4-19 04:15
the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it lea ...

......your English is really good

编程是一门艺术啊!!!!!

fantacyleo 发表于 2015-4-19 04:15
the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it lea ...

小规模排序的时候冒泡还是有优势的

sunyang 发表于 2015-4-19 10:04
小规模排序的时候冒泡还是有优势的

没有。至少就主流语言标准库的排序算法实现来说，我没有看到有使用冒泡排序的，倒是有在小规模排序时使用插入排序的，比如jdk。如果不要求稳定排序，小规模时用希尔排序优势非常明显。实际上从你列举的冒泡优化方式来说，也没有一种是针对规模的，全是针对特殊初始顺序

楼主好人，我就来一水贴得，你这个排序真心吊，一个比一个复杂

很厉害，很强大

mark, 回头好好看看

桑小龙 发表于 2015-4-19 09:06
......your English is really good

呵呵呵，挺谦虚的