11.10 泡沫排序法

sort 用了大半個單元，是時候拆開黑盒子——排序到底是怎麼「排」的？接下來三節介紹三種經典排序演算法，從最直觀的開始：泡沫排序法（Bubble Sort）。

¶原理：相鄰互換，最大的浮到最後

規則只有一條：由左到右檢查每一對相鄰的數，順序錯了（左邊比右邊大）就交換。把這條規則從頭到尾跑一輪，會發生一件妙事：最大的數一路被換到最右邊——它像汽水裡的泡泡一樣「浮」了上來，這就是名字的由來。

拿 6, 3, 2, 5, 4, 1 跑一輪：6 跟 3 換、跟 2 換、跟 5 換……一路換到底，變成 3, 2, 5, 4, 1, 6——6 就定位，之後不必再管最後一格。對剩下 n - 1 個數再跑一輪，第二大的數浮到倒數第二格……如此反覆，n - 1 輪之後全部就定位（最後剩一個數時它自動是最小的，不用再跑）：