0%

排序-冒泡排序及其优化

发表于 更新于 分类于

概念

冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直至没有反序的记录为止。
因为按照该算法，每次比较会将当前未排序的记录序列中最小的关键字移至未排序的记录序列最前（或者将当前未排序的记录序列中最大的关键字移至未排序的记录序列最后），就像冒泡一样，故以此为名。

演示

比如我们待排序的数组是 {9, 1, 5, 8, 3, 7, 4, 6, 2}
第1趟排序：
第1次比较，2和6比较，2小于6，反序，进行交换： 9 1 5 8 3 7 4 2 6
第2次比较，2和4比较，2小于4，反序，进行交换： 9 1 5 8 3 7 2 4 6
第3次比较，2和7比较，2小于7，反序，进行交换： 9 1 5 8 3 2 7 4 6
第4次比较，2和3比较，2小于3，反序，进行交换： 9 1 5 8 2 3 7 4 6
第5次比较，2和8比较，2小于8，反序，进行交换： 9 1 5 2 8 3 7 4 6
第6次比较，2和5比较，2小于5，反序，进行交换： 9 1 2 5 8 3 7 4 6
第7次比较，2和1比较，2大于1，正序，不用交换： 9 1 2 5 8 3 7 4 6
第8次比较，1和9比较，1小于1，反序，进行交换： 1 9 2 5 8 3 7 4 6
可以看出，第一趟排序将当前序列最小值移动至未排序的序列最前面的位置。

第2趟排序： 因为第一趟已经排好1的位置，所以只需要对剩下的{9, 2, 5, 8, 3, 7, 4, 6}再进行冒泡排序
… 重复以上操作，直至排序完毕

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
36
37
38
// 定义接口
interface Sorter {
	/**
	 * 将数组按升序排序
	 */
	int[] sort(int[] arr);

	/**
	 * 交换数组arr中的第i个位置和第j个位置的关键字
	 */
	default void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
}

// 冒泡排序
class BubbleSorter implements Sorter {

	@Override
	public int[] sort(int[] arr) {
		bubbleSort(arr);
		return arr;
	}

	private void bubbleSort(int[] arr) {
		int i, j;
		int len = arr.length;
		for (i = 0; i < len - 1; i++) {
			for (j = len - 1; j > i; j--) {
				if (arr[j - 1] > arr[j]) {
					swap(arr, j - 1, j);
				}
			}
		}
	}
}

优化

当待排序数组为{1, 3, 4, 5, 6, 7, 8, 9, 2}时：
第1趟排序的结果为： 1 2 3 4 5 6 7 8 9
此时其实序列已经完成，但是根据上述代码仍得继续遍历，直至第9趟排序。这显然是不合理的，如果我们能在代码中加入一个flag标记上一趟排序中是否进行过交换，如果进行过未进行交换，说明当前数组已经有序。
优化代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 优化的冒泡排序
class OptimizedBubbleSorter extends BubbleSorter {

	@Override
	protected void bubbleSort(int[] arr) {
		int i, j;
		int len = arr.length;
		boolean swapped = true; // 标记：上一趟循环是否进行过交换
		for (i = 0; i < len - 1 && swapped; i++) {
			swapped = false;
			// 在某一趟遍历中,如果没有可交换的,那么swapped = false,跳出外层循环;
			// 如果一旦进行了交换,则swapped = true,需要进行下一趟遍历
			for (j = len - 1; j > i; j--) {
				if (arr[j - 1] > arr[j]) {
					swap(arr, j - 1, j);
					swapped = true;
				}
			}
		}
	}
}

复杂度

时间复杂度：
最好情况： 排序表本身是顺序的，根据优化后的代码，则只需要进行n-1次比较，故时间复杂度为O(n)；
最差情况： 排序表本身是逆序的，则比较次数为 1+2+…+(n-1) = n*(n-1)/2 , 并作等数量级的移动操作；
平均情况： 时间复杂度为 O(n^2)

空间复杂度：
最好情况=最坏情况=平均情况=O(1)