JavaScript實(shí)現(xiàn)快速排序的方法分析

第JavaScript實(shí)現(xiàn)快速排序的方法分析本文實(shí)例講述了JavaScript實(shí)現(xiàn)快速排序的方法。分享給大家供大家參考，具體如下：

思想：

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

1.在數(shù)組中選擇一個(gè)元素為基準(zhǔn)

2.對數(shù)組進(jìn)行遍歷，小于基準(zhǔn)的元素都移到基準(zhǔn)的左邊，大于基準(zhǔn)的元素都移到基準(zhǔn)的右邊

3.對基準(zhǔn)左邊和右邊的兩個(gè)子集，不斷重復(fù)前兩步，直到所有子集只剩下一個(gè)元素為止

實(shí)現(xiàn)代碼：

functionsqort(arr){

if(arr.length===0){

return[];

varleft=[];

varright=[];

varpivot=arr[0];//(基準(zhǔn)以首元素)

for(vari=1;iarr.length;i++){

if(arr[i]pivot){

left.push(arr[i]);

}else{

right.push(arr[i]);

returnsqort(left).concat(pivot,qsort(right));//遞歸

vara=[];

for(i=0;i++i){

a[i]=Math.floor(Math.random()*100+1);

console.log(a);

console.log(sqort(a));

//(基準(zhǔn)以中間元素的情況)

functionsqort(arr){

if(arr.length=1){

returnarr;

varleft=[];

varright=[];

varpivotIndex=Math.floor(arr.length/2);

varpivot=arr.splice(pivotIndex,1)[0];//(基準(zhǔn)以中間元素)

for(vari=1;iarr.length;i++){

if(arr[i]pivot){

left.push(arr[i]);

}else{

right.push(arr[i]);

returnsqort(left).concat(pivot,sqort(right));//遞歸

vara=[12,34,23,78,34,26];

console.log(a);

console.log(sqort(a));

注:對于較小數(shù)組和較大數(shù)組分別遞歸調(diào)用sqort()函數(shù)，當(dāng)遞歸結(jié)束時(shí)候，再將較小的數(shù)組與基準(zhǔn)以及較大的數(shù)組連接起來形成最終的有序數(shù)組并返回。

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

在線動畫演示插入/選擇/冒泡/歸并/希爾/快速排序算法過程工具：

/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é)》、《Java