冒泡排序

冒泡排序(BubbleSort)是一种基础的交换排序,可以将无序数组按规则(规则:例如从小到大)排序。

算法原理

冒泡排序实例:从小到大排序

冒泡排序实例:从小到大排序

数组中所有相邻的元素两两比较,当满足规则时交换两个元素的位置,所有元素比较完后,本轮结束,数据中有多少元素,执行多少轮比较。
第一轮结束后,最满足规则的元素会在数组的顶端,继续下一轮;
第二轮结束后,次满足规则的元素会在数组的次顶端,继续下一轮;

最后一轮结束后,数组完成排序。

代码实现

使用Java实现简单的冒泡排序

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
public static void main(String[] args) {
int[] array = new int[]{5, 8, 6, 3, 9, 2, 1, 7, 10};
sortSimple(array);
}
/**
* 最简单的冒泡排序
*
* @param array
*/
public static void sortSimple(int[] array) {
System.out.println("排序前:" + Arrays.toString(array));
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
// 交换两数位置
swap(array, j, j + 1);
}
System.out.println("第:" + (i + 1) + "轮第" + (j + 1) + "次" + Arrays.toString(array));
}
}
System.out.println("排序后:" + Arrays.toString(array));
}

/**
* 交换数组中两个元素的位置
*
* @param array 数组
* @param i 元素i
* @param j 元素j
*/
private static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}

性能优化

排序中发现已完成排序,直接终止

如果一轮排序中没有任何元素交换顺序,说明数组已经有序,直接终止排序。

在sortSimple中,可以发现第7、8轮排序中没有任何元素交换顺序,所以我们可以在第7轮结束后直接终止后续排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 冒泡排序优化 - 如果一轮排序中没有任何元素交换顺序,说明数组已经有序,直接终止排序
* <p>
* 在sortSimple中,可以发现第7、8轮排序中没有任何元素交换顺序,所以我们可以在第7轮结束后直接终止后续排序。
*
* @param array
*/
public static void sortSimple1(int[] array) {
System.out.println("排序前:" + Arrays.toString(array));
for (int i = 0; i < array.length; i++) {
boolean isSorted = true;
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
isSorted = false;
}
System.out.println("第:" + (i + 1) + "轮第" + (j + 1) + "次" + Arrays.toString(array));
}
if (isSorted) {
break;
}
}
System.out.println("排序后:" + Arrays.toString(array));
}
坚持原创技术分享,您的支持将鼓励我继续创作!