【排序算法】-快速排序Quick Sort

简介

快速排序,通过一趟扫描将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

讲解

设示例数组为：[5 2 7 1 4 9 8]，

1. 先把第一项"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，哪位大神告诉下怎么计算的- -

代码执行结果