冒泡排序 Dubble Sort

发表于 分类于 阅读次数：

  • 冒泡排序：只对相邻的两个元素进行比较，第1轮循环遍历数组，如果左边的元素大于右边的就进行交换，否则比较下一个，一直最后将数组最大的元素放在数组尾部（尾部就是已经排序好的数组部分），接着n-1次循环遍历数组即可完成排序。

  • 冒泡排序是一个原地排序算法，是稳定的排序算法，其时间复杂度是O(n)

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
import java.util.Arrays;

public class Test {

	public static void bubbleSort(int[] a, int n) {
		if (n <= 1) return;

		for (int i = 0; i < n; ++i) {
			//提前退出冒泡循环的标志位
			boolean flag = false;
			int temp = 0;
			for (int j = 0; j < n - i - 1; ++j) {
				if (a[j] > a[j + 1]) {
					temp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = temp;
					flag = true; //表示有数据交换
				}
			}
			if (!flag) break; //没有数据交互，提前退出循环
		}
	}

	public static void main(String[] args) {
		int[] a= {3, 11, 1, 7, 9};
		bubbleSort(a, a.length);
		// for (int i = 0; i < a.length; i++) {
		//     System.out.print(a[i]+" ");
		// }
		System.out.print(Arrays.toString(a));
	}
}