快排及常见两种优化方法

csdn博客同步发布

正常快排

最近在找实习，然而我觉得博客还是要坚持日更，我相信时间总是挤出来的，不扯淡了，快排这是个面试常考题，今天主要着重于讲他的优化方法，那我就直接先贴快排代码，再来细细道来我所知道的优化方法，正常的快排，先上图片后上代码，比较容易理解

    public void sort(Comparable[] a,int lo,int hi){
        if(lo>= hi) return;
        int j=partition(a,lo, hi);
        sort(a,lo,j-1);
        sort(a,j+1, hi);
    }

    private int partition(Comparable[] a, int lo, int hi) {
     
        int i=lo,j=hi+1;
        Comparable temp = a[lo];
        while(true){
            while(a[++i].compareTo(temp)<0) if(i==hi) break;
            while(a[--j].compareTo(temp)>0) if(i==lo) break;
            if(i>=j) break;//why?why?
            swap(a,i,j);
        }
        swap(a,lo,j);
        return j;
    }

    private void swap(Comparable[] a, int i, int j) {
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

切分轨迹图片如下：

正常快排

时间复杂度

时间复杂度最快平均是O（nlogn）,最慢的时候是O(n2);辅助空间也是O(logn)；最开始学快排时最疑惑的就是这个东西不知道怎么得来的，一种是通过数学运算可以的出来，还有一种是通过递归树来理解就容易多了

这里写图片描述

这张图片别人博客那里弄过来的，所谓时间复杂度最理想的就是取到中位数情况，那么递归树就是一个完全二叉树，那么树的深度也就是最低为Logn，这个时候每一次又需要n次比较，所以时间复杂度nlogn，当快排为顺序或者逆序时，这个数为一个斜二叉树，深度为n，同样每次需要n次比较，那那么最坏需要n2的时间

第一种优化方法

第一种优化方法，于插入排序相结合，在小数组的情况下，快排比较慢，因为递归sort会出现调用自己情况，所以

//sort里面这句
if(start>=end) return;
//换成下面这句
if(start>=end+M） 
    Insertion.sort(a,start,end);//直接将这部分排序用插入排序来完成
return;

第二种优化方法

第二种就是三向切分，主要用于具有大量重复数据的情况，可以大大提高效率，因为正常的快排会出现同样会把这些数进行递归，

public void sort(Comparable[] a,int lo,int hi){
        if(lo>= hi) return;
        int j=partition(a,lo, hi);
        sort(a,lo,j-1);
        sort(a,j+1, hi);
    }

    private int partition(Comparable[] a, int lo, int hi) {
     
        int i=lo,j=hi+1;
        Comparable temp = a[lo];
        while(true){
            while(a[++i].compareTo(temp)<0) if(i==hi) break;
            while(a[--j].compareTo(temp)>0) if(i==lo) break;
            if(i>=j) break;
            swap(a,i,j);
        }
        swap(a,lo,j);
        return j;
    }

    private void swap(Comparable[] a, int i, int j) {
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

三向切分示意图和切分轨迹图，代码对照着图来看，相信聪明的你很快就可以理解

示意图 切分轨迹图

以上的图主要来自与算法第四版，源码地址[源码地址]，(http://download.csdn.net/detail/sinat_28676875/9804063)

ps：如果你觉得我文章哪里写错了或者哪里太糟糕了，欢迎指出
ps：如果你觉得我的文章对你有帮助，那么就点个喜欢，thank you也可以关注我的公众号

我的公众号