DIV CSS 佈局教程網

重寫 Array 的排序:手寫兩兩比較排序並掛到原型上
編輯:關於JavaScript     

想看懂 sort 之類的排序到底在做什麼,最直接的方式是自己寫一遍。這裡實作的是最直觀的兩兩比較排序(選擇排序的變體):每一輪拿當前位置的元素,去和牠之後的所有元素比對,若順序不對就交換。

以 [3, 1, 5, 6, 4, 2] 降序排列為例

第一輪:用第 1 個元素依序與後方元素比較

3 比 1 → 3 比 5(5 較大,交換)→ [5, 1, 3, 6, 4, 2]
5 比 6(交換)→ [6, 1, 3, 5, 4, 2]
6 比 4 → 6 比 2
第一輪結果:[6, 1, 3, 5, 4, 2]

第二輪:用第 2 個元素與其後方元素比較

1 比 3(交換)→ [6, 3, 1, 5, 4, 2]
3 比 5(交換)→ [6, 5, 1, 3, 4, 2]
5 比 4 → 5 比 2
第二輪結果:[6, 5, 1, 3, 4, 2]

以此類推:

第三輪結果:[6, 5, 4, 1, 3, 2]
第四輪結果:[6, 5, 4, 3, 1, 2]
第五輪結果:[6, 5, 4, 3, 2, 1]

程式碼實作

Array.prototype.fst = function (fn) {
  var fn = fn || function (a, b) { return a > b; };
  for (var i = 0; i < this.length; i++) {
    for (var j = i; j < this.length; j++) {
      if (fn(this[i], this[j]) > 0) {
        var t = this[i];
        this[i] = this[j];
        this[j] = t;
      }
    }
  }
  return this;
};

比較函數可自訂,不傳就預設做「由大到小」的比較;回傳大於 0 代表需要交換。要改成升冪,傳入 function (a, b) { return a < b; } 即可。

可以跑起來的示範頁

<!doctype html>
<html>
<head>
<meta charset="utf-8" />
<title>Array.prototype.fst 示範</title>
</head>
<body>
<pre id="out"></pre>
<script>
Array.prototype.fst = function (fn) {
  var fn = fn || function (a, b) { return a > b; };
  for (var i = 0; i <this.length; i++) {
    for (var j = i; j < this.length; j++) {
      if (fn(this[i], this[j]) > 0) {
        var t = this[i]; this[i] = this[j]; this[j] = t;
      }
    }
  }
  return this;
};

var a = [3, 1, 5, 6, 4, 2];
document.getElementById('out').innerHTML = a.fst().join(', ');
</script>
</body>
</html>

最後補一句現實面的建議:直接擴充 Array.prototype 在多人協作的專案裡容易引發非預期的衝突,而這種 O(n²) 的排序也只適合教學與理解原理;實務上請直接用原生 sort() 並傳入比較函數。

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