Secto白帽博客-专注于技术研究

C/C++排序算法-冒泡排序

上一章我们讲了桶排序,我们这一章就来看看冒泡排序

1. 原理

冒泡排序的原理就是多次依次从前往后比较两数的大小(这里以A>B为例)若后一个数比前一个数小,则交换他们。
我们来步骤分析一下:
首先给出数据:

12 35 99 18 76

将其从大到小排列
先进行第一轮排序:
首先比较12和35,发现35大于12,就把他们交换位置

然后比较12和99,发现99比12大,交换他们的位置

接着比较12和18,18大于12,交换他们的位置

最后比较12和76,76大于12,交换他们的位置

好了,我们进行了一轮排序,最多还要进行3次排序才能使数组有序
下面给一个形象的第一轮排序步骤图:

我们第一轮排序成功把12放到了最后
下面再给出第二轮排序的步骤
此时初始位置:

35 99 18 76 12

先比较35和99,99大于35,交换他们的位置

然后比较35和18,18小于35,位置不变

接着比较18和76,76比18大,交换他们的位置

接着还需要比较么?记得我们第一轮就把最小的数放到最后了吧,现在可以直接跳出这一轮的循环

2. 分析

每轮排序都可以找到最小的数放到最后

3. 代码

for(i=1;i<=n-1;i++){//一共只需要n轮排序(理由我上面提到过,最后所有数都有序了,没必要再循环一遍)
    for(j=1;j<=n-i;j++){//依次和后面的数比较
        if(a[j+1]>a[j]){//如果后一个数比前一个数大
            t=a[j];//交换位置
            a[j]=a[j+1];
            a[j+1]=t;
        }
    }
}

图片来源于本人恩师啊哈磊所著《啊哈算法》中

By:海螺HL
Time:2020/3/19

当前页面是本站的「Google AMP」版。查看和发表评论请点击:完整版 »