| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 16783 人关注过本帖, 22 人收藏
标题:冒泡算法讲解
取消只看楼主 加入收藏
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
结帖率:96.15%
收藏(22)
 问题点数:0 回复次数:10 
冒泡算法讲解
我发现,很多人写的所谓冒泡算法代码,其实是错的,这里给一份正确的代码,并讲解正确的冒泡代码的特征
程序代码:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//这个宏,定义交换两个数a,b,其中t是交换临时变量
#define SWAP(a, b) do {int t = a; a = b; b = t; } while(0)

int bubblesort_t(int* arr, int len)
{
    for (int ed = len-1; ed > 0; --ed) // ed 控制内循环的结束边界
    {
        for (int iter = 0; iter < ed; ++iter) // 内循环,it遍历从 0 至 ed-1
        {
            if ( !(arr[iter] <= arr[iter+1]) ) // 大小比较,比较方式直接决定排序的方式
            {
                SWAP(arr[iter], arr[iter+1]);  // 对不符合比较结果的,使其交换,以符合比较的方式
            }
        }
    }
    return 0;
}

int main()
{
    int nums[100];
    int n_nums = 10, n;

    srand((unsigned)time(NULL)); /* 初始化随机数 */
    for (n=0; n < n_nums; n++)
    {
        nums[n] = rand() % 99 + 1;  /*利用rand()函数产生随机数,%99表示产生随机数不超过三位数*/
    }

    printf("排序前:\n");
    for (n=0; n < n_nums; n++)
    {
        printf("%d ", nums[n]);     /*在显示屏上输出由上面随机产生的数字*/
    }

    bubblesort_t(nums, n);

    printf("\n排序后:\n");
    for (n=0; n < n_nums; n++)
    {
        printf("%d ", nums[n]);
    }
    scanf("%*s");
    return 0;
}


main函数可以不管,主要看bubblesort_t这个函数,有这样几个特点:
1 外层变量控制内层循环的结束条件,而非起始点
2 二重循环里,内层循环的控制变量和终止条件必然是一自加一自减
3 如果是无经过优化的冒泡,总共要比较len*(len-1)/2次
4 每次比较,总是比较相邻的两个数,不会发生其它位置的数的比较

不符合这些特点的,那你的算法很可能是错的,但不排除一个复杂化的版本,1-3都不符合,但却排序结果是对的,
比如直接用一个len的平方(即内外循环都直接用len而不变化)的写法,虽然正确,但不是严格意义上的冒泡,并且效率比冒泡更低下。

相对而言,选择排序则比冒泡容易写对,因为内外循环方式一致,代码也好写,所谓10个新手9个写错冒泡,真是一点都不夸张

以下解释一下,1,2两个特点,为什么会这样。
首先,冒泡的定义是每次比较相邻的两个数,每一轮的比较,会把最值交换到最后一次参与比较的地方,即循环的终点的地方
然后,不管已经确定好的最值,把剩下的数做同样的事
好了,从以上定义里,我们知道,最后一次参与比较的地方,即循环的终点的地方,一轮的比较结束后,那里是最大值或者最小值
那个数是不会再参与下一轮的比较的,那么,每一轮,起点不会变,变的是终点,
所以外层循环的变量,要控制内层循环,即每一轮的终点的值
我们假设S是起点,E是终点:
S _ _ _ ... _ _ _ E
内层循环的比较,起点是不变的,并且从起点不断向终点比较,内层循环从左向右
但是,终点在每一轮比较完以后,下一轮就不需要再比较了,E点每一轮就会左移一格,也就是说,外层循环从右向左
好了,这样以来,你定义从左向右,不管是下标递增还是递减,内外层循环的变量,总是一个加的话,另一个必然是减
否则,那你终点的值,根本连是不是最值都不能保证,只多试几组数就会发现排序并未完成,也就是说那个算法是错的

以上分析就到这里了,当你看明白这文章以后,相信你以后,一眼就可以看出一个自称冒泡算法的代码,是不是错的

[ 本帖最后由 御坂美琴 于 2010-10-6 16:54 编辑 ]
搜索更多相关主题的帖子: 算法 冒泡 讲解 
2010-10-04 16:39
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
收藏
得分:0 
VC6对标准支持的不够好,把for里面的定义,写在for前面就正常了

永远为正义而奋斗,锄强扶弱的Level 5 超能力者
とある魔術の禁書目錄インデックス__御み坂さか美み琴こと
http://bbs.bccn.net/space.php?action=threads&uid=483997
2010-10-04 17:37
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
收藏
得分:0 
还有一个可能是你用C方式编译的吧?早期的C不支持这种写法,或者大家都改成这样吧:

int bubblesort_t(int* arr, int len)
{
    int ed;
    for (ed = len-1; ed > 0; --ed) // ed 控制内循环的结束边界
    {
        int iter;
        for (iter = 0; iter < ed; ++iter) // 内循环,it遍历从 0 至 ed-1
        {
            if ( !(arr[iter] <= arr[iter+1]) ) // 大小比较,比较方式直接决定排序的方式
            {
                SWAP(arr[iter], arr[iter+1]);  // 对不符合比较结果的,使其交换,以符合比较的方式
            }
        }
    }
    return 0;
}

永远为正义而奋斗,锄强扶弱的Level 5 超能力者
とある魔術の禁書目錄インデックス__御み坂さか美み琴こと
http://bbs.bccn.net/space.php?action=threads&uid=483997
2010-10-04 17:52
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
收藏
得分:0 
以下是引用菜虫编编在2010-10-4 19:10:35的发言:

