简介
快速排序,通过一趟扫描将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
讲解
设示例数组为：[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]重复第一步->
排序后：[1] [2] [4]
[7 9 8]重复第一步->
排序后： [7] [9 8]
现在的数组是这样字的：[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（所选基数）的值
unsorted[left] = unsorted[right];//把找到的数赋给unsorted[left],比如[4,3,1,5,9,7,2]会变为[2,3,1,5,9,7,2]
while(left<right && unsorted[left]<tem){left++;}//从左边开始，找到第一个大于tem的值
unsorted[right]=unsorted[left];//把找到的数赋给unsorted[right],数组变作为[2,3,1,5,9,7,5]
//循环
}
unsorted[left] = tem;//数组变作为[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);
}
这个复杂度我却是计算不出来...依赖被测试的数组，好吧，网上说是：n*logn，哪位大神告诉下怎么计算的- -
代码执行结果
