每天一点算法-快速排序 (Day4)

介绍

快速排序简称快排，是最为常见的算法之一，前面介绍的桶排序虽然快但空间消耗大，冒泡排序利用的空间较为合理但O(n^2)显然在数据量较大时不够快；快排算是从两者取长补短的算法，算法逻辑（升序为例）：
1.在数据中选一个作为基准数（一般习惯是选中间的那个数，但选择其他数也可）；
2.将所有除基准数外的数据进行遍历，小于基数的放到一个数组记做a1，大于的放到一个数组记做a2；
3.若只有两个数则将小放前面、大的放后面; 若a1或者a2只有0~1个则当前数组退出；
4.将a1、a2执行步骤1,2,3。

这张图表达的快排逻辑很清晰:

例子

假设有一个待排序数组[77, 6, 37, 96, 34, 6, 14], js实现如下(升序)：

function sort(arr){
    if(arr.length<=1){return arr;}
    var pivotIndex=Math.floor(arr.length/2); //基准数
    var pivot=arr.splice(pivotIndex,1)[0]; //将基准数移出
    var a1=[];
    var a2=[];
    for(var i=0;i<arr.length;i++){
        if(arr[i]<=pivot) a1.push(arr[i]);
        else a2.push(arr[i]);
    }
    //递归
    return sort(a1).concat([pivot],sort(a2));
}

sort([77, 6, 37, 96, 34, 6, 14]); // =>[6, 6, 14, 34, 37, 77, 96]

时间复杂度

快排的平均时间复杂度为O(nlogn)，快排的时间复杂度计算较为复杂，有兴趣的同学可参考：https://www.zhihu.com/question/22393997
可以看到的是快排的时间复杂度是介于桶排序(O(n))和冒泡排序(O(n^2))之间的:
O(1 )< O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

感谢阅读！欢迎关注！持续更新中...