冒泡排序，我可以这样学

排序算法有很多，像冒泡排序，选择排序，插入排序，希尔排序，快速排序等等。今天这篇文章呢，我们来聊一聊简单的冒泡排序（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;		// 如果未发生交换，说明元素有序，直接退出循环，反之进行下一轮
		}
	}
}

以上便是我对冒泡排序的理解，感谢小伙伴们的阅读！