JavaScript如何實現快速排序

小編給大家分享一下JavaScript如何實現快速排序，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

具體如下：

思想：

通過分治思想、遞歸方法將數據依次分解為包含較小元素和較大元素的不同子序列

1.在數組中選擇一個元素為基準

2.對數組進行遍歷，小于基準的元素都移到基準的左邊，大于基準的元素都移到基準的右邊

3.對基準左邊和右邊的兩個子集，不斷重復前兩步，直到所有子集只剩下一個元素為止

實現代碼：

function sqort(arr){
 if(arr.length===0){
 return [];
}
var left=[];
var right=[];
var pivot=arr[0];//(基準以首元素)
for(var i=1;i<arr.length;i++){
 if(arr[i]<pivot){
 left.push(arr[i]);
}else{
 right.push(arr[i]);
}
}
return sqort(left).concat(pivot,qsort(right));//遞歸
}
var a=[];
for (i=0;i<10;++i){
a[i]=Math.floor(Math.random()*100+1);
}
console.log(a);
console.log(sqort(a));
//(基準以中間元素的情況)
function sqort(arr){
 if(arr.length<=1){
 return arr;
}
var left=[];
var right=[];
var pivotIndex=Math.floor(arr.length/2);
var pivot=arr.splice(pivotIndex,1)[0];//(基準以中間元素)
for(var i=1;i<arr.length;i++){
 if(arr[i]<pivot){
 left.push(arr[i]);
}else{
 right.push(arr[i]);
}
}
return sqort(left).concat(pivot,sqort(right));//遞歸
}
var a=[12,34,23,78,34,26];
console.log(a);
console.log(sqort(a));

注:  對于較小數組和較大數組分別遞歸調用sqort()函數，當遞歸結束時候，再將較小的數組與基準以及較大的數組連接起來形成最終的有序數組并返回。

以上是“JavaScript如何實現快速排序”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！