DIV CSS 佈局教程網

用 JavaScript 手寫冒泡排序與快速排序:原理拆解與程式碼
編輯:關於JavaScript     

排序是每個前端工程師都該親手寫過一次的題目。本文用 JavaScript 把最經典的兩種排序——冒泡排序與快速排序——從思路到實作完整拆一遍,看完你會明白它們為什麼一個慢、一個快。

一、冒泡排序(Bubble Sort)

想法非常直白:隨便挑一個位置的元素,跟它下一個位置的元素比一比。如果目標是由小到大,就把小的往前放、大的往後擺,本質上就是兩兩交換位置。一輪掃下來,最大的那顆「氣泡」會浮到最右端;接著再掃一輪,第二大也會到位。反覆進行,直到再也沒有需要交換的 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²),資料量一大就會明顯變慢,但勝在邏輯單純、空間開銷極小,教學與小資料量情境仍然好用。

二、快速排序(Quick Sort)

快速排序換了個思路:先從陣列裡挑一個基準值(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 排序方法實作》這類專題整理。希望本文對你的學習有幫助。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved