JS希爾排序與快速排序的實作方法

本文主要介紹了JS排序演算法之希爾排序與快速排序實現方法,結合實例形式分析了希爾排序與快速排序的原理及javascript實現技巧,需要的朋友可以參考下，希望能幫助到大家。

希爾排序：

定義一個間隔序列，例如是5，3，1。第一次處理，會處理所有間隔為5的，下次會處理間隔為3的，最後一次處理間隔為1的元素。也就是相鄰元素執行標準插入排序。

在開始最後一次處理時，大部分元素都將在正確的位置，演算法就不必對很多元素進行交換，這是比插入元素高級的地方。

時間複雜度O(n*logn)

#

function shellSort(){
  var N=arr.length;
  var h=1;
  while(h<N/3){
    h=3*h+1;//设置间隔
  }
  while(h>=1){
    for(var i=h; i<N; i++){
      for(j=i; j>=h && arr[j]<arr[j-h]; j-=h){
        swap(arr, j, j-h);
      }
    }
    h=(h-1)/3;
  }
}
function swap(array, i, j){//两个数调换
  var temp =array[j];
  array[j]=array[i];
  array[i]=temp;
}

快速排序：

透過遞歸的方式將資料依序分解成包含較小元素和較大元素的不同子序列，並不斷重複這個步驟，直到所有資料都是有序的。

選一個基準值，小於基準值的放一個陣列裡面。大於基準值的放一個陣列裡面。

時間複雜度O(n*logn)

#

function quickSort(arr){
  if(arr.length==0){
    return [];
  }
  var left=[];
  var right=[];
  var p=arr[0];
  for(var i=1; i<arr.length; i++){
    if(arr[i]<p){
      left.push(arr[i]);
    }else{
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat(p,quickSort(right));
}

快速排序適合大型資料集合，在處理小數據集合反而效能會下降。

相關推薦：

詳細分析php實作希爾排序演算法的方法

JavaScript排序演算法之希爾排序的2個實例_基礎知識

JavaScript希爾排序、快速排序、歸併排序演算法_javascript技巧

以上是JS希爾排序與快速排序的實作方法的詳細內容。更多資訊請關注PHP中文網其他相關文章！