- **介绍 **
冒泡排序法又称为交换排序，其比较方式由第一个元素开始，比较相邻元素大小，若大小顺序有误，则对调后再进行下一个元素的比较。如此扫描过一次后就可确保最后一个元素是位于正确的顺序。接着再进行第二次扫描，直到完成所有元素的排序关系为之。 -
演示
代码如下：
private static void bubbleSort() {
int data[] = {9, 6, 3, 2, 4, 5, 1, 8, 7};
int i, j, tmp;
for (i = data.length - 1; i > 0; i--) {
for (j = 0; j < i; j++) {
if (data[j] > data[j + 1]) {
tmp = data[j];
data[j] = data[j + 1];
data[j + 1] = tmp;
}
}
}
}
打印结果：
冒泡排序打印信息.png
-
分析
- 最坏情况及平均情况均需比较n(n-1)/2次；时间复杂度为O(n²)，最好情况只需要完成一次扫描，发现没有做交换的操作则表示排序已经完成，所以只做了n-1次比较，是复杂度为O(n)。
- 由于冒泡排序为相邻两者相互比较对调，并不会更变其原本排序的顺序，所以是稳定排序法。
- 只需一个额外的空间，所以空间复杂度为最佳。
- 冒泡排序法适用于数据量小或者有部分数据已经排序过的情况。
-
优化
通过上边的演示可以看出冒泡排序法有一个缺点，就是不管数据是否已经排序完成都会固定执行n(n-1)/2次，所以需要在排序中增加标记来提前中断程序，以此提高执行效率，代码如下：
private static void bubbleSort() {
int data[] = {9, 6, 3, 2, 4, 5, 1, 8, 7};
int i, j, tmp, flag;
for (i = data.length - 1; i > 0; i--) {
flag = 0; // flag 用来判断是否有执行
for (j = 0; j < i; j++) {
if (data[j] > data[j + 1]) {
tmp = data[j];
data[j] = data[j + 1];
data[j + 1] = tmp;
flag++; // 如果有执行过交换，则flag不为0
}
}
if (flag == 0){
break; // 如果没有发生过交换就退出
}
}
}
-
后记
通过比较会发现一个有意思的现象，冒泡排序每次扫描都会确定后边的元素为目标顺序，而选择排序每次都扫描都会确定前边的元素为目标顺序。
