冒泡排序，我可以这样学
排序算法有很多，像冒泡排序，选择排序，插入排序，希尔排序，快速排序等等。今天这篇文章呢，我们来聊一聊简单的冒泡排序（Bubble Sort）。
想必大家都知道鱼吐泡泡的现象，气泡从鱼的嘴巴里面呼出来，一个一个的往水面上冒出去。这是因为呀，气泡里面的拥有大量的二氧化碳，而二氧化碳比水要轻，所以气泡可以一个一个的往水面上浮动。
而我们今天要讲的冒泡排序与“鱼吐泡泡”现象有些相像，所以呢，我们可以把冒泡排序与该现象进行类比学习。
相比于“鱼吐泡泡”现象，冒泡排序的原理就是通过一次次的比较，将较大（较小）的元素向着数组的一侧移动。经过数次移动以后，数组中的元素就会按照从小到大（从大到小）排列起来。
了解了这些后，冒泡排序具体该怎么实现移动的动作呢，让我来给大家慢慢演示一遍：
有一个数组，里面存储着8个无序的数字，我们要做的就是将它们进行从小到大的顺序进行排列。
根据冒泡排序的思想，我们要把相邻的两个元素进行比较，因为要进行从小到大排序，如果前一个数比后一个数要大，那么我们就要交换两元素的位置；如果前一个数比后一个数要小或者相等，那么就无须交换元素，接着向下比较就好了。
例如：
首先是第一个数5与第二个数8进行比较, 5 < 8 , 则元素位置无须变化。
接下来让8和6进行比较，8 > 6 , 要交换8和6的位置。
然后再让8和3比较，8 > 3 , 所以交换8和3的位置。
再让8和9进行比较，8 < 9 , 元素位置不用改变。
接着再让9和2进行比较， 9 > 2 , 交换9和2的位置
接下来让9和1进行比较，9 > 1, 交换9和1的位置。
最后再让9和7进行比较，9 > 7 , 交换9和7的位置。
经过7次比较，我们选出了这8个元素中最大的元素—— 9，并且将元素9，像冒泡泡一样往上浮动，放在了数组的最后面。
这样，我们的第一轮冒泡排序已经结束，并且将元素9放在了最后，相当于形成了一个有序区，只不过此时的有序区只有一个元素9。
那么，现在我们再进行第二轮冒泡排序：
首先是5和6比较，5 < 6 , 元素位置不变。
再让6和3比较， 6 > 3 , 交换6和3的位置。
接着让6和8比较，6 < 8, 元素位置不变。
然后再让8和2进行比较，8 > 2, 交换8和2的位置。
接着再让8和7进行比较， 8 < 7, 交换8和7的位置。
因为9已经是有序区里面的元素了，无须参与第二轮比较，所以第二轮冒泡排序经过6次比较，选出了最大元素—— 8，随之将8算进有序区内。
按照相同的逻辑，我们可以得到：
第三轮冒泡排序结果：
第四轮冒泡排序结果：
第五轮冒泡排序结果：
第六轮冒泡排序结果：
第七轮冒泡排序结果：
第八轮冒泡排序结果：
经过8轮冒泡排序后，元素已经按照从小到大顺序排列在数组内，也可以说有序地排列在有序区内。
由于该排序算法的每一轮要遍历所有元素，轮转的次数和元素数量几乎相同，所以时间复杂度是O（N^2）
冒泡排序是一种稳定排序，也就是说当存在两个相同元素时，比如1, 2, 1, 3, 5.存在相同的两个元素——1，稳定排序说的就是在经历过多次排序，形成有序数列以后，相同元素的相对位置依然未改变。
排序前：1(第一个1), 2, 1(第二个1), 3, 5；
排序后：1(第一个1), 1(第二个1), 2, 3, 5。
排序前的第一个1就是排序后的第一个1；排序前的第二个1也就是排序后的第二个1。没有出现前一个1跑到后面去，后一个1跑到前面去的现象，所以说冒泡排序是一种稳定的排序。
下面是冒泡排序的代码实现：
//冒泡排序（从小到大）
public class Sort1 {
public static void main (String[] args) {
int[] arr = new int[] {5, 8, 6, 3, 9, 2, 1, 7};
sort(arr);
System.out.println("冒泡排序完毕后：" + Arrays.toString(arr));
}
public static void sort (int[] arr) {
for (int i = 0; i < arr.length; i++) { //比较轮次
for (int j = 0; j < arr.length - i - 1; j++) { //每一轮的比较次数
// 交换元素，大的值往后移
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
程序执行结果：
冒泡排序完毕后：[1, 2, 3, 5, 6, 7, 8, 9]
改进：
请大家看一看，后三轮的排序状态。
第六轮冒泡排序结果：
第七轮冒泡排序结果（元素已经有序）：
第八轮冒泡排序结果（元素已经有序）：
没错，后三轮排序的弊端在于，元素已经有序了，然而冒泡排序还在进行比较，这样的比较无疑是浪费时间的。
我再举一个较为极端的例子：我给出一个长度为8的数组：
这个数组，在使用冒泡排序时，第一轮过后，元素已经变得有序：
那么后面的7轮排序其实是在做“无用功”。因此我们要防止这种无意义的比较发生，我们需要对上述冒泡排序代码进行一些改动。
其实改动也比较简单，我们只需要加上一个变量isSorted，来判断元素是否已经有序即可。
改进代码：
//改进冒泡排序（从小到大）
public class Sort1 {
public static void main (String[] args) {
int[] arr = new int[] {5, 8, 6, 3, 9, 2, 1, 7};
sort(arr);
System.out.println("冒泡排序完毕后：" + Arrays.toString(arr));
}
public static void sort (int[] arr) {
for (int i = 0; i < arr.length; i++) { //比较轮次
boolean isSorted = true; //元素是否有序的判断变量
for (int j = 0; j < arr.length - i - 1; j++) { //每一轮的比较次数
// 交换元素，大的值往后移
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isSorted = false; //发生了元素交换，isSorted赋值为false
}
}
if (isSorted) //一轮冒泡排序后，如果发生了交换isSorted为false，否则为true
break; // 如果未发生交换，说明元素有序，直接退出循环，反之进行下一轮
}
}
}
以上便是我对冒泡排序的理解，感谢小伙伴们的阅读！
