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

冒泡排序的第一种写法

代码如下：

public static void bubbleSort(int[] arr) { 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]) { // 如果左边的数大于右边的数，则交换，保证右边的数字最大 arr[j + 1] = arr[j + 1] + arr[j]; arr[j] = arr[j + 1] - arr[j]; arr[j + 1] = arr[j + 1] - arr[j]; } } } }

最外层的 for 循环每经过一轮，剩余数字中的最大值就会被移动到当前轮次的最后一位，中途也会有一些相邻的数字经过交换变得有序。总共比较次数是(n-1)+(n-2)+(n-3)+…+1。

这种写法相当于相邻的数字两两比较，并且规定：“谁大谁站右边”。经过 n-1 轮，数字就从小到大排序完成了。整个过程看起来就像一个个气泡不断上浮，这也是“冒泡排序法”名字的由来。

其中，我们在交换两个数字时使用了一个小魔术：没有引入第三个中间变量就完成了两个数字的交换。这个交换问题曾经出现在大厂面试题中，感兴趣的读者可以细品一下。除了这种先加后减的写法，还有一种先减后加的写法：

arr[j + 1] = arr[j] - arr[j + 1]; arr[j] = arr[j] - arr[j + 1]; arr[j + 1] = arr[j + 1] + arr[j];

这两种交换数字的方式和我们平时常用的写法是等价的（不考虑数字越界的情况）：

int temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp;