从冒泡排序开始

冒泡排序（bubble sort）在排序算法中应该算是比较经典也比较简单的一个了，咱们就直入正题吧。

冒泡排序思想

其实它的名称都已经够直白了对吧，就是“冒泡”嘛。但是具体是怎么“冒”的呢？就是从数组中第一个位置开始，相邻元素两两比较大小，如果左边的元素大于右边的元素，则交换两元素的位置，否则，就保持它们在数组中的位置不变；然后再继续比较接下来相邻两元素的大小。

这样在经过每一轮比较和交换之后，最大的数字就会被移动到数组的最右边。类比一下汽水中的小气泡，如果把数组的左边看作汽水的瓶底，右边看作汽水的瓶口，数组中最大的数字每一轮都会像小气泡一样浮到了最上面，是不是裸眼3D效果都已经出来了。

接下来就用个简单的demo来演示一下整个过程吧。待排序数组如下：

2

5

4

8

7

9

1

6

3

第一轮比较和交换的详细过程为：
（1）2 < 5，保持不变；5 > 4，交换位置

2

4

5

8

7

9

1

6

3

（2）5 < 8，保持不变；8 > 7，交换位置

2

4

5

7

8

9

1

6

3

（3）8 < 9，保持不变；9 > 1，交换位置

2

4

5

7

8

1

9

6

3

（4）9 > 6，交换位置

2

4

5

7

8

1

6

9

3

（5）9 > 3，交换位置

2

4

5

7

8

1

6

3

9

至此，第一轮比较结束，可以发现，数组中的最大值 9 已经位于数组末尾。

后续的比较和交换过程与第一轮是一样的，就不赘述了，这里直接给出所有轮次的结果如下：

2	4	5	7	8	1	6	3	9
2	4	5	7	1	6	3	8	9
2	4	5	1	6	3	7	8	9
2	4	1	5	3	6	7	8	9
2	1	4	3	5	6	7	8	9
1	2	3	4	5	6	7	8	9
1	2	3	4	5	6	7	8	9
1	2	3	4	5	6	7	8	9

冒泡排序代码

/**
 * bubbleSort
 * @param data 待排序数组
 */
private int[] bubbleSort(int[] data) {
  // swap 时用到的临时变量
  int temp;
  for (int i = 0; i < data.length - 1; i++) {
    for (int j = 0; j < data.length - 1 - i; j++) {
      if (data[j] > data[j + 1]) {
        // swap
        temp = data[j];
        data[j] = data[j + 1];
        data[j + 1] = temp;
      }
    }
  }
  return data;
}

冒泡排序优化

经过前面的介绍，冒泡排序看起来还是挺简单的对吧，是的，但是一定程度上很简单也就意味着很粗暴，其实对于上个版本的实现来说，还是有很大的优化空间的。

仍然以上面的demo为例，我们直接去看所有轮次的结果，会发现其实在第六轮的时候数组已经排好序了，但是程序还是会兢兢业业的去执行第七轮和第八轮，所以这就是一个可以优化的点。

具体在代码优化实现上，我们可以加一个标志位来标记数组是否已经有序（或者也可以说，是用来标记数组中元素是否进行过交换）。

冒泡排序优化代码

/**
 * bubbleSort优化
 * @param data 待排序数组
 * 如果某一轮已经有序，则提前结束
 */
public int[] bubbleSort(int[] data) {
  int temp;
  // 标记是否有序
  boolean isSorted;
  for (int i = 0; i < data.length - 1; i++) {
    // 每一轮开始 isSorted 初始值都置为 true
    isSorted = true;
    for (int j = 0; j < data.length - 1 - i; j++) {
      if (data[j] > data[j + 1]) {
        // swap
        temp = data[j];
        data[j] = data[j + 1];
        data[j + 1] = temp;
        // 如果进行了交换，意味着数组还不是有序的，isSorted 置为 false
        isSorted = false;
      }
    }
    if (isSorted) {
      break;
    }
  }
  return data;
}

冒泡排序再优化

这里说冒泡排序还可以再优化，针对的是一种特殊的情况来说的。这种情况就是给定的待排序数组前半段是无序的，后半段是有序的。

再用个简单的demo来演示一下这种情况。待排序数组如下：

4

3

2

1

5

6

7

8

9

第一轮比较和交换的详细过程为：
（1）4 > 3，交换位置

3

4

2

1

5

6

7

8

9

（2）4 > 2，交换位置

3

2

4

1

5

6

7

8

9

（3）4 > 1，交换位置

3

2

1

4

5

6

7

8

9

（4）4 < 5，保持不变；5 < 6，保持不变；6 < 7，保持不变；7 < 8，保持不变；8 < 9，保持不变 至此，第一轮比较结束。

后续的比较和交换过程与第一轮是一样的，就不赘述了，这里可以发现一个问题：其实数组后半段已经是有序的了，但是每一轮还是会再去比较大小，其实这是没有必要的。所以这也是一个可以优化的点。

具体在代码优化实现上，我们可以维护一个边界位置，在该边界位置前半段是无序数组，后半段是有序数组，在内循环中，只需要比较到该边界的位置即可。

冒泡排序再优化代码

/**
 * bubbleSort优化
 * @param data 待排序数组
 * 每一轮排序后，记录最后一次元素交换的位置，该位置即为无序数组和有序数组的边界位置
 */
private int[] bubbleSort(int[] data) {
  int temp;
  boolean isSorted;
  // 每次交换的位置
  int lastChangeIndex = 0;
  // 无序数组和有序数组的边界，内循环中每次只需比较到这里为止，第一轮边界值为数组最后一个值
  int sortBorder = data.length - 1;
  for (int i = 0; i < data.length - 1; i++) {
    isSorted = true;
    for (int j = 0; j < sortBorder; j++) {
      if (data[j] > data[j + 1]) {
        // swap
        temp = data[j];
        data[j] = data[j + 1];
        data[j + 1] = temp;
        isSorted = false;
        // lastChangeIndex 更新为每次交换的位置
        lastChangeIndex = j;
      }
    }
    // 此时 lastChangeIndex 表示每一轮中最后一次交换的位置，即此时无序数组和有序数组的边界值，将它赋值给 sortBorder
    sortBorder = lastChangeIndex;
    if (isSorted) {
      break;
    }
  }
  return data;
}

复杂度和稳定性分析

1. 时间复杂度

• 最优时间复杂度：O(n)

  • 在最理想的情况下，即待排序数组本来就是有序的，用上述冒泡排序优化代码来实现，其实我们只需要遍历 1 次就可以了。假定待排序数组长度为 n，那么最优时间复杂度即为 O(n)。

• 最坏时间复杂度：O(n^2)

• 平均时间复杂度：O(n^2)

2. 空间复杂度：O(1)

• 整个过程都是原地排序，并没有用到其它辅助的空间。

3. 冒泡排序是一种稳定排序。

这里牵扯到两个概念，也在这里顺便介绍一下：

原地排序：在排序过程中不需要辅助空间，直接利用原来待排序数组的存储空间来进行比较和交换。

稳定性：如果待排序数组中存在相同的元素，且在排序后这些相同元素之间的顺序与排序前的顺序一致，则称这种排序为稳定性排序；否则，则为不稳定性排序。

---