DIV CSS 佈局教程網

JS 排序算法總結:冒泡、快速、選擇、插入、希爾、歸並
編輯:JavaScript基礎知識     

排序幾乎是每個程序員都會用到的知識點,今天簡單總結記錄一下常見的排序算法。

一、冒泡排序

冒泡排序思路非常直觀:不停對數組進行兩兩比較,把較大(或較小)的一項往前面放。以 var arr = [7, 3, 10, 1, 8, 4, 2, 4, 4, 3] 升序排列為例:

第一次 [3, 7, 1, 8, 4, 2, 4, 4, 3, 10]
第二次 [3, 1, 7, 4, 2, 4, 4, 3, 8, 10]
以此類推……
結果 [1, 2, 3, 3, 4, 4, 4, 7, 8, 10]。

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

二、快速排序

快速排序核心步驟:

1. 選擇中間數。
2. 構建兩個臨時數組,比中間數小的放左邊,大的放右邊。
3. 對臨時數組重復 1-2。

例如原始數組 [2,4,1,5,6,3,12,9,7],第一步選第 5 項 6 為中間數,創建 left、right,left 結果為 [2,4,1,5,3],right 結果為 [12,9,7],再分別對 left 和 right 做相同操作,直到長度為 1。

// 快速排序
function quickSort(arr){
  if(arr.length <= 1){ // 長度為 1 時停止遞歸
    return arr;
  }
  var l = Math.floor(arr.length/2); // 選擇中間數
  var left = [], right = [];
  var splitEle = arr.splice(l, 1)[0]; // 將中間數從原數組刪除並保存
  for(i=0; i<arr.length; i++){
    if(arr[i] < splitEle){
      left.push(arr[i]);
    }else{
      right.push(arr[i]);
    }
  }
  return arguments.callee(left).concat(splitEle, arguments.callee(right));
}

三、選擇排序

升序排列時,假設第一項為最小值,把它與其他項分別比較,若其他項更小則交換位置,這樣第一輪結束後第一項即為最小值,然後對第二項做類似操作,以此類推。

// 選擇排序
function selectQuot(arr){
  for(i=0; i<arr.length-1; i++){
    for(j=i+1; j<arr.length; j++){
      if(arr[i] > arr[j]){
        var temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

四、插入排序

插入排序很好理解:先取出第一項放入一個虛構數組,再取第二項,若比第一項小則放前面,否則放後面;接著取第三項,與前兩項分別比較……有點像打撲克牌。以 [2, 4, 1, 5, 3, 8, 7, 9, 6] 為例,虛擬數組依次變成 [2]、[2,4]、[1,2,4]……以此類推。實際編程中並不需要單獨創建數組。

// 插入排序
function insertSort(arr){
  for(i=1; i<arr.length; i++){
    var temp = arr[i], j = i - 1;
    while(j>=0 && temp < arr[j]){
      arr[j+1] = arr[j]; // 相當於把虛擬數組當前項後移一位
      j--;
    }
    arr[j+1] = temp; // 新加項最終插入的位置
  }
  return arr;
}

五、希爾排序

希爾排序是插入排序的升級版,又稱縮小增量排序。對於插入排序,若數據本就有序則無需移動,基於此,希爾排序先把數組按一定間隔分成若干小組分別插入排序,然後逐漸減小間隔直至為 1,最後一次(間隔為 1)處理時數組已基本有序,從而提高效率。

原始數組 [3, 4, 6, 5, 1, 9, 6, 10, 8, 8],假設增量為 3:

// 希爾排序
function shellSort(array){
  var len = array.length;
  var gap = len;
  do {
    gap = Math.floor(gap/3)+1; // 減小增量
    // 把距離為 gap 的元素編為一組,掃描所有組
    for (var i = gap; i < len; i++){
      var temp = array[i], j = i - gap;
      while(j>=0 && temp < array[j]){
        array[j + gap] = array[j];
        j -= gap;
      }
      array[j+gap] = temp;
    }
  }while(gap > 1)
  return array;
}

六、歸並排序

歸並排序核心思想:先把數組分成若干子數組並各自變成有序數組,再合併這些有序數組。

var mergeSort = {
  splitArr: function(arr){
    if(arr.length == 1) return arr;
    var mid = Math.floor(arr.length/2),
        left = arr.slice(0, mid),
        right = arr.slice(mid);
    return this.merge(this.splitArr(left), this.splitArr(right));
  },
  merge: function(left, right){
    var result = [];
    while(left.length > 0 && right.length > 0){
      if(left[0] < right[0]){
        result.push(left.shift());
      }else{
        result.push(right.shift());
      }
    }
    return result.concat(left).concat(right);
  }
}
XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved