什么是冒泡排序
冒泡排序是一种基础的交换排序，其思想是，把相邻的元素两两比较，当一个元素大于右侧相邻的元素时，交换它们的位置：当一个元素小于或等于右侧的元素时，位置不变。
冒泡排序是一种稳定排序，值相等的元素并不会打乱原有的顺序，由于该排序算法的每一轮都要遍历元素，总共遍历（元素数量 - 1）轮，所以平均时间复杂度是O(n^2)。
工欲善其事，必先利其器
在讲述冒泡排序之前，我们先来搭建一个简单的排序算法编写的环境，这个环境可以帮助我们更加方便地编写和测试排序算法。
SortUtils
一个排序算法的工具类，其中包含了排序算法编写和测试的一些基本操作。
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
| public class SortUtils {
public static int[] generateRandomArray(int size, int rangeL, int rangeR) {
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = (int) (Math.random() * (rangeR - rangeL + 1)) + rangeL;
}
return arr;
}
public static int[] generateAlmostOrderlyArray(int size, int swapTimes) {
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = i;
}
for (int i = 0; i < swapTimes; i++) {
int index1 = (int) (Math.random() * size);
int index2 = (int) (Math.random() * size);
swap(arr, index1, index2);
}
return arr;
}
public static boolean isOrderly(int[] arr) {
return isOrderAsc(arr) || isOrderDesc(arr);
}
private static boolean isOrderAsc(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
return false;
}
}
return true;
}
private static boolean isOrderDesc(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
if (arr[i] > arr[i - 1]) {
return false;
}
}
return true;
}
public static int[] copyIntArray(int[] arr) {
int[] copyArr = new int[arr.length];
System.arraycopy(arr, 0, copyArr, 0, arr.length);
return copyArr;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void printArray(int[] arr) {
for (int i : arr) {
System.out.print(i + "\t");
}
System.out.println();
}
}
|
Sort函数式接口
一个基于 JDK8 Lambda 特性的函数式接口，所以该排序算法环境的搭建基于 JDK8+ 的版本。
1
2
3
4
5
6
7
8
9
10
| @FunctionalInterface
public interface Sort {
void sort(int[] arr);
}
|
SortRunner
SortRunner 中有用于运行 Sort 函数式接口的方法，可以在该类的方法下编写一些特定的操作，用于辅助排序算法编写和测试。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| public class SortRunner {
public static void run(int[] arr, Sort sort) {
System.out.print("数组排序前：");
SortUtils.printArray(arr);
long startTime = System.currentTimeMillis();
sort.sort(arr);
long endTime = System.currentTimeMillis();
if (SortUtils.isOrderly(arr)) {
System.out.print("数组排序后：");
SortUtils.printArray(arr);
System.out.println("数组排序所需时间为：" + (endTime - startTime) + "毫秒");
} else {
System.out.println("数组排序失败");
}
System.out.println();
}
}
|
冒泡排序
普通冒泡排序
普通的冒泡排序是把相邻的元素两两比较，直到所有元素都比较结束为止
1
2
3
4
5
6
7
8
9
10
11
| System.out.println("普通冒泡排序");
SortRunner.run(SortUtils.generateRandomArray(10000, 100, 100000),
(arr) -> {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
SortUtils.swap(arr, j, j + 1);
}
}
}
});
|
这是最为常见的冒泡排序，编写简单，易于理解，但是在一些特殊情况下，可能会浪费一些性能。
比如排序到 n - i 轮的时候，这是遍历数组，发现数组已经有序了，剩下的 i -1 轮其实已经可以不进行遍历了。
所以我们可以对冒泡排序进行一些优化。
布尔类型变量判断有序
这种冒泡排序的思想是，在每一轮遍历数组前，设置一个变量用于标识数组有序，如果在该轮中，数组相邻的元素之间发生了交换，则说明此时数组仍处于无序状态，反之则有序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
System.out.println("布尔类型变量判断有序优化冒泡排序");
SortRunner.run(SortUtils.generateRandomArray(10000, 100, 100000),
(arr) -> {
for (int i = 0; i < arr.length - 1; i++) {
boolean isSorted = true;
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
SortUtils.swap(arr, j, j + 1);
isSorted = false;
}
}
if (isSorted) {
break;
}
}
});
|
无序边界值
布尔类型变量判断有序优化冒泡排序，本质上是减少了冒泡排序的轮数，可以让冒泡排序轮询 <= n - 1 次，但是对于每一轮交换的元素个数，依然是固定的。
但是有的时候，每一轮交换元素的时候，可能交换 n - i 次，数组后段的元素其实就已经有序了，这时继续向后遍历比较是无用的。
所以为了解决这种情况，可以使用无序边界来优化冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
System.out.println("无序边界值优化冒泡排序");
SortRunner.run(SortUtils.generateRandomArray(10000, 100, 100000),
(arr) -> {
int lastExchangeIndex = 0;
int sortBorder = arr.length - 1;
for (int i = 0; i < arr.length - 1; i++) {
boolean isSorted = true;
for (int j = 0; j < sortBorder; j++) {
if (arr[j] > arr[j + 1]) {
SortUtils.swap(arr, j, j + 1);
isSorted = false;
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
if (isSorted) {
break;
}
}
});
|
鸡尾酒排序
在一些特殊情况下，比如对一些近似有序的数组进行排序的时候，可以考虑用鸡尾酒排序来对数据进行排序。
鸡尾酒排序的思想是：在冒泡排序比较元素和交换的过程中，使用双向遍历比较和交换元素。
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
30
|
System.out.println("鸡尾酒排序");
SortRunner.run(SortUtils.generateRandomArray(10000, 100, 100000),
(arr) -> {
for (int i = 0; i < arr.length / 2; i++) {
boolean isSorted = true;
for (int j = i; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
SortUtils.swap(arr, j, j + 1);
isSorted = false;
}
}
if (isSorted) {
break;
}
isSorted = true;
for (int j = arr.length - i - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
SortUtils.swap(arr, j, j - 1);
isSorted = false;
}
}
if (isSorted) {
break;
}
}
});
|
左右无序边界值
鸡尾酒排序同样可以使用无序边界值的方法对算法进行优化，不过因为鸡尾酒排序是双向的，所以无序值也是有左右两个。
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
30
31
32
33
34
35
36
37
38
39
40
41
42
|
System.out.println("左右无序边界值优化鸡尾酒排序");
SortRunner.run(SortUtils.generateRandomArray(10000, 100, 100000),
(arr) -> {
int leftExchangeIndex = 0;
int leftSortBorder = leftExchangeIndex;
int rightExchangeIndex = arr.length - 1;
int rightSortBorder = rightExchangeIndex;
for (int i = 0; i < arr.length / 2; i++) {
boolean isSorted = true;
for (int j = i; j < rightSortBorder; j++) {
if (arr[j] > arr[j + 1]) {
SortUtils.swap(arr, j, j + 1);
isSorted = false;
rightExchangeIndex = j;
}
}
rightSortBorder = rightExchangeIndex;
if (isSorted) {
break;
}
isSorted = true;
for (int j = arr.length - i - 1; j > leftSortBorder; j--) {
if (arr[j] < arr[j - 1]) {
SortUtils.swap(arr, j, j - 1);
isSorted = false;
leftExchangeIndex = j;
}
}
leftSortBorder = leftExchangeIndex;
if (isSorted) {
break;
}
}
});
|
鸡尾酒排序的效率
数组长度：100000
|
冒泡排序 |
鸡尾酒排序 |
| 无序数组 |
27412毫秒 |
12868毫秒 |
| 近似有序 |
13962毫秒 |
43毫秒 |
以上的测试数据仅仅为简单测试，具体情况请自行测试，另外，如果排序数组长度过长，建议修改 SortRunner.run() 方法，去掉一些无用的操作步骤，减少排序测试的总体时长
最后
本文Github https://github.com/herenpeng/code-learn 已收录，欢迎Star。
