冒泡排序及其优化

2019-10-09

最最常见的排序-冒泡排序及其优化

核心思想

冒泡的核心思想是两两比较,若前面的比后面的大,则相互交换,一趟下来,最大的数位于最后

代码

5个数两两比较,需要比较4次,因此n个数需要比较n-1次

int a[] = { 3, 2, 7, 1, 5 };
for (int i = 0; i < a.length - 1; i++) {
	if (a[i] > a[i + 1]) {
		int temp = a[i];
		a[i] = a[i + 1];
		a[i + 1] = temp;
	}
}
System.out.println(Arrays.toString(a));

第一轮完成后的运行结果如下,最大的数已经沉底

1	[2, 3, 1, 5, 7]

因此可以加上一个外层的循环来完成所有排序

int a[] = { 3, 2, 7, 1, 5 };

for (int j = 0; j < a.length - 1; j++) {
	for (int i = 0; i < a.length - 1 - j; i++) {
		if (a[i] > a[i + 1]) {
			int temp = a[i];
			a[i] = a[i + 1];
			a[i + 1] = temp;
		}
	}
}
System.out.println(Arrays.toString(a));

执行完后可以得到打印信息:

1	[1, 2, 3, 5, 7]

优化

上面代码虽然可以满足排序的需求,但是本身数据有序或者某块有序,则应该中断排序
可以加入一个标志位,来判断是否有序了,如果标志位不变则表示已经排好序了,则可以中断排序
全部代码如下


public static void main(String[] args) {
//冒泡以及优化算法
// int a[] = { 1, 2, 3, 10, 9, 8, 7, 6, 5, 4 };
int a[] = { 1, 2, 3, 5, 4 };
int time = 0;
for (int j = 0; j < a.length; j++) {
	int flag = 0;
	for (int i = 0; i < a.length - 1 - j; i++) {
		if (a[i] > a[i + 1]) {
			int temp = a[i];
			a[i] = a[i + 1];
			a[i + 1] = temp;
			flag++;
		}
	}

	if (flag == 0) {
		break;
	}
	time++;

}
System.out.println(time);
System.out.println(Arrays.toString(a));

}