DIV CSS 佈局教程網

JavaScript 快速排序 Quicksort 原理與實作
編輯:關於JavaScript     

快速排序是一種分治法排序演算法。它的核心概念是選出一個基準值,再把資料分成小於基準與大於等於基準的兩群,最後遞迴排序。

排序步驟

1. 選出一個基準 pivot。
2. 把小於 pivot 的元素放到左邊,大於等於 pivot 的元素放到右邊。
3. 對左右兩邊的子集合重複上述步驟。

JavaScript 實作

var quickSort = function(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];

  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return quickSort(left).concat([pivot], quickSort(right));
};

快速排序在平均情況下效率很好,但若資料已接近排序完成,或基準值選擇不當,可能會導致效能下降。實務上可加入隨機基準值或三數取中等方式改善。

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