Java冒泡排序

今天回顾了一下冒泡排序,到网上一搜答案很多都是像下面这样的

1
2
3
4
5
6
7
8
9
10
11
public bubbleSort(int[] a) {
int temp = 0;
for(int i = 0;i < a.length; i++) {
for(int j = i + 1; j < a.length; j++) {
if(a[i] > a[j]) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}

初看起来没什么问题,而且结果也能正确算出来,但是看了一下冒泡排序的定义之后就会发现问题了。

冒泡排序算法的运作如下:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

而上面的算法比较的并不是相邻的两个元素,正确的算法应该如下。

1
2
3
4
5
6
7
8
9
10
11
12
public void sort(int[] a) {
int tmp = 0;
for(int i = 0; i < a.length; i++) {
for(int j = 0; j < a.length - 1 - i; j++) {
if(a[j] < a[j + 1]) {
tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
}
}
}
}

再次进行优化后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void sort(int[] a) {
int tmp = 0;
boolean flag = true;
for(int i = 0; i < a.length && flag; i++) {
flag = false;
for(int j = 0; j < a.length - 1 - i; j++) {
if(a[j] < a[j + 1]) {
tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
flag = true;
}
}
}
}

加上一个标志位,如果内层循环全部有序的话外层不再继续进行。