| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 350 人关注过本帖
标题:冒泡排序法详析
只看楼主 加入收藏
lyb661
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:18
帖 子:47
专家分:83
注 册:2018-12-12
结帖率:71.43%
  问题点数:0  回复次数:0   
冒泡排序法详析
冒泡排序法详析
   作者:lyb661 (20190102)
    冒泡排序法,是大多数人接触到的第一种排序算法,也是一种最简单的排序算法。
冒泡排序法利用循环,对一个数值序列从头至尾两相比较,使数值较大的数不断后移。例如,有数组:
    int a[]={86,46,22,18,77,45,32};

    第一轮比较结果:
    46,22,18,77,45,32,86
    第二轮比较结果:
    22,18,46,45,32,77,86
    第三轮比较结果:
    18,22,45,32,46,77,86   
    第四轮比较结果:
    18,22,32,45,46,77,86
    第五轮比较结果:
    18,22,32,45,46,77,86
    第六轮比较结果:
    18,22,32,45,46,77,86
   
至此,排序完成。
    冒泡排序算法使用套嵌循环来实现排序的目标。外循环控制循环轮次。对于n个元素的数组,要完成排序,理论上需要n-1轮循环。上例中的数组a[],有7个元素,因此需要6轮循环。
套嵌中的内循环,完成元素两两比较,并交换元素的位置。每次内循环,有两个数参加比较。上例中的数组,第一轮循环,有7个元素两相比较,因此需要6轮循环,才能完成最大数的尾移。第二轮需要比较的元素减少了1个,因此需要5次循环……依次类推。完成排序,内循环一共进行了6+5+4+3+2+1=21(次)。
由此可见,冒泡排序中冒泡的含义,并非如多数人所说的小数像气泡一样上浮,而是大数不断地下沉。就好像向深潭中丢下一块石头,泛起的泡沫,不过意味着石头正在沉入潭底。
每一次冒泡,即表示一个大数移到末尾。
补充:大家可能注意到,例中数组的排序至第四轮已经完成,第五六轮没有什么操作。这与数组元素的复杂程度和程序运行的效率有关。每一个数组中的元素,不大可能完全无序,遇到这种情况,程序将无事可做。有兴趣的,可以优化一下排序的代码,使其路过不必要的循环。我尝试在内循环中使用while循环,甚至while空语句,但是没有成功。
下边是冒泡排序的完整代码:
 
//bubble_sort.cpp
#include <iostream>
using namespace std;

void swap_arr(int& x, int& y)
{
    int tmp = x;
    x = y;
    y = tmp;
}

void print(int a[],int n)
{
    for(int i=0;i<n;i++){
        if(i>0)
            cout<<' ';
        cout<<a[i];
    }
    cout<<'\n';
}

void bubble_sort(int a[],int n)
{
    for(int i=0;i<n-1;i++)
        for(int j=0;j<n-1-i;j++){
            if(a[j]>a[j+1])
                swap_arr(a[j],a[j+1]);
            print(a,n);
        }
}

int main()
{
    int a[]={86,46,22,18,77,45,32};
    int n=sizeof(a)/sizeof(a[0]);

    print(a,n);
    cout<<"\n-------------分割线-------------\n";
    cout <<endl<< endl;

    bubble_sort(a,n);
    cout<<"\n-------------分割线-------------\n";
    print(a,n);

    cout<<endl;

    return 0;
}

内外循环全部排序过程如下:

86 46 22 18 77 45 32

-------------分割线-------------


46 86 22 18 77 45 32
46 22 86 18 77 45 32
46 22 18 86 77 45 32
46 22 18 77 86 45 32
46 22 18 77 45 86 32
46 22 18 77 45 32 86
22 46 18 77 45 32 86
22 18 46 77 45 32 86
22 18 46 77 45 32 86
22 18 46 45 77 32 86
22 18 46 45 32 77 86
18 22 46 45 32 77 86
18 22 46 45 32 77 86
18 22 45 46 32 77 86
18 22 45 32 46 77 86
18 22 45 32 46 77 86
18 22 45 32 46 77 86
18 22 32 45 46 77 86
18 22 32 45 46 77 86
18 22 32 45 46 77 86
18 22 32 45 46 77 86

-------------分割线-------------
18 22 32 45 46 77 86


Process returned 0 (0x0)   execution time : 0.047 s
Press any key to continue.
搜索更多相关主题的帖子: 冒泡排序 排序 循环 比较 int 
2019-01-02 10:19







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

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