幾乎每種語言都內建了排序函數,直接呼叫就好。那為什麼還要學排序?因為排序承載的是算法思想。演算法對電腦的重要性不言自明,好演算法能讓效率事半功倍,而它所代表的計算思維,值得花時間細細體會。
關於冒泡排序,前輩們已經寫過很多精闢的文章。我這裡換個角度,試著把它的執行過程講得更具體一些。
如果光靠想像無法建立畫面,建議直接讓瀏覽器把每一輪的變化演出來。
打開 Chrome,載入你的腳本頁面:

右鍵選擇「檢查」:

依序切換到 Sources,找到你的腳本:

我的腳本是 bubble.html,放在 www.test.com 的 js/f/ 目錄下。你的檔名與路徑應該不同,按自己的情況找即可。

在 for 循環那幾行打上斷點——這正是我想觀察冒泡每一輪怎麼運作的位置。

回到瀏覽器重新執行腳本:

那個藍色矩形標出了當前暫停的執行位置。接下來用單步執行按鈕,就能一行一行往下走:

對新手而言,這樣直觀地看著變量變化,比讀十遍文字都有用。
借助中間變量,這是最直白的做法:
// 交互元素
if(arr[j] > arr[j+1]){
mark = false;
var temp = arr[j]; // 把第一個元素存入中間變量
arr[j] = arr[j+1]; // 第二個元素給第一個,此時原值已安全存在 temp 中
arr[j+1] = temp; // temp 的值給第二個元素,交換完成
}
冒泡排序本質是:比較相鄰兩元素,若順序不對就交換,一趟走完整個元素就被挑選出來。
拿這組無序數組說明:2,9,4,8,5,1,0,7,3,6,比較規則為「大於」。
第一輪:
2,4,9,8,5,1,0,7,3,62,4,8,9,5,1,0,7,3,6注意 9 的軌跡:因為它本來就比 2 大,所以沒被換到前面;接著每遇到一個更小的數就後退一格,像氣泡一樣一路浮到最右端。第一輪結束時數組變成 2,4,8,5,1,0,7,3,6,9,最大值已經到位。
第二輪:出發點是上一輪的結果,這一點要特別確認,否則會看糊塗。
2,4,5,8,1,0,7,3,6,92,4,5,1,8,0,7,3,6,92,4,5,1,0,7,3,6,8,9兩輪之後,末尾兩位已經有序。以此類推,十輪之後整個數組必然排好——元素有幾個,最多就需要幾輪。
// 外層控制輪數
for(var i=0;i<len;i++){
// 內層對數組元素進行冒泡選擇
for(var j=0;j<len-1-i;j++){
// 交互元素
if(arr[j] > arr[j+1]){
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
分工很清楚:外層管第幾輪,內層管每一輪比幾次,並在每次比較時依規則交換位置。內層的 len-1-i 是個關鍵優化——末尾 i 個元素已經就位,不必再比。
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="https://www.w3.org/1999/xhtml" xml:lang="zh-cn">
<head>
<meta http-equiv="Content-Type" content="text/html;charset=UTF-8" />
<title>冒泡排序</title>
<script type="text/javascript">
// 參數:數字數組
function bubble(arr){
// 檢查參數
if(toString.call(arr) !== '[object Array]'){
return false;
}
var len = arr.length;
if(len <= 1){ // 小於等於 1 個元素無需排序
return arr;
}
// 外層控制輪數
for(var i=0;i<len;i++){
var mark = true; // 標記本輪是否發生過交換
// 內層進行冒泡選擇
for(var j=0;j<len-1-i;j++){
if(arr[j] > arr[j+1]){
mark = false;
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
if(mark){
// 本輪一次交換都沒發生,說明已經有序,提前收工
return arr;
}
}
return arr;
}
// 測試
var ar = [9,3,7,4,8,2,5,1,6,0];
alert(bubble(ar));
</script>
</head>
<body>
</body>
</html>
那個 mark 標記是實務上很重要的一手:若某輪完全沒有交換,代表序列已有序,可直接跳出,對近乎排序好的資料能省下大量比較。
本文只講冒泡。快速排序、選擇排序、插入排序的原理與它有相通之處,網上也有不少好文章,有興趣可以自己往下鑽。