| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1485 人关注过本帖, 1 人收藏
标题:冒泡排序---内附步骤
只看楼主 加入收藏
木偶人丶
Rank: 2
等 级:论坛游民
帖 子:36
专家分:16
注 册:2017-3-3
结帖率:88.89%
收藏(1)
已结贴  问题点数:20 回复次数:2 
冒泡排序---内附步骤
冒泡排序,共享一下
程序代码:
/*
        2017年3月13日 16:22:38
        冒泡排序经典排序算法 - 冒泡排序Bubble sort原理如下。
*/
#include<stdio.h>
void sort(int * a, int len)
{
    int i, j;
    int t;
    for(i=0; i<len-1; ++i)
    {
        for(j=0; j<len-1-i; ++j)
        {
            if(a[j]>a[j+1])
            {
                t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
        }
    }
}


int main(void)

{
    int i;
    int a[6]={6, 9, 7, -8, 3, 0};
    sort (a, 6);
    for(i=0; i<6; ++i)
        printf("%2d",a[i]);
    printf("\n");
    return 0;
}
/*
--------------
输出结果为:
-8 0 3 6 7 9
Press any key to continue
--------------
*/
/*
---------------------
简单原理如下:
原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,
这样一趟过去后,最大或最小的数字被交换到了最后一位,
然后再从头开始进行两两比较交换,直到倒数第二位时结束,其余类似看例子
例子为从小到大排序,
原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 |

第一趟排序(外循环)
第一次两两比较6 > 2交换(内循环)
交换前状态| 6 | 2 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 6 | 4 | 1 | 5 | 9 |

第二次两两比较,6 > 4交换
交换前状态| 2 | 6 | 4 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 6 | 1 | 5 | 9 |

第三次两两比较,6 > 1交换
交换前状态| 2 | 4 | 6 | 1 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 6 | 5 | 9 |

第四次两两比较,6 > 5交换
交换前状态| 2 | 4 | 1 | 6 | 5 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

第五次两两比较,6 < 9不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

第二趟排序(外循环)
第一次两两比较2 < 4不交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |
交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

 
第二次两两比较,4 > 1交换
交换前状态| 2 | 4 | 1 | 5 | 6 | 9 | 
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

第三次两两比较,4 < 5不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 | 
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

第四次两两比较,5 < 6不交换
交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

 
第三趟排序(外循环)
第一次两两比较2 > 1交换
交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

第二次两两比较,2 < 4不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 | 
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

第三次两两比较,4 < 5不交换
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 | 
交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

第四趟排序(外循环)无交换
第五趟排序(外循环)无交换

排序完毕,输出最终结果1 2 4 5 6 9
---------------------
*/
搜索更多相关主题的帖子: 经典 
2017-05-07 18:47
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:20 
j的值直接为i + 1不就得了,只有进入内循环为j赋值的一次计算。


程序代码:
void sort(int * a, int len)
{
    int i,j;
    int t;

    for( i = 0; i < len; ++i )
        for( j = i + 1; j < len; ++j )
            if( a[ i ] > a[ j ] )
            {
                t = a[ i ];
                a[ i ] = a[ j ];
                a[ j ] = t;
            }
}



你的内循环每次循环都需要2次运算,如果涉及到交换的话,那就是4次运算,所以你的算法并不高效,而且在可读性上也远不及上面的代码。

我对你的代码稍作修改,打印两个次数,一个是内循环次数,一个是内循环中的计算次数。



图片附件: 游客没有浏览图片的权限,请 登录注册



程序代码:
#include<stdio.h>
void sort(int * a, int len)
{
    int i, j;
    int t;
    int x;
    int y;

    for(i=0, x = 0, y = 0; i<len-1; ++i)
    {
        for(j=0; j<len-1-i; ++j,++x)
        {
            y += 2;
            if(a[j]>a[j+1])
            {
                y += 2;
                t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
        }
    }
    printf("内循环次数:%d\n",x);
    printf("内循环计算次数:%d\n",y);
}


int main(void)

{
    int i;
    int a[6]={6, 9, 7, -8, 3, 0};
    sort (a, 6);
    for(i=0; i<6; ++i)
        printf("%2d",a[i]);
    printf("\n");
    return 0;
}



以下代码生成1W个随机数,测试两种排序所用的时间,每种算法执行10次。
先给出结果,你的代码是算法2.
图片附件: 游客没有浏览图片的权限,请 登录注册


下面是生成10W个随机数进行排序所花费的时间:
图片附件: 游客没有浏览图片的权限,请 登录注册


程序代码:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*void sort(int * a, int len)//冒泡排序算法1
{
    int i,j;
    int t;

    for( i = 0; i < len; ++i)
        for( j = i + 1; j < len; ++j )
            if( a[ i ] > a[ j ] )
            {
                t = a[ i ];
                a[ i ] = a[ j ];
                a[ j ] = t;
            }
}
*/

void sort(int * a, int len)//冒泡排序算法2
{
        int i, j;
        int t;
    
        for(i=0; i<len-1; ++i)
        for(j=0; j<len-1-i; ++j)
                if(a[j]>a[j+1])
                {
                    t = a[j];
                    a[j] = a[j+1];
                    a[j+1] = t;
                }
}



int main(void)
{
        int i;
    int j;
        int a[10000];
        clock_t time1;

    for( j = 0; j < 10; ++j )
    {
            time1 = clock();
            srand((unsigned int)time(NULL));
            sort (a, 10000);
            for(i=0; i<10000; ++i)
                a[i] = rand() % 10000;
        
            sort (a, 10000);
            printf("算法2(第%d次):%.2lf\n",j,(double)(clock() - time1)/CLOCKS_PER_SEC);
    }
    return 0;
}



[此贴子已经被作者于2017-5-7 23:12编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-05-07 19:02
木偶人丶
Rank: 2
等 级:论坛游民
帖 子:36
专家分:16
注 册:2017-3-3
收藏
得分:0 
回复 楼主 木偶人丶
恩恩,,受教了,谢谢
2017-05-08 11:33
快速回复:冒泡排序---内附步骤
数据加载中...
 
   



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

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