经典排序算法之冒泡排序

超、凢脫俗 2022-09-12 14:43 163阅读 0赞

### 前言 ###

> 最近在学习一些排序算法相关的知识，然后为了巩固知识，想把所学所想以文章的形式进行整理记录和输出。  
> 提到排序，想必大家都能想到冒泡排序，相信只要是程序员也应该都知道这个耳熟能详的经典算法了。  
> 虽然冒泡排序不是最优的排序方案，但绝对绝对称得上是经典。  
> 在我最初学习冒泡排序时其实并不懂得它的具体思路是什么，老师只是让我们记住了一个口诀：“外层循环 n - 1，内层循环 n - i - 1。其中n为数组的长度，i是外层循环的变量”。还别说这个口诀还真\*\*的准，一套准对。就这么稀里糊涂的用了好几年，虽然每次都能用对，但正如那句话：知其然不知其所以然。直到前段时间学习算法，这才彻底明白了为什么要这样用，同时还知道了原来还有一种优化方案。接下来我们就一起来分析一下冒泡排序的实现思路及优化方案。

### 思路分析 ###

> 假设给定一个无序数组\[12, 1,8,21,7,4,10\]，我们想让这个数组中的值进行升序排序，那么最终想要的效果就是\[1, 4,7,8,10,12,21\]。其实冒泡的原理很简单，就是两个相邻数进行比较然后交换位置，以上面的数组为例。记住我们的口诀（外层循环n-1，内层循环n-i-1）
> 
>  *  循环开始12和1比较，发现12比1大，然后交换位置则变为：\[1,12,8,21,7,4,10\]
>  *  循环继续12和8比，交换位置：\[1,8,12,21,7,4,10\]
>  *  循环继续12和21比，不用交换位置：\[1,8,12,21,7,4,10\]
>  *  循环继续21和7比，交换位置：\[1,8,12,7,21,4,10\]
>  *  循环继续21和4比，交换位置：\[1,8,12,7,4,21,10\]
>  *  循环继续21和10比，交换位置：\[1,8,12,7,4,10,21\]
>  *  循环结束，共进行了6次比较  
>     我们发现得到的结果并不是我们最终想要的，但是最大一个数已经被排到了最后。显然只有一轮循环是不够的，依照上面我们提到的口诀，要得到我们期望的结果一共得需要6（外循环n-1）轮的循环。
>  *  第二轮循环结束，得到结果：\[1,8,7,4,10,12,21\]，此轮循环共计比较5次，且第二大值被排到倒数第二。
>  *  第三轮循环结束：得到结果：\[1,7,4,8,10,12,21\]，此轮循环共计比较4次，且第三大值被排到倒数第三。
>  *  第四轮循环结束：得到结果：\[1,4,7,8,10,12,21\]，此轮循环共计比较3次，且第四大值被排到倒数第四。
>  *  第五轮循环结束：得到结果：\[1,4,7,8,10,12,21\]，此轮循环共计比较2次，且第五大值被排到倒数第五。
>  *  第六轮循环结束：得到结果：\[1,4,7,8,10,12,21\]，此轮循环共计比较1次，且第六大值被排到倒数第六。

> 经过上面的六轮循环，最终已经得到了我们期望的结果了，但是从上面的分析不难看出，其实在第四轮的时候就已经得到期望的结果了，那为什么还要再继续循环2轮呢（外循环n-1），而内循环为什么又是n-i-1呢。  
> 其实上面这个例子中的数组比较特殊刚好在第四轮就得到结果了，但是依照冒泡的原理就是：两个相邻的数都要进行比较，而每一轮循环都只是两个相邻数进行交换位置，因此在第四轮结束后还需要第五轮1，4，7比较和第六轮1，4比较，这样才能确保每两个相邻数都能得到比较，那么也就是必须要进行n-1轮循环。

> 至于内层循环 n - i - 1：从上面几轮循环可以看出，每一轮的循环都会将比较大的数挪到了后面，比如第一轮循环结束最大值21排在最后，而再进行第二轮循环时21就不用再参与比较了，因为它已经是最大值了，同理在进行第三轮循环时那么倒数第二个值和最后一个值也都不需参与比较，同理得出内层循环比较的次数是逐渐递减的，因此得出内层循环n - i - 1

### 冒泡代码 ###

### 总结 ###

> 至此我们已经实现冒泡排序算法，但从上面的分析思路来看，这并不是最优的冒泡，会有一些不必要的浪费。在下一篇文章[经典排序算法之冒泡排序的优化方案][Link 1]中我们将分析一下冒泡的优化。

[Link 1]: https://blog.csdn.net/lixiaosenlin/article/details/120489154