数据结构----排序算法之一（冒泡排序及其优化）

2020年7月3日 因为早些时间在准备期末考试，所以在写博客上面没太花心思，队列那一期还是挤时间写的。 就在昨天，这场被誉为在“海里遨游”的线上考试它结束了，可以做自己想做的事咧。这一期就写写有关排序的，估计会有好几期。

关于冒泡排序

什么是冒泡排序？ 它是一种基础的交换排序之所以叫冒泡排序，就是让数值较大的数，像气泡一样，一点一点移向一侧。举个“栗子”。一个数组，里面的值为{5 ， 8 ， 6 ， 3 ， 2}。要想让它变得有序，就要像图片里，两两比较，当一个元素大于右侧相邻元素时，交换他们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。直至最后，数组的最右侧必是这些值中的最大值。 冒泡排序是一种稳定排序，值相等时并不会打乱原本的顺序。由于每次都要遍历所有元素，所以总共遍历（元素数量 - 1）轮，平均时间复杂度时O(n^2)。下面上代码。

第一版的冒泡排序（未优化）

import java.util.Arrays; public class BubbleSort { public static void sort(int []array){ for (int i = 0; i < array.length - 1; i++){ for (int j = 0; j < array.length - i -1; j++){ //中间变量（存较大的值） int temp = 0; if (array[j] > array[j + 1]){ temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } } public static void main(String[] args) { int []array = new int[]{5,8,6,3,2}; sort(array); System.out.println(Arrays.toString(array)); } }

未优化的冒泡排序存在问题：

1.当经过几轮的排序后，数组已经有序了，但仍然还在执行着循环； 2.当后面的元素已经有序了，但每次循环仍会去执行比较。 这样白白增加了工作时间！

最终优化

为了解决上面两个问题，可以参考下面代码，引入判断标记，引入有序区边界。

import java.util.Arrays; public class BubbleSort { /** * 冒泡排序优化 * @param array */ public static void sort(int []array){ for (int i = 0; i < array.length - 1; i++){ //有序标记，每轮初始值为true boolean isSort = true; //无序数列边界，每次比较只需要比到这里 int sortBorder = array.length - 1; for (int j = 0; j < sortBorder; j++){ int temp = 0; if (array[j] > array[j + 1]){ temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; //因为有元素进行交换，所以不是有序，置为false isSort = false; //把无序数列的边界更新为最后一次交换元素的位置 sortBorder = j; } } if (isSort){ break; } } } public static void main(String[] args) { int []array = new int[]{5,8,6,3,2}; sort(array); System.out.println("----排序后----"); System.out.println(Arrays.toString(array)); } }

冒泡排序并不难理解嘛！

结束语

“天再高又怎样，踮起脚尖就更接近阳光。”