溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

JS排序算法之希爾排序與快速排序?qū)崿F(xiàn)方法

發(fā)布時間：2020-09-12 03:12:35 來源：腳本之家 閱讀：136 作者：xxza 欄目：web開發(fā)

本文實例講述了JS排序算法之希爾排序與快速排序?qū)崿F(xiàn)方法。分享給大家供大家參考，具體如下：

希爾排序：

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

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

時間復(fù)雜度O(n*logn)

function shellSort(){
  var N=arr.length;
  var h=1;
  while(h<N/3){
    h=3*h+1;//設(shè)置間隔
  }
  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){//兩個數(shù)調(diào)換
  var temp =array[j];
  array[j]=array[i];
  array[i]=temp;
}

快速排序：

通過遞歸的方式將數(shù)據(jù)依次分解成包含較小元素和較大元素的不同子序列，不斷重復(fù)這個步驟，直到所有數(shù)據(jù)都是有序的。

選一個基準值，小于基準值的放一個數(shù)組里面。大于基準值的放一個數(shù)組里面。

時間復(fù)雜度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));
}

快速排序適合用于大型數(shù)據(jù)集合，在處理小數(shù)據(jù)集合反而性能會下降。

PS：這里再為大家推薦一款關(guān)于排序的演示工具供大家參考：

在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)學運算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)》

希望本文所述對大家JavaScript程序設(shè)計有所幫助。

向AI問一下細節(jié)

免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手