首頁  >  文章  >  web前端  >  有關JS希爾排序演算法(詳細教學)

有關JS希爾排序演算法(詳細教學)

亚连
亚连原創
2018-06-21 11:29:001776瀏覽

這篇文章主要介紹了JS排序演算法之希爾排序與快速排序實現方法,結合實例形式分析了希爾排序與快速排序的原理及javascript實現技巧,需要的朋友可以參考下

本文實例講述了JS排序演算法之希爾排序與快速排序實作方法。分享給大家供大家參考,具體如下:

希爾排序:

定義一個間隔序列,例如是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));
}

上面是我整理給大家的,希望今後會對大家有幫助。

相關文章:

在javaScript中有關空值和假值的說法

在Webpack中有關自動化建置(詳細教學)

在微信小程式中如何實作圖片上傳等一系列功能

如何建立前端通用的資料模擬框架(詳細教學)

以上是有關JS希爾排序演算法(詳細教學)的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn