排序算法（八）冒泡排序
冒泡排序（Bubble-Sort）是一种最基础的交换排序。冒泡排序的原理：从第一个数开始，依次往后比较，相邻的元素两两比较，根据大小来交换元素的位置，如果前面的数比后面的数大就交换，否则不作处理。这就类似烧开水时，壶底的水泡往上冒的过程。
图解过程
以数组：5, 9, 2, 4, 7为例，按从小到大的方式排序，冒泡排序的过程如下：
第一次循环：多次交换后，将9上浮到最顶处。
第一次循环
第二次循环：多次交换后，将7上浮到最顶处。
第二次循环
可以发现每次循环后，再次循环的次数在递减，因为每次循环后，数目最大的数都被排到最上面的位置，因此接下来接没必要再去比较最顶端的数字了。
代码实现
int[] numbers = {5, 9, 2, 4, 7};
for (int i = 0; i < numbers.length; i++) {
for (int j = 0; j < numbers.length - 1 - i; j++) {
if (numbers[j] > numbers[j+1]) {
int temp = numbers[j];
numbers[j] = numbers[j+1];
numbers[j+1] = temp;
}
}
}
在第三次循环的时候，我们可以发现，数组已经成为有序序列了，无需再继续进行比较操作，
第三次循环
因此可以对冒泡排序进行优化。优化思想为：如果该次循环没有发生一次数的交换，就说明数组已经排好序了，那么后面的循环比较就可以停止了。
代码如下
public int[] sort() {
int[] numbers = {5, 9, 2, 4, 7};
// 设置标志。为true表示在一次循环中有进行交换操作，false则相反
boolean isExchange = true;
for (int i = 0; i < numbers.length; i++) {
// 如果未交换，则跳出循环
if (!isExchange) break;
// 每次循环前将其置为 false
isExchange = false;
for (int j = 0; j < numbers.length - 1 - i; j++) {
if (numbers[j] > numbers[j+1]) {
// 正在进行交换操作，将其置为true
isExchange = true;
int temp = numbers[j];
numbers[j] = numbers[j+1];
numbers[j+1] = temp;
}
}
}
return numbers;
}
然而我们还可以发现，例如当数组：4, 2, 1, 7, 8, 9，一开始循环时，后面三位数已经排好序了，那么我们在循环的时候也就无需去对他们进行对比，解决方法如下
public int[] sort() {
int[] numbers = {4, 2, 1, 7, 8, 9};
// 设置标志。为true表示在一次循环中有进行交换操作，false则相反
boolean isExchange = true;
// 记录最后一次循环的位置
int lastExchange = 0;
// 循环的界限初始化为 numbers.length - 1
int sortBorder = numbers.length - 1;
for (int i = 0; i < numbers.length; i++) {
// 如果未交换，则跳出循环
if (!isExchange) break;
// 每次循环前将其置为 false
isExchange = false;
for (int j = 0; j < sortBorder; j++) {
if (numbers[j] > numbers[j+1]) {
// 正在进行交换操作，将其置为true
isExchange = true;
// 记录位置
lastExchange = j;
int temp = numbers[j];
numbers[j] = numbers[j+1];
numbers[j+1] = temp;
}
}
// 设置循环界限
sortBorder = lastExchange;
}
return numbers;
}
时间复杂度
- 冒泡排序最好的时间复杂度为O(n)，平均时间复杂度为O(n^2)。
- 冒泡排序为稳定排序算法。
