Chinaunix首页 | 论坛 | 博客
  • 博客访问: 387582
  • 博文数量: 80
  • 博客积分: 1750
  • 博客等级: 上尉
  • 技术积分: 1380
  • 用 户 组: 普通用户
  • 注册时间: 2011-11-13 11:35
文章分类
文章存档

2014年(3)

2013年(1)

2012年(54)

2011年(22)

分类: C/C++

2012-10-31 20:39:15

     在每一趟比较结束后,若从某个位置r开始,不在进行记录交换,就说明从A[r+1]到A[n-1]已经排好序,从而下一趟比较只要进行到位置r就行了。若某一趟没有元素交换,则算法结束。

改进后的算法如下,每次只记录最后一次交换的位置:
  1. void Bubble(int *Array, int n)
  2. {
  3.     int bound=n;
  4.     int m,i;
  5.     int a;

  6.     while(bound != 0){
  7.         m = 0;
  8.         for(i = 0; i < bound; i++){
  9.             if(*(Array+i) > *(Array+i+1)){
  10.                 a = *(Array+i);
  11.                 *(Array+i) = *(Array+i+1);
  12.                 *(Array+i+1) = a;
  13.                 m = i;
  14.             }
  15.         }
  16.         bound = m;          //记录发生最后一次交换的位置
  17.     }
  18. }

前面所看到的都是单向冒泡,经过一趟大气泡沉底或轻气泡上浮。为了提高效率,可以使用双向冒泡,即大气泡下沉的同时,也使轻气泡上浮。此为双向冒泡排序算法.
双向冒泡算法:

  1. void TwoBubble(int *Araay, int n)
  2. {
  3.     int boundmin = 0;
  4.     int boundmax = n;
  5.     int min, max, i, a;

  6.     while(boundmin < boundmax){
  7.         mmin=0;
  8.         max=0;
  9.         for(i = boundmin; i < boundmax; i++){
  10.              if(*(Array+i) > *(Array+i+1)){
  11.                    a = *(Array+i);
  12.                    *(Array+i) = *(Array+i+1);
  13.                    *(Array+i+1) = a;
  14.                    max = i;      #记录下沉最后一次交换的位置
  15.              }
  16.          }
  17.          if(max == 0)
  18.              break;
  19.          boundmax = max;
  20.          for(i = boundmax-1; i > boundmin; i--){
  21.               if(*(Array+i) < *(Array+i-1)){
  22.                     a = *(Array+i);
  23.                     *(Array+i) = *(Array+i-1);
  24.                     *(Array+i-1) = a;
  25.                     min = i;       #记录上升最后一次交换的位置
  26.               }
  27.          }
  28.          if(min == 0)
  29.             break;
  30.          boundmin = min;
  31.     }
  32. }



阅读(1866) | 评论(2) | 转发(2) |
给主人留下些什么吧!~~

yungho2012-11-02 18:41:28

leeXsen: 你确定那个双向冒泡排序算法里的 while(boundmin < boundmax) 没问题?好像boundmin和boundmax都等于0......
不好意思,我写错了。boundmax=n;.谢谢你把错误指出来。

leeXsen2012-11-01 23:27:42

你确定那个双向冒泡排序算法里的 while(boundmin < boundmax) 没问题?好像boundmin和boundmax都等于0.