快速排序采用分治法的一個非常典型的應用
算法思想
快速排序使用分治法策略來把一個序列分為兩個子序列芹彬，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數(shù)據(jù)變成有序序列
時間復雜度
O(nlgn)
步驟：
- 從數(shù)列中挑出一個元素窘行，稱為"基準"（pivot）
- 所有比基準值小的元素擺放在基準前面蝗砾，所有比基準值大的元素擺在基準后面
- 遞歸的把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序
舉例
現(xiàn)有一個數(shù)組：arr = [6,4,5,2,7]
那么先拿出一個基準：5
從左開始遍歷該數(shù)組：
6 4 5 2 7
|
大于5
如果大于基準5則放在基準右邊
4 5 6 2 7
|
放此位置
繼續(xù)遍歷：
4 5 6 2 7
|
小于5
如果小于基準5則放在基準左邊佑惠，故位置不變融欧，繼續(xù)遍歷：
4 5 6 2 7
|
小于5
則放在基準左邊：
4 2 5 6 7
|
放此位置
那么我們的一次遍歷就完成了他炊，以此類推，再遍歷左邊序列以及右邊序列
代碼實現(xiàn)
常用實現(xiàn)方法如下咧擂，c和java都可以：
function quick_sort(arr,low,high){
var i = low;
var j = high;
var temp = arr[i];
if(low < high){
while(i < j){
while(i<j && arr[j] >= temp){
j--;
}
arr[i] = arr[j];
while(i<j && arr[i] <= temp){
i++;
}
arr[j] = arr[i];
}
arr[i] = temp;
quick_sort(arr,low,i-1);
quick_sort(arr,i+1,high);
}
else{
return;
}
}
var arr = [6,4,5,2,7];
quick_sort(arr,0,arr.length-1)
console.log(arr); // [2,4,5,6,7]
以下方法只適用于JavaScript，因為使用了JavaScript的數(shù)組的方法檀蹋，并且該方法空間復雜度比較大松申，因為多使用了兩個數(shù)組
function quick_sort(arr) {
if (arr.length <= 1) {
return arr;
}
var middle = Math.floor(arr.length / 2);
var pivot = arr.splice(middle, 1)[0];
var low = [];
var high = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
low.push(arr[i]);
} else {
high.push(arr[i]);
}
}
return quickSort(low).concat([middleValue], quickSort(high));
}
var arr = [6,4,5,2,7];
quick_sort(arr); // [2,4,5,6,7]
優(yōu)化思路
- 對于小數(shù)組，可以采用插入排序俯逾，避免遞歸調(diào)用
- 采用子數(shù)組的一部分元素的中位數(shù)來切分數(shù)組