那么长,而且还那么的繁琐,作铺垫的变量也太多了吧!!
精简才是精华啊!~~~

繁琐吗?我是从你写的代码精简出来的

永远为正义而奋斗,锄强扶弱的Level 5 超能力者
とある魔術の禁書目錄インデックス__御み坂さか美み琴こと
http://bbs.bccn.net/space.php?action=threads&uid=483997
2010-10-04 19:32
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
收藏
得分:0 
你注意一下,内循环中的条件是9-i,也就是说,外循环的i当成负值使用,那么,i++ 实际上等于 (9-i) --
i在自增,会导致9-i不断地减小
所以实际上也是一增一减的,你这个代码并没有问题

永远为正义而奋斗,锄强扶弱的Level 5 超能力者
とある魔術の禁書目錄インデックス__御み坂さか美み琴こと
http://bbs.bccn.net/space.php?action=threads&uid=483997
2010-10-05 18:08
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
收藏
得分:0 
改了一下描述:二重循环里,内层循环的控制变量和终止条件必然是一自加一自减
这样的话,我想会清晰一点

永远为正义而奋斗,锄强扶弱的Level 5 超能力者
とある魔術の禁書目錄インデックス__御み坂さか美み琴こと
http://bbs.bccn.net/space.php?action=threads&uid=483997
2010-10-06 16:56
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
收藏
得分:0 
问题是这样的,大多数的对C/C++自动格式化代码的软件,以行结尾的分号作为标记,
如果没有这个分号,那下一行会缩进一个tab的
如果直接用{int t = a; a = b; b = t; },虽然也是对的,并且你最后没写分号也不会错,但缩进时会错掉,下一行开始就多缩进了
如果写成do {int t = a; a = b; b = t; } while(0),效果虽然一样,但最后必须有分号,不然就编译错误
这样可以强迫你把代码写完整,自动缩进也不会错,更容易检查出问题

永远为正义而奋斗,锄强扶弱的Level 5 超能力者
とある魔術の禁書目錄インデックス__御み坂さか美み琴こと
http://bbs.bccn.net/space.php?action=threads&uid=483997
2010-10-12 21:20
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
收藏
得分:0 
以下是引用动力天在2010-10-14 01:16:53的发言:

#include "stdio.h"
void main()
    {
            int a[10],i,j,k;
            printf("Input  ten num:\n");
            for(i=0;i<10;i++)
            scanf("%d",&a);
            for(j=0;j<9;j++)
                {
                     for(i=0;i<9-j;i++)
                        if(a>a)
                          {  k=a;
                             a=a;
                             a=k;
                           }
                }
            printf("The last num:\n");
            for(i=0;i<10;i++)
            printf("%d\n",a);
   }
//这种“冒泡法”有什么缺陷吗?


最大的缺陷是没写成子函数

永远为正义而奋斗,锄强扶弱的Level 5 超能力者
とある魔術の禁書目錄インデックス__御み坂さか美み琴こと
http://bbs.bccn.net/space.php?action=threads&uid=483997
2010-10-14 21:21
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
收藏
得分:0 
以下是引用侧卫宝宝在2010-10-14 23:02:46的发言:

lz 我用的也是VC6.0 compile的时候是没有错误的 但是在bulid的时候提示出现错误:
--------------------Configuration: lianxi - Win32 Debug--------------------
Compiling...
maopao.c
D:\Program Files\Microsoft Visual Studio\MyProjects\lianxi\maopao.c(1) : error C2059: syntax error : '<'
执行 cl.exe 时出错.

lianxi.exe - 1 error(s), 0 warning(s)
 怎么回事?

麻烦,如果用C编译,请看5楼的说明

永远为正义而奋斗,锄强扶弱的Level 5 超能力者
とある魔術の禁書目錄インデックス__御み坂さか美み琴こと
http://bbs.bccn.net/space.php?action=threads&uid=483997
2010-10-14 23:05
御坂美琴
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:魔術の禁書目錄
等 级:小飞侠
威 望:9
帖 子:952
专家分:2929
注 册:2010-8-18
收藏
得分:0 
以下是引用stone_yang在2010-10-20 17:56:10的发言:

int bubblesort_t(int* arr, int len)
{   int *p=arr;
     int *n=arr;
    for ( arr; arr<p+len;arr++,n++)     
   {   n=arr;
        for (n; n < p+len;n++)        
        {
            if (*arr<=*(n+1))           
           {
                SWAP(*arr, *(n+1));  // 对不符合比较结果的,使其交换,以符合比较的方式
            }
         }
     }
     return 0;
}

说明:让第一个元素和所有的元素比较,得到最大的;然后让第二个和它后的所有元素比较,得到第二大的元素;依次下去,便得到从大到小的排列顺序。这样的算法更容易理解。
 程序没有调试过,希望版主以及同仁,探讨一下它的对与错。如有不合适请指出。

没有错,这样是更容易理解,在一楼已经说过了,你这种是选择排序,选择排序的确更容易懂,也容易写对得多,但本主题是冒泡排序,不是选择排序

永远为正义而奋斗,锄强扶弱的Level 5 超能力者
とある魔術の禁書目錄インデックス__御み坂さか美み琴こと
http://bbs.bccn.net/space.php?action=threads&uid=483997
2010-10-20 20:35
快速回复:冒泡算法讲解
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.014917 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved