前言
对于Java程序员来说，一般对于算法没有什么要求，但是有一个算法除外——排序算法。排序算法不仅在日常开发中经常用到，还是面试中几乎必问的题目，并且通常是以“手写代码”的形式出现，因此掌握好排序算法是对每一个程序员的最基本要求。
谈到排序算法，第一个浮现在我们脑中的一定是“冒泡排序”。“冒泡排序”由于较简单的过程，得到大多数程序员的“厚爱”，本文将简单的介绍排序算法的整个过程。
冒泡排序算法的运作如下：
1. 比较两个相邻的数，如果前面的数大于后面的数，则将这两个数交换位置。第一次遍历后，最大的数会被放到数组的最后位置，即array[length - 1]。
2. 第二次遍历时跳过最后一个元素，因为该元素通过第一次遍历已经确定是最大值。
3. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
下面通过一个例子来看看冒泡排序是怎么工作的。红色的数为正在比较的数，原数组如下。
0 |
1 |
2 |
3 |
19 |
15 |
37 |
12 |
第一次循环：
1.首先比较array[0]和arary[1]，即19和15；因为19 > 15，因此交换两个数的位置，交换完的数组如下。
0 |
1 |
2 |
3 |
15 |
19 |
37 |
12 |
比较和交换对应的代码如下：
if (array[j] > array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; }
2.接着比较array[1]和array[2]，即19和37；因为19 < 37，因此两个数的位置不变，如下。
0 |
1 |
2 |
3 |
15 |
19 |
37 |
12 |
3.最后比较array[2]和array[3]，即37和12；因为37 > 12，因此交换两个数的位置，交换完的数组如下。
0 |
1 |
2 |
3 |
15 |
19 |
12 |
37 |
至此第一次循环结束，由于是相邻两数比较，可以看到第一次循环我们只需要进行3次比较，即：(arary.length - 1) 次。
第二次循环：
1.首先比较array[0]和arary[1]，即15和19；因为15 < 19，因此两个数的位置不变，如下。
0 |
1 |
2 |
3 |
15 |
19 |
12 |
37 |
2.接着比较array[1]和array[2]，即19和12；因为19 > 12，因此交换两个数的位置，交换完的数组如下。
0 |
1 |
2 |
3 |
15 |
12 |
19 |
37 |
3.由于array[3]经过第一次循环后，必然大于前面所有的数，因此不再进行比较，则第二次循环结束。
在第二次循环中，由于已经结束的循环次数为1，因此有1个数已经确定位置无需再比较，因此我们比较的次数只有2次，比较次数可以抽象成以下公式：
array.length - 1 - (已经结束的循环次数)
第三次循环：
1.首先比较array[0]和arary[1]，即15和12；因为15 > 12，因此交换两个数的位置，交换完的数组如下。
0 |
1 |
2 |
3 |
12 |
15 |
19 |
37 |
2.由于array[2]经过第二次循环后，必然大于前面所有的数，因此不再进行比较，则第三次循环结束。
第四次循环：
在经过第三次循环后，array[1]~array[3]均回到属于他们的正确位置，因此此时array[0]必然也在属于它的正确位置，因此无需进行第四次循环。
最后我们通过以下动图来看冒泡排序的整个过程，图中浅蓝色的柱子为还未在正确位置的数，绿色的两个柱子为正在比较的数，橘黄色的柱子为已经在正确位置的数。
通过上文例子无需进行第四次循环可以知道，循环的次数为：数组元素的个数 - 1，则循环次数可以表示成如下：
for (int i = 0; i < array.length - 1; i++)
在上文例子的第二次循环中，我们将每次循环的比较次数抽象成以下公式：
array.length - 1 - (已经结束的循环次数)
用具体的例子展示，每次循环需要比较的次数如下：
第一次循环：array.length - 1 - 0 第二次循环：array.length - 1 - 1 第三次循环：array.length - 1 - 2 ...
通过上面的两个公式可以观察到，“已经结束的循环次数” 刚好可以使用上面的最外层循环的变量 i 进行代替，即每次循环的比较次数可以用如下公式：
for (int j = 0; j < array.length - i - 1; j++)
结合两个公式的代码，还有上面的比较和交换代码，冒泡排序整理成代码如下：
public static void bubbleSort(int[] array) { if (array == null || array.length == 0) { return; } for (int i = 0; i < array.length - 1; i++) { for (int j = 0; j < array.length - i - 1; j++) { if (array[j] > array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } }
在通常情况下。冒泡排序的比较次数 = (n - 1) + (n - 2) + ... + 2 + 1，即：n * (n - 1) / 2，所以冒泡排序的时间复杂度为：O(n^2)。
由于冒泡排序的时间复杂度为：O(n^2)。因此，在进行量比较大的排序时，最好不要采用冒泡排序。经过简单的测试，在1000个数字以内的排序，用冒泡排序是可以接受的。1000个随机数使用冒泡排序耗时一般在5毫秒以内，但是当数字个数达到10000个时，耗时会达到100+毫秒，简直是灾难。
对排序算法熟悉的人应该知道，冒泡排序最优情况的时间复杂度是：O(n)，怎么得出来的了？通过上文的代码是无法达到O(n)的，需要对上文的代码进行一点点的优化，优化后的代码如下。
public class BubbleSort { public static void bubbleSort(int[] array) { if (array == null || array.length == 0) { return; } for (int i = 0; i < array.length - 1; i++) { // 当次循环是否发生元素交换 boolean isSwap = false; for (int j = 0; j < array.length - i - 1; j++) { if (array[j] > array[j + 1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; isSwap = true; } } // 如果当次循环没有发生元素交换, 则数组已经排好序 if (!isSwap) { return; } } } }
如果array数组本来就是有序的，则第一次循环结束后由于没有元素交换，会直接return，此时的时间复杂度即为：O(n)。
