冒泡排序是学习排序算法时最先遇到的算法,其形象名称和排序过程最容易记住,很多人会在面试时谈论起,真正理解了冒泡排序算法才能更深入地学习其他排序算法。
详细描述
冒泡排序是一种交换排序,基本思想是在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。
即每当两个相邻的数比较后发现它们的顺序与排序要求相反时,就将它们互换。
冒泡排序详细的执行步骤如下:
- 从第一个元素开始,比较相邻的元素,如果前一个比后一个大,就交换它们两个;
- 从前往后,对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素就会是最大的数;
- 将这次找出的最大元素放在最后一个元素位置上,然后针对除这个最大元素以外的其他所有元素重复以上 1~2 步骤;
- 重复以上步骤,直到最后第一个元素和第二个元素完成比较、交换,则排序完成。
算法图解

问题解疑
冒泡排序是原地排序算法吗?
冒泡排序是一个原地排序算法,过程只涉及相邻数据的交换操作,只需要常量级的临时空间,它的空间复杂度是 $O(1)$。
冒泡排序是稳定的排序算法吗?
为了保证冒泡排序算法的稳定性,当有相邻的两个元素大小相等时可以不做交换,相同大小的数据在排序前后不会改变顺序,所以冒泡排序是稳定的排序算法。
冒泡排序的时间复杂度是多少?
使用最优时间复杂度解法,原序列是有序时的时间复杂度是 $O(n)$;最坏情况时间复杂度为 $O(n^2)$;平均时间复杂度是 $O(n^2)$。
代码实现
排序接口
1
2
3
4
5
6
7
8
| package cn.fatedeity.algorithm.sort;
/**
* 排序接口
*/
public interface Sort {
int[] sort(int[] numbers);
}
|
排序抽象类
1
2
3
4
5
6
7
8
9
10
11
12
| package cn.fatedeity.algorithm.sort;
/**
* 排序抽象类
*/
public abstract class AbstractSort implements Sort {
protected void swap(int[] numbers, int src, int target) {
int temp = numbers[src];
numbers[src] = numbers[target];
numbers[target] = temp;
}
}
|
冒泡排序类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| package cn.fatedeity.algorithm.sort;
/**
* 冒泡排序类
*/
public class BubbleSort extends AbstractSort {
@Override
public int[] sort(int[] numbers) {
if (numbers.length <= 1) {
return numbers;
}
for (int i = 0; i < numbers.length - 1; i++) {
boolean doSwap = false;
for (int j = 0; j + 1 < numbers.length - i; j++) {
if (numbers[j] > numbers[j + 1]) {
this.swap(numbers, j, j + 1);
doSwap = true;
}
}
// 优化基础冒泡排序的步骤
if (!doSwap) {
// 如果遍历整个序列无需交换,则表示整个序列已经完全有序
return numbers;
}
}
return numbers;
}
}
|