大师网-带你快速走向大师之路 解决你在学习过程中的疑惑,带你快速进入大师之门。节省时间,提升效率

每天一点算法-快速排序 (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)

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