DIV CSS 佈局教程網

JavaScript 陣列排序技巧總整理:氣泡、sort、快速、希爾、插入
編輯:關於JavaScript     

本文整理五種常見的 JavaScript 陣列排序實作,並附上原生 sort 的使用注意事項。每個版本都可直接複製使用。

① 氣泡排序

 bubbleSort:function(array){
  var i = 0, len = array.length, j, d;
  for(; i<len; i++){
    for(j=0; j<len; j++){
      if(array[i] < array[j]){
        d = array[j];
        array[j] = array[i];
        array[i] = d;
      }
    }
  }
  return array;
}

② 利用原生 sort

實務上這才是最該用的寫法。關鍵在於傳入比較函式,否則 sort 會以字串順序排序。

 systemSort:function(array) {
  return array.sort(function(a, b) {
    return a - b;
  });
}

③ 快速排序

取基準點後分左右兩側遞迴,平均時間複雜度 O(n log n),是實作上最實用的排序之一。

 quickSort:function(array) {
  var i = 0;
  var j = array.length - 1;
  var Sort = function(i, j){
    // 結束條件
    if(i == j ){
      return
    };
    var key = array[i];
    var tempi = i; // 記錄開始位置
    var tempj = j; // 記錄結束位置
    while(j > i){
      // j <<-------------- 向前查找
      if(array[j] >= key){
        j--;
      } else{
        array[i] = array[j]
        //i++ ------------>>向後查找
        while(j > ++i){
          if(array[i] > key){
            array[j] = array[i];
            break;
          }
        }
      }
    }
    // 如果第一個取出的 key 是最小的數
    if(tempi == i){
      Sort(++i, tempj);
      return ;
    }
    // 最後一個空位留給 key
    array[i] = key;
    // 遞歸
    Sort(tempi, i);
    Sort(j, tempj);
  }
  Sort(i, j);
  return array;
}

④ 希爾排序

插入排序的改良版,透過逐步縮小的間距(gap)讓元素先大範圍地移動,最後再以 gap=1 收尾。這裡用了兩組預先算好的步長序列,分別針對小陣列與大陣列。

 //Jun.array.shellSort(Jun.array.df(10000));
shellSort:function(array){
  var tempArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1]; // reverse() 在維基上看到這個最優的步長 較小數組
  //var tempArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1] //針對大數組的步長選擇
  var i = 0;
  var tempArrtempArrLength = tempArr.length;
  var len = array.length;
  var len2 = parseInt(len/2);
  for(;i < tempArrLength; i++){
    if(tempArr[i] > len2){
      continue;
    }
    tempSort(tempArr[i]);
  }
  // 排序一個步長
  function tempSort(temp){
    var i = 0, j = 0, f, tem, key;
    var tempLen = len%temp > 0 ? parseInt(len/temp) + 1 : len/temp;
    for(;i < temp; i++){
      // 依次循環列
      for(j=1;/*j < tempLen && */temp * j + i < len; j++){
        //依次循環每列的每行
        tem = f = temp * j + i;
        key = array[f];
        while((tem-=temp) >= 0){
          // 依次向上查找
          if(array[tem] > key){
            array[tem+temp] = array[tem];
          }else{
            break;
          }
        }
        array[tem + temp ] = key;
      }
    }
  }
  return array;
}

⑤ 插入排序

把每個元素往前插入到已排序的區段中,資料量小的時候效率相當不錯,而且近乎有序時接近 O(n)。

 insertSort:function(array){
  var i = 1, j, temp, key, len = array.length;
  for(; i < len; i++){
    temp = j = i;
    key = array[j];
    while(--j > -1){
      if(array[j] > key){
        array[j+1] = array[j];
      }else{
        break;
      }
    }
    array[j+1] = key;
  }
  return array;
}

附錄:原生 sort 的三個注意事項

 var arrDemo = new Array();
arrDemo[0] = 10;
arrDemo[1] = 50;
arrDemo[2] = 51;
arrDemo[3] = 100;
arrDemo.sort(); //調用sort方法後,數組本身會被改變,即影響原數組
alert(arrDemo);//10,100,50,51
// 默認情況下sort方法是按ascii字母順序排序的,而非我們認為是按數字大小排序
arrDemo.sort(function(a,b){return a>b?1:-1});//從小到大排序
alert(arrDemo);//10,50,51,100
arrDemo.sort(function(a,b){return a<b?1:-1});//從大到小排序
alert(arrDemo);//100,51,50,10

結論:

1、陣列呼叫 sort 之後會直接影響原陣列本身,而不是回傳新陣列。
2、sort() 預設以字元順序排序,對數字型陣列排序時,別理所當然地以為會按數值大小排。
3、想改變預設行為,就自行指定排序規則函式。

另外補充一個求值上的細節:比較函式請直接寫 return a - b,不要用 a > b ? 1 : -1。後者在 a 等於 b 時會回傳 -1,違反了比較函式「相等要回 0」的契約,在某些引擎上可能導致排序結果不穩定。

希望本文所述對大家 JavaScript 程式設計有所幫助。

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