- 相關(guān)推薦
JavaScript快速排序實(shí)現實(shí)例教程
目前最常見(jiàn)的排序算法大概有七八種，理解和掌握各種排序算法似乎是一個(gè)合格的程序員所必須要掌握的。今天想要和大家分享快速排序算法的Javascript的實(shí)現。
快速排序(Quicksort),又稱(chēng)為 劃分交換排序(partition-exchange sort)，最早是由東尼·霍爾提出的。
基本思想
快速排序使用 分治法(Divide and conquer)策略(即分而治之，各個(gè)擊破)把一個(gè)序列(list)分為兩個(gè)子序列(sub-lists)。其基本步驟如下:
從數列中挑出一個(gè)元素，稱(chēng)為 基準(pivot)。
重新排序數列，所有小于基準的元素，都移到基準的左邊;所有大于基準的元素都移到基準的右邊。這個(gè)分區結束之后，該基準處于數列的中間位置，稱(chēng)為 分區(partition)操作。
對基準左邊和右邊的兩個(gè)子集，進(jìn)行遞歸操作，即不斷重復第一步和第二步。直到所有子集只剩下一個(gè)元素為止。
示例說(shuō)明
下面我們舉個(gè)示例進(jìn)行排序說(shuō)明，數列為[8,7,0,7,5,2,5,3,1]。
第一步: 基準值選取�；鶞手悼梢匀我膺x取，便于理解，這里我們選擇中間值5作為基準。
[8,7,0,7, 5, 2,5,3,1]
第二步: 進(jìn)行分區操作。按照順序將每個(gè)元素與基準進(jìn)行比較，想成兩個(gè)子集，大于5與小于5.
[0,2,5,3,1, 5, 8,7,7]
第三步，遞歸操作。對兩個(gè)子集不斷重復第一步和第二步，直到所有子集只剩下一個(gè)元素為止。
[0,2, 5, 3,1] 5 [8, 7, 7][0,2,3,1, 5 ] 5 [7, 7, 8][0, 2, 3,1]5,5,7, 7, 8[0,1, 2, 3] 5, 5, 7, 7, 8[0,1,2,3,5,5,7,7,8]
Javascript的實(shí)現
講述了快速排序的基本思想，下面就讓我們使用代碼對其進(jìn)行實(shí)現吧~
第一步: 定義函數quicksort,參數為一個(gè)數組。
var quicksort = function(arr){
};
第二步: 檢查數組個(gè)數，小于等于1，則返回。
var quicksort = function(arr){ if(arr.length <= 1){ return arr;
}
};
第三步: 進(jìn)行基準選擇，定義兩個(gè)空數組進(jìn)行左右兩個(gè)子集元素的存放。
var quicksort = function(arr){ if(arr.length <= 1){ return arr;
} var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex,1)[0]; var left = []; var right = []; for(var i = 0;i < arr.length;i++){ if(arr[i] < pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
};
第四步: 遞歸操作。對兩個(gè)子集不斷重復第一步和第二步，直到所有子集只剩下一個(gè)元素為止。
var quicksort = function(arr){ if(arr.length <= 1){ return arr;
} var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex,1)[0]; var left = []; var right = []; for(var i = 0;i < arr.length;i++){ if(arr[i] < pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
} return quicksort(left).concat([pivot],quicksort(right));
};
第五步: quicksort函數的調用
這里可以直接定義一個(gè)數組，對函數進(jìn)行調用即可。
var quicksort = function(arr){ if(arr.length <= 1){ return arr;
} var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex,1)[0]; var left = []; var right = []; for(var i = 0;i < arr.length;i++){ if(arr[i] < pivot){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
} return quicksort(left).concat([pivot],quicksort(right));
};var array = [8,7,0,7,5,2,5,3,1];
quicksort(array); //[0,1,2,3,5,5,7,7,8]
小結
快速排序的基本思想還是比較簡(jiǎn)單的，巧用了分治法策略 ~。
【JavaScript快速排序實(shí)現實(shí)例教程】相關(guān)文章：
深入理解JS實(shí)現快速排序和去重javascript技巧10-28
Javascript實(shí)例教程08-10
常用排序算法之JavaScript實(shí)現代碼段06-04
Javascript實(shí)例教程如何使用HoTMetal06-12
用Javascript進(jìn)行簡(jiǎn)單的Table點(diǎn)擊排序08-29
使用JavaScript實(shí)現Java的List功能10-26