排序是校招（或初級社招）最常見的考點之一，普通IT公司主要考察簡單排序，經常讓你手寫一個排序算法。既能考察代碼實現水平，又能看看思維方式，對面試官來說，實在是高效面試、回去加班之必備考題！

大部分同學會說，那我就寫一個冒泡排序吧，因為冒泡的思路最好理解。

當然，能正常寫出來的也就20%左右，主要是兩層循環(huán)的指針起始數字不準確；還有要命的，說是寫冒泡，但是代碼卻是插入排序；最NB的是代碼寫對了，但是讓講講思路，一問三不知，靠背代碼過面試還是有難度的。

今天我們就講一下冒泡排序，講完之后，大家如果不能在理解的情況下閉著眼寫出代碼來，請在評論區(qū)留言。

1、簡單排序

首先理解下簡單排序，隨意給出一給亂序的數給a[]，比如 15，9，7，-1，6，3，正常情況下，從頭到尾只走一遍是不能排序完成的，只能保證把一個數放到屬于它的那個蘿卜坑里。

也就是說一個循環(huán)搞不到，那就加一個循環(huán)唄。外循環(huán)控制循環(huán)輪數，內循環(huán)一輪排好一個數。而且對外循環(huán)來說，n個數已經排好了n-1個，那最后一個自然就不用排了，所以只用走n-1輪

代碼實現如下：

內循環(huán)按各自排序的思路實現，不管是冒泡排序、直接插入排序還是簡單選擇排序，都是類似的兩個循環(huán)樣式，平均時間復雜度都是O(n^2)，所以都稱之為簡單排序。

2. 冒泡排序思想

冒泡排序的思想是，每輪內循環(huán)相鄰的兩個進行比較，如果前面的數比后面的在，就交換位置，直到最后的排序位置上。

先給大家看個圖，綠色的就是內循環(huán)相鄰的兩個數不斷后移比較，橙色的是本輪走完，已經排序好的數。

因為是交換，所以內層代碼是

3. 處理內循環(huán)的起始值

可以看出內循環(huán)每輪都是從第一個數開始比較的，所以j的起始值為0。稍微麻煩點的是結束值，首先要理解的是相鄰兩個數進行比較，而且內部實現里也用了j+1。所以第一輪時j最多到n-1。后面的第一輪結束點都提前結束一個值，因為前面一輪已經排序好的數一定比本輪的數大，就不用再比較和交換了。其實就是減去輪數，也就是 n-i-1，

到此，冒泡排序就完成了

4. 還有個尾巴

冒泡排序其實還可以簡單優(yōu)化一下的。如果在某一輪排序中，一次交換也沒發(fā)生。也就是說對于任意相鄰的兩個數，后面的數都比前面的數大，意味著什么呢？對，就是已經完成排序了。后面就不需要一輪一輪的繼續(xù)比較下去了。

我們來調整下代碼。一次交換也沒有，也就是是否發(fā)生交換，一看到”是否“，而且最終是沒有交換就結束，那定義一個bool類型的變量

因為比較交換在內循環(huán)，而且每輪中一出現交換就要改變值為true，一直到本輪結束，所以這句話只能放在外循環(huán)內，內循環(huán)外。

最終的比較語句是

也只能放在外循環(huán)內，內循環(huán)外。

最終優(yōu)化版的代碼如下