交换排序算法之冒泡排序数据结构与算法

八种排序算法可以按照如图分类，本文主要介绍冒泡排序。

文章图片

交换排序所谓交换，就是序列中任意两个元素进行比较，根据比较结果来交换各自在序列中的位置，以此达到排序的目的。

冒泡排序冒泡排序是一种简单的交换排序算法，以升序排序为例，其核心思想是：

从第一个元素开始，比较相邻的两个元素。如果第一个比第二个大，则进行交换。
轮到下一组相邻元素，执行同样的比较操作，再找下一组，直到没有相邻元素可比较为止，此时最后的元素应是最大的数。
除了每次排序得到的最后一个元素，对剩余元素重复以上步骤，直到没有任何一对元素需要比较为止。

文章图片

用 Java 实现的冒泡排序如下

/** * 冒泡排序常规版 * * 没有经过任何优化操作的版本 * @param arr 待排序的整型数组 * @return 比较次数 */ public static int bubbleSortOpt1(int[] arr) {if (arr == null) { throw new NullPointerException(); } else if (arr.length < 2) { return 0; }int temp; int count = 0; for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } count++; } } return count; }

算法优化现在有个问题，假如待排序数组是 2、1、3、4、5 这样的情况，按照上述代码实现，第一次循环即可得出正确结果。但循环并不会停止，而是继续执行，直到结束为止。显然，之后的循环遍历是没有必要的。
为了解决这个问题，我们可以设置一个标志位，用来表示当前次循环是否有交换，如果没有，则说明当前数组已经完全排序。

/** * 冒泡排序优化第一版 * * 设置了一个标志位，用来表示当前次循环是否有交换，如果没有，则说明当前数组已经完全排序 * @param arr 待排序的整型数组 * @return 比较次数 */ public static int bubbleSortOpt2(int[] arr) {if (arr == null) { throw new NullPointerException(); } else if (arr.length < 2) { return 0; }int temp; int count = 0; for (int i = 0; i < arr.length - 1; i++) { int flag = 1; for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; flag = 0; } count++; } // 没有发生交换，排序已经完成 if (flag == 1) { return count; } } return count; }

算法还可以再优化，比如 3、4、2、1、6、7、8 这个数组，第一次循环后，变为 3、2、1、4、6、7、8 的顺序，我们发现，1 之后的 4 、6、7、8 已经有序了，第二次循环就没必要对后面这段再遍历比较。
假设一次循环后数组第 i 个元素后所有元素已经有序，优化目标就是下次循环不再花费时间遍历已经有序的部分。关键在于如何定位 i 这个分界点，其实并不难，可以想象，由于 i 之前的元素是无序的，所以一定有交换发生，而 i 之后的元素已经有序，不会发生交换，最后发生交换的地点，就是我们要找的分界点。

/** * 冒泡排序优化第二版 * * 定位最后发生交换的分界点，之后的元素无需遍历。 * @param arr 待排序的整型数组 * @return 比较次数 */ public static int bubbleSortOpt3(int[] arr) {if (arr == null) { throw new RuntimeException(); } else if (arr.length < 2) { return 0; }int temp; int count = 0; int len = arr.length - 1; for (int i = 0; i < len; i++) { // 记录最后一次交换位置 int lastChange = 0; for (int j = 0; j < len; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; // 每交换一次更新一次 lastChange = j; } count++; } // 没有发生交换，排序已经完成 if (lastChange == 0) { return count; } len = lastChange; } return count; }

我们同样可以用 lastChange 来判断当前次循环是否发生交换，这样就结合了第一种优化方案了。各位可以自行设计测试数据，看看返回的比较次数大小是否减少。

性能分析冒泡排序算法是稳定的，因为相同元素的前后顺序并不会变。
分析最优版本算法，最好的情况是一开始已经排好序，那就没必要交换了，直接返回，此时只走了外层的第一次循环，最优时间复杂度为 O(n)。
最坏的情况当然是数组是逆序的，这样里外两层循环都走了遍，最坏时间复杂度为 O( n^2 )。
【交换排序算法之冒泡排序】空间复杂度则是用于交换的临时变量，至于标志位和其他的因算法的不同实现有差异。