经典排序算法之冒泡排序

算法之冒泡排序"/>

经典排序算法之冒泡排序

前言

最近在学习一些排序算法相关的知识，然后为了巩固知识，想把所学所想以文章的形式进行整理记录和输出。
提到排序，想必大家都能想到冒泡排序，相信只要是程序员也应该都知道这个耳熟能详的经典算法了。
虽然冒泡排序不是最优的排序方案，但绝对绝对称得上是经典。
在我最初学习冒泡排序时其实并不懂得它的具体思路是什么，老师只是让我们记住了一个口诀：“外层循环 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比，交换