前言
冒泡排序(Bubble Sort
),在概念上是最简单的排序算法,但效率也不高。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序
或降序
排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
排序思路
依次比较相邻的两个元素:
- 当一个元素大于右侧相邻元素时,交换它们的位置;
- 当一个元素小于或等于右侧相邻元素时,位置不变;
- 重复步骤1和步骤2,直至全部排序完成。
代码实现
通常来说,冒泡排序有三种写法:
第一种写法
第一种就是最原始的写法,使用双循环来进行排序:外部循环控制所有的回合,内部循环代表每一轮的冒泡处理,先进行元素比较,再进行元素交换。
public static void sort1(int array[]) {
int tmp = 0;
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
// 左侧元素大于右侧元素,则交换
if (array[j] > array[j + 1]) {
tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
}
}
System.out.println("第" + (i+1) + "轮:" + Arrays.toString(array));
}
}
最外层的 for 循环每经过一轮,剩余数字中的最大值就会被移动到当前轮次的最后一位,中途也会有一些相邻的数字经过交换变得有序。总共比较次数是(n-1)+(n-2)+(n-3)+…+1。
其中,关于两个数字的交换,不使用中间变量 tmp 也可以完成
由于该排序算法的每一轮要遍历所有元素,轮转的次数和元素数量相当,所以时间复杂度是O(N²)
。但这种写法有待优化,通过输出语句可以观察每一轮的排序结果:
经过第4轮排序后,整个数列已经是有序的了;可是排序算法仍然“兢兢业业”地继续执行第5轮排序,直到第8轮。
这种情况下,如果能判断出数列已经有序,并且做出标记,剩下的几轮排序就可以不必执行,提早结束工作。
第二种写法
第二种写法就是在第一种的基础上进行优化,利用布尔变量isSorted
作为标记。如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,说明数列已然有序,直接跳出大循环。
public static void sort2(int array[]) {
int tmp = 0;
for (int i = 0; i < array.length; i++) {
//有序标记,每一轮的初始是true
boolean isSorted = true;
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j+ 1]) {
tmp = array[j];
array[j] = array[j+ 1];
array[j+ 1] = tmp;
//有元素交换,所以不是有序,标记变为false
isSorted = false;
}
}
if (isSorted){
break;
}
System.out.println("第" + (i+1) + "轮:" + Arrays.toString(array));
}
}
第三种写法
解决“整体有序后依然排序”的问题后,其实,还存在“部分有序后依然排序”的问题。观察每一轮的排序结果,可知
- 第1轮排序后,数组内最大的元素“99”排在了数组的最后;
- 第2轮排序后,第二大的元素“88”排在了数组的倒数第二;
- 第3轮排序后,第三大的元素“77”排在了数组的倒数第三;
......
每完成一轮排序,数组内右侧的有序元素不断增加,形成一个有序区。但是即使右侧的元素是有序的,每一次内部循环都重复比较了。按照现有的逻辑,有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1,第二轮排序过后的有序区长度是2......实际上,数列真正的有序区可能会大于这个长度,例如,部分有序的数组:[33, 44, 55, 66, 11, 22, 99, 88, 77]。这个数组,仅在第2轮排序,后面5个元素就已经是有序的了,因此后面的许多次元素比较是没有意义的。
如何避免这种不必要的比较呢?可以在每一轮排序的最后,记录下最后一次元素交换的位置,那个位置也就是无序数列的边界,再往后就是有序区了。第三种写法是在第二种写法的基础上进一步优化:
public static void sort3(int array[]) {
int tmp = 0;
//记录最后一次交换的位置
int lastExchangeIndex = 0;
//无序数列的边界,每次比较只需要比到这里为止
int sortBorder = array.length - 1;
for (int i = 0; i < array.length;i++) {
//有序标记,每一轮的初始是true
boolean isSorted = true;
for (int j = 0; j < sortBorder; j++) {
if (array[j] > array[j + 1]) {
tmp = array[j];
array[j] = array[j + 1];
array[j + 1] = tmp;
//有元素交换,所以不是有序,标记变为false
isSorted = false;
//把无序数列的边界更新为最后一次交换元素的位置
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
if (isSorted){
break;
}
System.out.println("第" + (i+1) + "轮:" + Arrays.toString(array));
}
}
sortBorder
就是无序数列的边界。每一轮排序过程中,sortBorder
之后的元素就完全不需要比较了,肯定是有序的,这样又提高了排序效率。
动画演示
演示动画来自于visualgo
如图所示,未排序的元素为浅蓝色,正在对比交换的元素为深绿色,已经有序的元素标记为橙黄色。
复杂度分析
一般来说,数组中有N个数据项,则第一轮排序中有(N-1)次比较,第二轮中有(N-2)次比较,如此类推,不难得出它的求和公式:(N-1)+(N-2)+(N-3)+...+1 = N *(N-1)/2。所以,算法做了约(N²/2)次比较(可以忽略-1,影响不大,尤其当 N 很大时),交换的次数一般少于比较的次数。最好的情况是数据是正序的,那么只需要比较不需要交换;最坏的情况是数据是逆序的,那么每次比较都需要交换;而在一般情况下,数据是随机的,大概只有一半左右的数据需要交换,则交换的次数为(N²/4)。
交换和比较的次数都与 N² 都成正比,由于常数项(1/2、1/4)可以忽略,那么平均时间复杂度为O(N²)
。
参考
程序员小灰
Github
data-flair
LeetCode
冒泡排序升级版就是鸡尾酒排序。