黑马程序员技术交流社区

标题: 冒泡算法的三种实现 [打印本页]
作者: sunyang    时间: 2015-4-19 01:52
标题: 冒泡算法的三种实现
冒泡排序是非常容易理解和实现，以从小到大排序举例：
设数组长度为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;

  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. }
复制代码





作者: 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 leads to some interesting theoretical problems  --- by Donald Knuth
                        
作者: 桑小龙    时间: 2015-4-19 09:06
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
作者: tyisbest    时间: 2015-4-19 09:54
编程是一门艺术啊!!!!!
作者: sunyang    时间: 2015-4-19 10:04
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 ...

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

没有。至少就主流语言标准库的排序算法实现来说，我没有看到有使用冒泡排序的，倒是有在小规模排序时使用插入排序的，比如jdk。如果不要求稳定排序，小规模时用希尔排序优势非常明显。实际上从你列举的冒泡优化方式来说，也没有一种是针对规模的，全是针对特殊初始顺序
作者: 大家叫我小祥子    时间: 2015-4-19 14:36
楼主好人，我就来一水贴得，你这个排序真心吊，一个比一个复杂
作者: 四头    时间: 2015-4-19 14:53
很厉害，很强大
作者: 帅哥    时间: 2015-4-19 21:30
mark, 回头好好看看
作者: 桑小龙    时间: 2015-4-19 21:36
桑小龙 发表于 2015-4-19 09:06
......your English is really good

呵呵呵，挺谦虚的



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2