排序是校招（或初级社招）最常见的考点之一，普通IT公司主要考察简单排序，经常让你手写一个排序算法。既能考察代码实现水平，又能看看思维方式，对面试官来说，实在是高效面试、回去加班之必备考题！
大部分同学会说，那我就写一个冒泡排序吧，因为冒泡的思路最好理解。
当然，能正常写出来的也就20%左右，主要是两层循环的指针起始数字不准确；还有要命的，说是写冒泡，但是代码却是插入排序；最NB的是代码写对了，但是让讲讲思路，一问三不知，靠背代码过面试还是有难度的。
今天我们就讲一下冒泡排序，讲完之后，大家如果不能在理解的情况下闭着眼写出代码来，请在评论区留言。
1、简单排序
首先理解下简单排序，随意给出一给乱序的数给a[]，比如 15，9，7，-1，6，3，正常情况下，从头到尾只走一遍是不能排序完成的，只能保证把一个数放到属于它的那个萝卜坑里。
也就是说一个循环搞不定，那就加一个循环呗。外循环控制循环轮数，内循环一轮排好一个数。而且对外循环来说，n个数已经排好了n-1个，那最后一个自然就不用排了，所以只用走n-1轮
代码实现如下：
内循环按各自排序的思路实现，不管是冒泡排序、直接插入排序还是简单选择排序，都是类似的两个循环样式，平均时间复杂度都是O(n^2)，所以都称之为简单排序。
2. 冒泡排序思想
冒泡排序的思想是，每轮内循环相邻的两个进行比较，如果前面的数比后面的在，就交换位置，直到最后的排序位置上。
先给大家看个图，绿色的就是内循环相邻的两个数不断后移比较，橙色的是本轮走完，已经排序好的数。
因为是交换，所以内层代码是
3. 处理内循环的起始值
可以看出内循环每轮都是从第一个数开始比较的，所以j的起始值为0。稍微麻烦点的是结束值，首先要理解的是相邻两个数进行比较，而且内部实现里也用了j+1。所以第一轮时j最多到n-1。后面的第一轮结束点都提前结束一个值，因为前面一轮已经排序好的数一定比本轮的数大，就不用再比较和交换了。其实就是减去轮数，也就是 n-i-1，
到此，冒泡排序就完成了
4. 还有个尾巴
冒泡排序其实还可以简单优化一下的。如果在某一轮排序中，一次交换也没发生。也就是说对于任意相邻的两个数，后面的数都比前面的数大，意味着什么呢？对，就是已经完成排序了。后面就不需要一轮一轮的继续比较下去了。
我们来调整下代码。一次交换也没有，也就是是否发生交换，一看到”是否“，而且最终是没有交换就结束，那定义一个bool类型的变量
boolean isChanged =false;
因为比较交换在内循环，而且每轮中一出现交换就要改变值为true，一直到本轮结束，所以这句话只能放在外循环内，内循环外。
最终的比较语句是
if(!isChange) {//没有交换
break;
}
也只能放在外循环内，内循环外。
最终优化版的代码如下
public int[] bubbleSort(int a[]) {
int len = a.length;
for(int i=0 ; i < len -1; i++ ) {
boolean isChanged = false;//标记是否发生变化
for(int j = 0 ; j < len - i - 1; j++) {
if(a[j] > a[j+1]) {
int temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
isChanged = true;//发生交换
}
}
if(!isChanged) {//本轮没有发生交换就退出
break;
}
}
return a;
}
本文为【拿OFFER】原创，转载请标明出处。
网友评论