閱讀原文
冒泡排序是一個比較經(jīng)典和簡單的排序算法，今天我們從從算法本身殷蛇，時間復(fù)雜度以及穩(wěn)定性方面來看看冒泡排序谱轨，這些方面也是研究其他排序算法的一般思路
冒泡思想
在算法國內(nèi)，相傳有一位算法大師浙炼，他不喜做官份氧，一心只在民間傳道受業(yè)，弟子三千弯屈，人稱“Bill大師”蜗帜。
有一天，Bill大師帶著新收的弟子張大胖去溪邊游玩资厉，看到許多大大小小的石頭在溪邊厅缺，他靈機一動，就拿起了四個大小不同的石子宴偿，擺成一行：
Bill大師問：“大胖湘捎，你如何將這些石子按照從小到大的順序從左到右依次排列成一行？”
“先找出最大的放在右邊酪我，然后再找出次大的消痛，放在最大的左邊，按照這個規(guī)律就可以依次排好了”都哭，大胖不假思索地回答道秩伞。
“那你如何找到最大的呢？”
“用肉眼看”欺矫，大胖弱弱地說了一句纱新。
“蠢材，怎么可以用肉眼看穆趴，如果成千上萬你也用肉眼看嗎脸爱？咱們算法國以算法著稱，就是讓一切問題的解決都可以最終化為一個算法未妹，可以用程序?qū)懗鰜聿痉希 ?Bill嚴(yán)厲地批評道空入。
“那該如何找最大的呢？” 大胖問道
“你看那水中的魚族檬，他們時不時地吐出泡泡歪赢，那泡泡越往上走就會越大，我們可以借鑒這種思路啊单料÷窨”
“從第一個石子開始，讓它和右邊相鄰的石子進行比較扫尖，如果左邊的石子大于右邊的石子白对，那么就交換兩個石子的位置，（也可以左小于右交換换怖，這里采用大于交換）甩恼，這樣每比較一次，大的就跑到右邊狰域，直到跑到最右邊”媳拴，Bill說道。
Bill看大胖不明白兆览，解釋道：“起始時屈溉，左下標(biāo)指向第一個石子，右下標(biāo)指向第二個石子抬探，然后比較”子巾，說著說著畫了一個圖
“然后左右下標(biāo)同時向右移動，再次比較”小压，Bill接著說道线梗，手不停的畫著
“這樣一來，每次比較完怠益，右下標(biāo)指向的石頭就是已經(jīng)比較過的元素中的最大元素”仪搔，Bill微微笑了一下，然后又畫了一個圖：
“按照這個做法蜻牢，這一趟下來所有石子中最大的就跑到最右邊了”烤咧，大胖悟出了其中的真諦，接著老師的話說了一句抢呆，自己在地上也畫了一個圖：
“這是第一趟排序煮嫌，經(jīng)過這趟排序之后，最大的就在最右邊了抱虐，也就是排好序了昌阿，那么接下來就從剩下的三個石子中選最大的了，規(guī)則就和上面的一樣了”，大胖繼續(xù)說道懦冰，并畫了一個圖：
Bill臉上露出滿意的笑容灶轰。接著問道：“如果有 N 個石子，稱從左到右找最大為一趟刷钢，那么要排好序需要多少趟框往？”
大胖想了想，說道：“需要N-1次闯捎，因為如果因為N-1個數(shù)都排好了，那么最后一個數(shù)也就不用排了”许溅，順便畫了一個圖演示剛才四個石子的情況
冒泡代碼
“那你能把這個過程用代碼實現(xiàn)嗎瓤鼻？”，Bill問道贤重。
“這個......”茬祷，大胖撓了撓頭，傻傻地笑了一下并蝗，Bill不滿地看了新徒弟一眼祭犯，只好自己寫了，只見他飛速地寫了短短的幾行代碼：
private static void BubbleSort(int[] arr){
int temp = 0;
for (int i=0; i<arr.length-1; i++) { // 一共n-1趟
for (int j=0; j<arr.length-1-i; j++) { // 第i+1趟時滚停，需要比較arr.length-1-i次
if (arr[j] > arr[j+1]) { // 交換兩個元素的值
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
大胖心中暗暗驚嘆老師的功力沃粗。
“這個第一層循環(huán)是控制趟數(shù)，第二行能具體講講嗎键畴？”最盅，大胖再次撓了撓頭。
“第二層就是控制你第 i+1趟（因為i從0開始）所比較的次數(shù)起惕，第 i +1 趟比較了 n - 1 -i 次”涡贱，Bill說道，最后畫了兩張圖惹想。
“隨著趟數(shù)的增加问词，比較的次數(shù)也隨之減小，這個規(guī)律很容易發(fā)現(xiàn)吧嘀粱！”激挪，Bill說道。
張大胖點了點頭草穆，明白了灌灾。
時間復(fù)雜度
“那你說說這個算法的時間復(fù)雜度吧””锋喜，Bill問道。
張大胖心說好不容易跟著老師出來一次，本想游山玩水嘿般，沒想到這么多問題段标！ 他不敢怠慢，趕緊盤算起來：
4個石子炉奴，排序完需要3趟逼庞，第一趟需要比較3次，第二趟需要比較2次瞻赶，第三趟需要比較1次赛糟，那一共比較了 3 + 2 + 1 次。
那推廣到數(shù)量為 n 的規(guī)模的話砸逊，那就需要 (n-1) + (n-2) +...+2+1 次璧南，這不就是一個等差數(shù)列嗎，很顯然：
根據(jù)復(fù)雜度的規(guī)則师逸，去掉低階項（也就是n/2）,并去掉常數(shù)系數(shù)司倚，那復(fù)雜度就是O(n^2)了
“O(n^2)”,大胖想了一會說道。
“恩恩篓像，不錯动知，孺子可教≡北纾” Bill贊賞到盒粮，心想這小子數(shù)學(xué)還不錯。
穩(wěn)定性
“那這個算法穩(wěn)不穩(wěn)定呢屈暗？”拆讯，Bill又問道。
“哦? 什么是穩(wěn)定性养叛？”
奧种呐，這個還沒有給他講過，Bill忽然想起來弃甥。
“所謂穩(wěn)定性爽室，其實就是說，當(dāng)你原來待排的元素中間有相同的元素淆攻，在沒有排序之前它們之間有先后順序阔墩，在排完后它們之間的先后順序不變，我們就稱這個算法是穩(wěn)定的”瓶珊，Bill說道啸箫，順便畫了一個圖舉了一個例子
“看到了吧，原本同樣大的石子伞芹，藍(lán)色的在綠色的左邊忘苛，拍完序后藍(lán)色的仍然在綠色的左邊蝉娜，這就是穩(wěn)定的”，Bill解釋道扎唾。
“哦召川，我懂了，那冒泡排序就是一個穩(wěn)定的排序了胸遇，因為在交換的時候荧呐，如果兩個石子相同骆捧，那么就不交換[if (arr[j] > arr[j+1]){ 交換}],相同元素不會因為算法中哪條語句相互交換位置的枪汪。”
“恩暑诸，對的”逗威，Bill說道收捣。
天色漸晚，Bill和弟子準(zhǔn)備回去庵楷，張大胖問道：“老師，這個排序算法是不是叫做冒泡排序楣颠？”
Bill說：“沒錯尽纽，很形象吧？ 對了大胖童漩，我今天發(fā)現(xiàn)你的理論基礎(chǔ)不錯弄贿，一點就透，但是編碼功底太差矫膨，以后要多加練習(xí)啊差凹，不要成為一個眼高手低的人啊〔嘞冢”
“謹(jǐn)遵老師教誨危尿！我一定多加練習(xí)！”
摘錄自：碼分享
