DIV CSS 佈局教程網

排序演算法的 JavaScript 實作與講解
編輯:關於JavaScript     

氣泡排序(Bubble Sort)

氣泡排序的原理是讓最大或最小的元素「浮」起來。插入排序、選擇排序、快速排序、氣泡排序都屬於比較排序。

思路:依序比較相鄰的兩個數,小的放前、大的放後。第一趟從第一對比較到最後一對,把最大的數送到末尾;第二趟再從頭比較到倒數第二個(末尾已就位),如此反覆,直到完成排序。由於小的不斷往前、大的往後,就像氣泡上升,故名氣泡排序。

實作時要注意三點:一是交換可用 a=[b,b=a][0] 這個巧妙寫法,取代傳統的暫存變數;二是快取 array.length 避免重複取值;三是內層迴圈要從第一個數比較到倒數第 n 個。

function bubbleSort(array) {
  var l=array.length;
  for (var i = 0; i < l; i++) {
    for (var j = 0; j < l-i; j++) {
      if (array[j] < array[j - 1]) {
        array[j] = [array[j - 1], array[j - 1] = array[j]][0]// 交換元素
      }
    }
  }
}

插入排序(Insertion Sort)

非常直觀,就像摸牌、插牌的過程。思路:先假設手裡有一張已排好的牌,取出下一張 a,從後往前掃描已排序的牌,若某張比 a 大就往後挪出空間,直到找到不大於 a 的位置插入,然後重複。

function insert(arr) {
  var l = arr.length;
  var empty = [];// 空陣列,表示我們的手
  empty.push(arr[0]);// 先摸起來一張
  for (var i = 1; i < l; i++) {
    if (arr[i] > empty[empty.length - 1]) {
      empty[empty.length] = arr[i]
    }
    for (var j = empty.length; j > 0 && arr[i] < empty[j - 1]; j--) {
      empty[j] = empty[j - 1];// 向右移動
      empty[j - 1] = arr[i];// 放到空出來的位置
    }
  }
  return empty
}

這裡 && 表示「且」,兩邊條件都成立才成立,也能用來取代簡單的 if。另外要記得:陣列 arr 的「最後一項」是 arr[arr.length-1]。

選擇排序(Selection Sort)

思路:在未排序區找出最小元素放到已排序序列的起始位置,再從剩餘元素找次小的放到末尾,以此類推。實作時用一個變數記錄目前最小值的索引,遍歷後與起始位置交換。

function selectSort(array) {
  var min;
  var l = array.length;
  for (var i = 0; i < l; i++) {
    min = i;
    for (var j = i + 1; j < l; j++) {
      if (array[min] > array[j])
        min = j;
    }
    if (min != i) {
      array[i]= [array[min],array[min]=array[i]][0];// 交換元素
    }
  }
  return array;
}

快速排序(Quick Sort)

快速排序是目前最強大的排序演算法,運用了遞迴。思路:從陣列挑出一個「基準」值,比它小的放左邊、比它大的放右邊,得到「左陣列 + 基準 + 右陣列」,再對左右兩邊套用同樣的處理,直到子陣列長度不足以再分為止。

function quickSort(arr) {
  var l = arr.length;
  if(arr.length <= 1){return arr};
  var num = Math.floor(arr.length / 2);
  var numValue = arr.splice(num, 1)[0];// 取一個元素出來
  var left = [];
  var right = [];
  for (var i = 0; i < l; i += 1) {
    arr[i] < numValue ? left.push(arr[i]) : right.push(arr[i]);
  }
  return quickSort(left).concat([numValue], quickSort(right))
}

這裡要注意 arr.splice(num,1) 雖然只取一個數,但結果仍是陣列,需要 [0] 取出,否則會出現一堆巢狀陣列。

以上四種演算法除了快速排序外都屬於簡單排序,而它們在面試中考得非常頻繁。要特別強調的是,這些演算法大量運用了迴圈與陣列操作,務必熟記。

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