這篇文章主要介紹了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)); }
以上是有關JS希爾排序演算法(詳細教學)的詳細內容。更多資訊請關注PHP中文網其他相關文章!