如果需要查看排版好看的请搜索微信公众号放开我我还能学
前言
这次我们介绍交换类排序中的冒泡排序，和简单插入排序相似，冒泡排序虽然时间复杂度也是O(n^2)，但是对于有序数组的排序，时间复杂度也可以降为O(n)，效率是比较高的。
冒泡排序
对数组[1, 4, 3, 2, 5, 6, 7, 8]从小到大排序，使用冒泡排序步骤如下：
- 依次比较相邻元素的大小。
- 如果前面的数据大于后面的数据，就交换这两个数据，然后向右移动一步，接着比较。经过第一轮的多次比较交换后，最大的数据就移动到了最后。
- 以此类推，经过 n 轮循环，数组就排序好了。
下图展示了冒泡排序的过程：
冒泡排序代码：
<code>public static void sort(Comparable[] arr) { int n = arr.length; for (int i = n; i > 0; i--) { for (int j = 1; j < i; j++) { if (arr[j - 1].compareTo(arr[j]) > 0) { swap(arr, j - 1, j); } } }}private static void swap(Object[] arr, int i, int j) { Object t = arr[i]; arr[i] = arr[j]; arr[j] = t;}/<code>优化1
如果对于一个有序的数组，使用上述冒泡排序的话，同样会执行n(n-1)/2次。实际上，在内循环中每一次比较只要没有发生逆序，即元素之间进行交换，那么就说明数组已经有序，这时已经可以退出程序了。
优化思路就是设置一个交换标志swapped，只要发生了交换，就让swapped = true，外部循环判断swapped是否为true，不是就结束程序，说明排序完成。
下面展示了优化思路的过程：
优化代码：
<code>public static void sort(Comparable[] arr) { int n = arr.length; boolean swapped = false; do { swapped = false; for (int i = 1; i < n; i++) { if (arr[i - 1].compareTo(arr[i]) > 0) { swap(arr, i - 1, i); swapped = true; } } // 每一次for循环将最大的元素放在了最后的位置 // 所以下一次排序, 最后的元素可以不再考虑，n-- n--; } while (swapped); }private static void swap(Object[] arr, int i, int j) { Object t = arr[i]; arr[i] = arr[j]; arr[j] = t;}/<code>优化2
在上述优化的基础上，我们还可以进一步优化。
对于数组：[1, 4, 3, 2, 5, 6, 7, 8]，按照上面的优化思路，我们在第一轮比较时，需要让5, 6, 7, 8比较，第二轮比较时，需要让5, 6, 7比较，然而它们都是有序的排列，因此，我们是否能减少这些不必要的比较呢？答案是可以的。
优化思路就是每一轮循环完后，更新n的值，更新为最后一次交换的位置，这样，在此之后的元素都已经是有序的了，那么下次循环中就不用再比较了。
下图展示了优化思路的过程：
优化代码：
<code>public static void sort(Comparable[] arr) { int n = arr.length; int newn; do { newn = 0; for (int i = 1; i < n; i++) { if (arr[i - 1].compareTo(arr[i]) > 0) { swap(arr, i - 1, i); // 记录最后一次的交换位置，在此之后的元素都是已经有序的，因此下一轮扫描中不再考虑 newn = i; } } n = newn; } while (newn > 0);}private static void swap(Object[] arr, int i, int j) { Object t = arr[i]; arr[i] = arr[j]; arr[j] = t;}/<code>
分享到:
閱讀更多 放開我我還能學 的文章
