经典算法题型之排序算法（三）

冒泡排序的第二种写法

第二种写法是在第一种写法的基础上改良而来的：

public static void bubbleSort(int[] arr) { // 初始时 swapped 为 true，否则排序过程无法启动 boolean swapped = true; for (int i = 0; i < arr.length - 1; i++) { // 如果没有发生过交换，说明剩余部分已经有序，排序完成 if (!swapped) break; // 设置 swapped 为 false，如果发生交换，则将其置为 true swapped = false; for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { // 如果左边的数大于右边的数，则交换，保证右边的数字最大 int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; // 表示发生了交换 swapped = true; } } } }

最外层的 for 循环每经过一轮，剩余数字中的最大值仍然是被移动到当前轮次的最后一位。这种写法相对于第一种写法的优点是：如果一轮比较中没有发生过交换，则立即停止排序，因为此时剩余数字一定已经有序了。

看下图演示：

图中可以看出：

• 第一轮排序将数字 6 移动到最右边；
• 第二轮排序将数字 5 移动到最右边，同时中途将 1 和 2 排了序；
• 第三轮排序时，没有发生交换，表明排序已经完成，不再继续比较。