排序是每個前端工程師都該親手寫過一次的題目。本文用 JavaScript 把最經典的兩種排序——冒泡排序與快速排序——從思路到實作完整拆一遍,看完你會明白它們為什麼一個慢、一個快。
想法非常直白:隨便挑一個位置的元素,跟它下一個位置的元素比一比。如果目標是由小到大,就把小的往前放、大的往後擺,本質上就是兩兩交換位置。一輪掃下來,最大的那顆「氣泡」會浮到最右端;接著再掃一輪,第二大也會到位。反覆進行,直到再也沒有需要交換的 pair,排序就完成了。
正因為一次循環只能確定一個最大值的位置,所以外層還必須再包一層迴圈來驅動整個過程。
var arr = [3, 1, 4, 2, 5, 21, 6, 15, 63];
function bubbleSort(arr) {
for (var i = 0; i < arr.length - 1; i++) {
for (var j = i + 1; j < arr.length; j++) {
// 取出前一個值,跟後一個值比較
var cur = arr[i];
if (cur > arr[j]) {
// 因為要交換,得先把後面的值暫存起來
var temp = arr[j];
arr[j] = cur;
arr[i] = temp;
}
}
}
return arr;
}
它的時間複雜度是 O(n²),資料量一大就會明顯變慢,但勝在邏輯單純、空間開銷極小,教學與小資料量情境仍然好用。
快速排序換了個思路:先從陣列裡挑一個基準值(pivot),接著讓每個元素跟它比一次,比它小的丟到左邊、比它大的丟到右邊。這樣一輪之後,基準值就落在最終的正確位置上了。然後對左右兩堆各自再跑一次同樣的流程——這正是遞迴的用武之地。
var arr = [3, 1, 4, 2, 5, 21, 6, 15, 63];
function quickSort(arr) {
// 只剩一個(或零個)元素時,本來就有序,不必再比
if (arr.length <= 1) {
return arr;
}
// 取中間位置作為基準值
var len = Math.floor(arr.length / 2);
var cur = arr.splice(len, 1);
var left = []; // 比基準值小的放這裡
var right = []; // 比基準值大的放這裡
for (var i = 0; i < arr.length; i++) {
if (cur > arr[i]) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
// 遞迴:左右兩堆各自排好,再跟基準值拼回去
return quickSort(left).concat(cur, quickSort(right));
}
平均情況下快速排序的時間複雜度是 O(n log n),遠優於冒泡排序,代價是額外的記憶體配置與遞迴呼叫的開銷。實務上真正的排序需求直接呼叫原生 Array.prototype.sort() 就好,但理解這兩種經典思維,對後續學習 Divide and Conquer、遞迴與複雜度分析都很有幫助。
想再深入一點,可以延伸閱讀《JavaScript 排序方法實作》這類專題整理。希望本文對你的學習有幫助。