簡介
快速排序,通過一趟掃描將要排序的數(shù)據(jù)分割成獨立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數(shù)據(jù)變成有序序列。
講解
設(shè)示例數(shù)組為：[5 2 7 1 4 9 8]燎猛，
- 先把第一項"5"取出來;
用"5"依次與其余項進行比較;
如果比"5"小就放"5"前邊,[2 1 4] 都比"5"小,所以全部放到"5"前邊,[2 1 4] [5];
如果比"5"大就放"5"后邊,[7 9 8]比"5"大,放到"5"后邊[5] [7 9 8];
第一次排序完成后:
排序前: [5 2 7 1 4 9 8]
排序后: [2 1 4 5 7 9 8]
對前半部分和后半部分分別進行快速排序
[2 1 4]重復(fù)第一步->
排序后：[1] [2] [4]
[7 9 8]重復(fù)第一步->
排序后： [7] [9 8]
現(xiàn)在的數(shù)組是這樣字的：[1 2 4 5 7 9 8]對[9 8]排序
排序后：[8] [9]
排序完成啦：[1 2 4 5 7 8 9];
演示代碼
function quickSort(array,low,high){
var tt =0;
if(low<high){
tt = partition(array,low,high);
quickSort(array,low,tt-1);
quickSort(array,tt+1,high);
}
}
var partition = function(unsorted,left,right){
var tem = unsorted[left];
while(left<right){
while(left<right && unsorted[right]>=tem){right--;}//從右邊開始，找到第一個小于tem（所選基數(shù)）的值
unsorted[left] = unsorted[right];//把找到的數(shù)賦給unsorted[left],比如[4,3,1,5,9,7,2]會變?yōu)閇2,3,1,5,9,7,2]
while(left<right && unsorted[left]<tem){left++;}//從左邊開始邢隧，找到第一個大于tem的值
unsorted[right]=unsorted[left];//把找到的數(shù)賦給unsorted[right],數(shù)組變作為[2,3,1,5,9,7,5]
//循環(huán)
}
unsorted[left] = tem;//數(shù)組變作為[2,3,1,4,9,7,5]认烁，分割成功
return left;//left=3;
}
window.onload=function(){
var array = [4,3,1,5,9,7,2];
quickSort(array,0,array.length-1);
console.log(array);
}
這個復(fù)雜度我卻是計算不出來...依賴被測試的數(shù)組，好吧，網(wǎng)上說是：n*logn宾舅，哪位大神告訴下怎么計算的- -
代碼執(zhí)行結(jié)果
