20200613-02 算法集合-冒泡法

拼搏现实的明天。 2023-02-17 08:54 4阅读 0赞

## 算法讲解 ##

写这个系列的初衷就是网上源码质量参差不齐，我能保证的是个人上传代码都经过程序验证，当然有可能存在不正确的地方，欢迎斧正，第一时间修改，谢谢

冒泡法，可以理解为像个泡泡一样上浮，我们需要的东西上浮，不需要的东西下沉，不断进行两两相互比较，满足条件则交互两个数据之间的位置

举例: 22 11 3 5 99 29 我们需要升序(从小到大排列) array[i] > array[i+1]
    第一次: 22 11 3 5 99 29
    i:0 22 > 11 交换 11 22　3 5 99 29
    i:1 22 > 3  交换 11 3 22 5 99 29
    i:2 22 > 5  交换 11 3 5 22 99 29
    i:3 22 > 99 不交换 11 3 5 22 99 29  
    i:4 99 > 29 交换 11 3 5 22 29 99
    第二次: 11 3 5 22 29 99
    i:0 11 > 3 交换 3 11 5 22 29 99
    i:1 11 > 5 交换 3 5 11 22 29 99
    i:2 11 > 22 不交换 3 5 11 22 29 99
    i:3 22 > 29 不交换 3 5 11 22 29 99
    第三次: 3 5 11 22 29 99
    i:0 3 > 5 不交换 3 5 11 22 29 99
    i:1 5 > 11 不交换 3 5 11 22 29 99
    i:2 11 > 22 不交换 3 5 11 22 29 99
    第四次: 3 5 11 22 29 99
    i:0 3 > 5 不交换 3 5 11 22 29 99
    i:1 5 > 11 不交换 3 5 11 22 29 99
    第五次: 3 5 11 22 29 99
    i:0 3 > 5 不交换 3 5 11 22 29 99

以上就是完成一次排序  
1 每次都是相邻数值进行比较，满足条件则交互数字  
2 由于每次循环完成之后，最后数值已经满足条件，可以直接跳过提升效率

## 算法源码 ##

void sort_bubb(int array[], int n)
    { 
        auto temp { 0};
        //两两比较，所以只要执行到 array[n-3] < array[n-2]则一轮循环结束 
        for (int i = 0; i < n - 1; i++) {  
        	//n-i-1 就是跳过数值已经放置正确数值的位置，提升效率
            for (int j = 0;j < n - i - 1; j++) { 
                if (array[j] > array[j+1]) {  //> 升序从小到达　<　降序从大到小
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }

## 推荐课程 ##

尹成老师带你学算法

数据结构核心原理与算法应用