本文主要介绍冒泡排序，包括原始的排序以及优化后的版本，附带的介绍了一些交换的技巧。
排序算法
冒泡排序
第一种写法
1
2
3
4
5
6
7
8
9
10
11
| public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
|
第二种改良写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
}
}
if (!flag) {
break;
}
}
}
|
第三种写法，在下一轮比较时，只需比较到上一轮比较中，最后一次发生交换的位置即可。因为后面的所有元素都没有发生过交换，必然已经有序了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public static void bubbleSort(int[] arr) {
int lastExchangeIndex = 0;
int sortBorder = arr.length - 1;
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = false;
for (int j = 0; j < sortBorder; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true;
lastExchangeIndex = j;
}
}
sortBorder = lastExchangeIndex;
if (!flag) {
break;
}
}
}
|
附录：交换的技巧
一般的我们会用中间变量，进行两个值的交换，如下
1
2
3
| int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
|
但是这种情况，需要额外的空间，如果我们不使用额外的空间，如何交换呢？
加法：
1
2
3
| arr[j] = arr[j] + arr[j + 1];
arr[j + 1] = arr[j] - arr[j + 1];
arr[j] = arr[j] - arr[j + 1];
|
减法：
1
2
3
| arr[j] = arr[j] - arr[j + 1];
arr[j + 1] = arr[j] + arr[j + 1];
arr[j] = arr[j + 1] - arr[j];
|
但是这两种方式都有可能造成数组越界，最好使用异或的方式进行交换。
1
2
3
| arr[j] = arr[j] ^ arr[j + 1];
arr[j + 1] = arr[j] ^ arr[j + 1];
arr[j] = arr[j] ^ arr[j + 1];
|