DIV CSS 佈局教程網

JavaScript 陣列排序算法整理:冒泡、快速、插入與希爾排序
編輯:關於JavaScript     

排序是前端面試與日常開發都很常碰到的題目。下面把幾種常見的排序方式整理成一個 sorting 物件,每個方法都接收陣列並回傳排序後的結果,方便直接替換比較。

window.onload = function () {
  var array = [0, 1, 2, 44, 4, 324, 5, 65, 6, 6, 34, 4, 5, 6, 2, 43,
    5, 6, 62, 43, 5, 1, 4, 51, 56, 76, 7, 7, 2, 1, 45, 4, 6, 7, 8];
  console.log('原始陣列');
  console.log(array);
  array = sorting.shellSort(array);
  console.log('排序後的陣列');
  console.log(array);
}

var sorting = {

  // 利用原生 sort 排序
  systemSort: function (arr) {
    return arr.sort(function (a, b) { return a - b; });
  },

  // 氣泡排序
  bubbleSort: function (arr) {
    var len = arr.length, tmp;
    for (var i = 0; i < len - 1; i++) {
      for (var j = 0; j < len - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
          tmp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = tmp;
        }
      }
    }
    return arr;
  },

  // 快速排序
  quickSort: function (arr) {
    var low = 0, high = arr.length - 1;
    sort(low, high);
    function sort(low, high) {
      if (low < high) {
        var mid = (function (low, high) {
          var tmp = arr[low];
          while (low < high) {
            while (low < high && arr[high] >= tmp) { high--; }
            arr[low] = arr[high];
            while (low < high && arr[low] <= tmp) { low++; }
            arr[high] = arr[low];
          }
          arr[low] = tmp;
          return low;
        })(low, high);
        sort(low, mid - 1);
        sort(mid + 1, high);
      }
    }
    return arr;
  },

  // 插入排序
  insertSort: function (arr) {
    var len = arr.length;
    for (var i = 1; i < len; i++) {
      var tmp = arr[i];
      for (var j = i - 1; j >= 0; j--) {
        if (tmp < arr[j]) {
          arr[j + 1] = arr[j];
        } else {
          arr[j + 1] = tmp;
          break;
        }
      }
    }
    return arr;
  },

  // 希爾排序
  shellSort: function (arr) {
    var h = 1;
    while (h <= arr.length / 3) {
      h = h * 3 + 1;   // O(n^(3/2)) by Knuth, 1973
    }
    for (; h >= 1; h = Math.floor(h / 3)) {
      for (var k = 0; k < h; k++) {
        for (var i = h + k; i < arr.length; i += h) {
          for (var j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
            var tmp = arr[j];
            arr[j] = arr[j - h];
            arr[j - h] = tmp;
          }
        }
      }
    }
    return arr;
  }
}

挑選建議

  • systemSort:最省事,注意 sort() 預設是字串比較,數字排序一定要傳比較函式。
  • 氣泡排序:概念最簡單,平均與最壞都是 O(n²),適合教學。
  • 快速排序:平均 O(n log n),實務上最快,但最壞情況會退化,且需要留意堆疊深度。
  • 插入排序:資料量小或接近有序時表現很好,常被當成快排的遞迴底層。
  • 希爾排序:插入排序的改良版,透過增量序列先讓整體大致有序,再逐步縮小增量。

以上就是這次整理的內容,希望對大家有幫助。

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