数据结构与算法
Sorting Algorithms:Bubble Sort
1 基本思路
- 该算法对一个数组中的相邻的每一对数字都进行比较
- 假如令大的在前，小的在后，该数组有n个元素,
- 第一次对该数组的所有相邻元素比较，比较完后则会排列出整个数组最小元素放在最后
- 接着第二次只需对剩下的 n-1 个相邻的元素进行比较，排序出第二小的元素，
- 以此类推进行第 3，4，5，6，7…到 n-1 次,
- 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。”每次排序‘浮’出的都是最小的。
2 图示
164a6ebed74469f8.gif
3 算法复杂度分析
| 平均 | 最坏 | 最好 | 稳定性 | 空间复杂度 |
|---|---|---|---|---|
| O(n^2) | O(n^2) | O(n^2) | 稳定 | O(1) |
p.s. 最好情况：即已经数组按顺序排好的情况，加了flag判定后，内循环执行一次即可不再执行
4 代码实现
/**
* Bubble Sort : * 该算法对一个数组中的相邻的每一对数字都进行比较，
* 假如令大的在前，小的在后，该数组有n个元素
* 第一次对该数组的所有相邻元素比较，
* 比较完后则会排列出整个数组最小元素放在最后，
* 接着第二次只需对剩下的 n-1 个相邻的元素进行比较，
* 排序出第二小的元素， * 以此类推进行第 3，4，5，6，7...到 n-1 次
* 因为第 n-1 次排出第二大的元素，自然剩下那个就是最大的元素 *
* “这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。”
* 每次排序‘浮’出的都是最小的 *
* 算法复杂度分析
* 时间复杂度（平均） O(n^2) 外循环n次，内循环m次 m*n
* 时间复杂度（最坏） O(n^2) 外循环n次，内循环m次 m*n
* 时间复杂度（最好） O(n) (即已经数组按需排好的情况，加了flag判定后，内循环执行一次即可不再执行)
* 空间复杂度 O(1)
* 稳定性 稳定
*/
public class BubbleSort {
public static void main(String[] args) {
int[] a = new int[10];
boolean flag = true; //random array
for (int i = 0; i < a.length; i++) {
Random rd = new Random();
a[i] = rd.nextInt(10);
}
System.out.println("Random Array :");
System.out.println(Arrays.toString(a));
System.out.println();
System.out.println("Bubble Sort :");
//冒泡排序开始
// 外循环规定了排序次数，从第1次到第 n-1 次
for (int i = 0; i < a.length - 1 && flag; i++) {
flag = false;
//内循环规定了剩余未排序元素,j是从后往前循环
for (int j = a.length - 2; j >= i; j--) {
//前一个大于后一个，则交换
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag = true;
}
}
}
// 另一种形式
// This might be easy for you to understand.
for (int i = 0; i < a.length - 1 && flag; i++) {
flag = false;
for (int j = 0; j < a.length - i - 1; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag = true;
}
}
}
System.out.println(Arrays.toString(a));
}
}
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
