冒泡排序

Posted by 石玉军 on 2018-07-26

冒泡排序在排序算法中效率算最慢的一类了,但是因为它简单的缘故仍然是工作1-3年的程序员面试经常会碰到的算法问题,今天就来给大家分析一下冒泡排序的排序流程。

假如我们现在要排序的数组为[3,1,0,2,8,4,2]那么我们第一轮排序为

比较3和1,发现3比1大,那么我们就交换3和1,数组变成了[1,3,0,2,8,4,2]
比较3和0,发现3比0大,那么我们就交换3和0,数组变成了[1,0,3,2,8,4,2]
比较3和2,发现3比2大,那么我们就交换3和2,数组变成了[1,0,2,3,8,4,2]
比较3和8,发现3没有8大,那么不操作,数组还是[1,0,2,3,8,4,2]
比较8和4,发现8比4大,那么我们就交换8和4,数组变成了[1,0,2,3,4,8,2]
比较8和2,发现8比2大,那么我们就交换8和2,数组变成了[1,0,2,3,4,2,8]
现在第一轮的排序已经完成了,我们就筛选出来了最大值8,此时数字8已经在数组最后的位置了,下一轮排序我们就可以排除它了。

第二轮排序为:

比较1和0,发现1比0大,那么我们就交换1和0,数组变成了[0,1,2,3,4,2,8]
比较1和2,发现1没有2大,那么不操作,数组还是[0,1,2,3,4,2,8]
比较2和3,发现2没有3大,那么不操作,数组还是[0,1,2,3,4,2,8]
比较3和4,发现3没有4大,那么不操作,数组还是[0,1,2,3,4,2,8]
比较4和2,发现4比2大,那么我们就交换4和2,数组变成了[0,1,2,3,2,4,8]
现在第二轮排序完成了,数组最后的4和8是不是已经有序了呢。

聪明的你是不是已经发现了冒泡排序的规律了呢,那么你能用代码去手写一下实现么?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int []a=new int[]{3,1,0,2,8,4,2};
int i,j;
int flag; // 标记
for (i=a.length-1; i>0; i--) {
flag = 0; // 初始化标记为0
// 将a[0...i]中最大的数据放在末尾
for (j=0; j<i; j++) {
if (a[j] > a[j+1]) {
// 交换a[j]和a[j+1]
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = 1; // 若发生交换,则设标记为1
}
}

if (flag==0)
break; // 若没发生交换,则说明数列已有序。
}
for (int ii:a){
System.out.print(ii+",");
}

上方代码就是我们冒泡排序的一个简单实现了。你手写的是不是比我的更强呢。

上方的代码还有一个flag我们没有说到,不知道你注意到了么,本身待排序的数组是需要数组长度-1大轮排序才能得出结果,但是我们这个数组在第三轮排序完成后就已经有序了,第四轮的时候其实内层的循环是没有进去的,那么我们是不是可以得出结论,既然第四轮没有进行排序那么再后面的排序是不是也不需要了,所以我们使用了一个flag标记来避免多余的操作。

一个简单的冒泡排序讲完了。在这里温馨提示大家,学习算法时,我们没必要拘泥于代码的实现,那没有意义。我的建议就是深入理解步骤,当你理解步骤以后代码是随你怎么玩都可以的。