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

更新時(shí)間：2017年12月12日 14:38:33 作者：xxza

這篇文章主要介紹了JS排序算法之希爾排序與快速排序?qū)崿F(xiàn)方法,結(jié)合實(shí)例形式分析了希爾排序與快速排序的原理及javascript實(shí)現(xiàn)技巧,需要的朋友可以參考下

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

希爾排序：

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

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

時(shí)間復(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){//兩個(gè)數(shù)調(diào)換
  var temp =array[j];
  array[j]=array[i];
  array[i]=temp;
}

快速排序：

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

選一個(gè)基準(zhǔn)值，小于基準(zhǔn)值的放一個(gè)數(shù)組里面。大于基準(zhǔn)值的放一個(gè)數(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ù)集合反而性能會(huì)下降。

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

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

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

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

您可能感興趣的文章: