冒泡排序，我可以这样学( 二 ) _冒泡排序

文章插图

第六轮冒泡排序结果：

文章插图

第七轮冒泡排序结果：

文章插图

第八轮冒泡排序结果：

文章插图

经过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，否则为truebreak;// 如果未发生交换，说明元素有序，直接退出循环，反之进行下一轮}	}}

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

【冒泡排序，我可以这样学】