花生_TL007

这个屌丝很懒，什么也没留下！

热门标签

快速排序详解及优化方式

作者：花生_TL007 | 2024-04-28 08:08:42

踩

快速排序详解及优化方式

1.快速排序的核心思想

2.快速排序的两个重要方法

Hoare法

quickHoare函数（想办法把基准放到数组正确排序好的位置）

下面都以升序为例进行讲解：

1.快速排序的核心思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：

1.在数组中任取一个元素作为基准（基准一般选取最左边的元素），

想办法排列数组，让所有小于基准的元素都放到基准的左边，所有大于基准的元素都放到基准的右边，完成后，基准元素就排列好了。

2.采用分而治之的思想，分别对基准左区间的元素和基准右区间的元素进行1中的操作，从而完成排序。

2.快速排序的两个重要方法

Hoare法

传入的数组作为唯一的接口，对quickSortHoare方法进行实现：


public static void quickSortHoare(int[] arr){
        quickHoare(arr,0,arr.length-1);
    }

核心思想中提到了分治，所以大概率我们是要递归定义这个quickHoare方法的：


    private static void quickHoare(int[] arr,int left,int right){
        if(left>=right)return;//已经没有排序区间了，直接返回即可
 
        
        //下面这个partionHoare方法可以把基准放到排序好的位置，然后返回基准排好后的下标位置
        int mid=partitonHoare(arr,left,right);//left和right一定是合法有效的
        
        quickHoare(arr,left,mid-1);//递归基准左侧区间
        quickHoare(arr,mid+1,right);//递归基准右侧区间
    }

先不关心quickHoare函数的具体实现和细节，把总体思路捋一遍，以上的代码就是核心思路了，只要把quickHoare实现函数，快速排序就搞定了。

quickHoare函数（想办法把基准放到数组正确排序好的位置）

默认最左边的元素为基准(stand)

left下标和right下标分别指向最左和最右

{1 3 4 5 6 7 9}--》这是排序好的数组，下面看看quickHoare函数，怎么把没排好序的数组中6放到4的位置的：

1.先让right往前走，只要arr[right]>=stand，right就减减:

2.然后再让left往下走，只要arr[left]<=3，left就加加:

3.到了这里，right和left都不能走了，所以接下来arr[left]和arr[right]两个元素进行交换:

4.在重复上述right和left的移动逻辑，直到，left与right相遇（一定会相遇）：

5.遇到上面这个情况实际上就是循环终止条件，直接把arr[left]（当然arr[right]也是可以的）和6进行交换即可：

此时，元素“6”的位置已经排好，在对1 3 4 5和7 9进行分治采用相同的方法即可达到排序目的。

代码：


 private static int partitonHoare(int[] arr,int left,int right){//返回排序好元素的下标
 
        int i=left;
        int stand=arr[left];//基准默认是最左边的元素
        while(left<right){//此条件防止下标越界
            //先右边下标走
            while(left<right&&arr[right]>=stand){
                right--;
            }
 
            while(left<right&&arr[left]<=stand){
                left++;
            }
 
            //程序到达这里时：arr[right]<stand 而arr[left]>stand
 
            swap(arr,right,left);            //交换arr[right]和arr[left]
        }
        //当程序到达这里，right==left了，此时这两个下标所指的位置，就是arr[i]有序时，因该在的位置
        swap(arr,i,left);
        return left;//返回right也是一样的
    }

Hoare方法的整体代码：


class TestSort{
 
    private static void swap(int[] arr,int a,int b){
        int t=2;
        t=arr[a];
        arr[a]=arr[b];
        arr[b]=t;
    }
 
    public static void quickSortHoare(int[] arr){
        quickHoare(arr,0,arr.length-1);
    }
 
    private static void quickHoare(int[] arr,int left,int right){
        if(left>=right)return;//已经没有排序区间了，直接返回即可
 
 
        //下面这个partionHoare方法可以把基准放到排序好的位置，然后返回基准排好后的下标位置
        int mid=partitonHoare(arr,left,right);//left和right一定是合法有效的
 
        quickHoare(arr,left,mid-1);//递归基准左侧区间
        quickHoare(arr,mid+1,right);//递归基准右侧区间
    }
 
    private static int partitonHoare(int[] arr,int left,int right){//返回排序好元素的下标
 
        int i=left;
        int stand=arr[left];//基准默认是最左边的元素
        while(left<right){
            //先右边下标走
            while(left<right&&arr[right]>=stand){
                right--;
            }
 
            while(left<right&&arr[left]<=stand){
                left++;
            }
 
            //程序到达这里时：arr[right]<stand 而arr[left]>stand
 
            swap(arr,right,left);            //交换arr[right]和arr[left]
        }
        //当程序到达这里，right==left了，此时这两个下标所指的位置，就是arr[i]有序时，因该在的位置
        swap(arr,i,left);
        return left;//返回right也是一样的
    }

不知道小伙伴们有没有这样的困惑：

1、能让left先走，然后right再走吗？

2、为什么arr[left]<=stand arr[right]>=stand 小于或者等于不可以吗？

首先第一个问题，我们：还是用前面那个数组作为样例

让left先走，然后是right,其他逻辑不变：

交换：

left先走:

哦豁，按照这样，6因该放到7的位置，显然是错的

根据1 3 4 5 6 7 9，因该放到4的位置（倒数第三个位置）。

这就是为什么要让right先走，然后left再走的原因的原因。
其次，第二个问题，left>=stand或者right<=stand就停下，以这个数组为例

{ 1 ，1， 1， 1， 1}

如果是这种重复的数组，那么left和right就不可能相遇了，会死循环的。

挖坑法

逻辑：

顾名思义就是挖坑，举个例子：

此时的3，就被挖走了，放到了tmp中（当然这是抽象的理解，实际上3还在数组的原来位置）。

接下来的逻辑就和hoare法差不多，先让right走，但是因为arr[right]=2<3所以，right就不走了，然后把arr[right]“挖走”，填到arr[left]中，然后再让left++：

此时arr[right]形成了新的坑（当然也是抽象理解，实际装的还是2）

我们继续尝试让left前进，但是arr[left]=7>3了，所以left停下，

挖走arr[left]填给arr[right]，然后right往上移动：

循环上面的逻辑：

right移动到1的位置停止：

挖走arr[right]填到arr[left]，然后left往下移动：

此时left==right，退出循环，把tmp填进坑：

如图，3已经在升序的正确位置了。

翻译成代码：


private static int partitionPit(int[] arr,int left,int right){//左右，都是有效的闭区间下标
        int tmp=arr[left];//先挖一个坑(在left的位置)，把土放进tmp
        while(left<right){
            while(left<right&&arr[right]>=tmp){
                right--;
            }
            arr[left]=arr[right];//填坑，然后arr[right]成了新的坑
            while(left<right&&arr[left]<=tmp){
                left++;
            }
            arr[right]=arr[left];//填坑，在挖坑
        }
        arr[left]=tmp;//把最后一个坑填上
        return left;
    }

3.快速排序的时间复杂度分析

快速排序的时间复杂度比较特殊，它不是很稳定，最坏情况和最好情况我们都要了解。

最好情况

假设有N个元素，且恰好定义的基准，排序好的位置在数组的中间：

一共有logN+1层

每一层都有N个元素要被right和left走完，

所以每一层都要执行N此，因此时间复杂度是：

O（fast）=N*(logN+1)=N*logN+N

取最高阶：O（fast）=N*logN

和堆排序的时间复杂度是一样的，不过快速排序实际上要比堆排序快一些，在最好情况下。

最坏情况

什么是最坏情况？

我们可以分离变量，来理解一下，首先对于一个数组进行快速排序，那么他的执行次数至少是N次，因为left=0，right=数组长度-1，即使递归子树，但是每层的子树之和次数也是N

所以每一层的执行次数，永远是N次，那我们只用考虑，啥时候层数是最多的就可以了

我来举个最坏情况的例子：

像这种基准永远都在最最左侧的情况下，是没有右树的，程序会递归N次，每次left，right走的总次数是一个公差为-1，首项为N的等比数列，所以时间复杂度就是有N项，首项为N，公差为-1的等差数列，自然时间复杂度是：

O（slow）=N^2

这种最坏情况可以说就是一个冒泡排序了

总结：

快速排序的时间复杂度是O(n log n)，其中n为待排序数组的长度。快速排序的每次划分操作需要O(n)的时间复杂度，而递归调用的次数为O(log n)，因此总的时间复杂度为O(n log n)。在最坏的情况下，即数组已经有序的情况下，快速排序的时间复杂度为O(n^2)。

空间复杂度分析

实际上快速排序的这三个方法：

定义的变量都是常量级的，是O(1)我们不用管。重要的是，quickHoare方法需要递归，递归要开辟栈帧，所以快速排序的空间复杂度和递归的深度有关。

最优情况时间复杂度为：O(logN)-->每次均等分割

最差情况时间复杂度为：O(N)

如图与时间复杂度最坏情况类似：

4.基于减少递归的优化方法

想要优化快速排序，从时间复杂度分析中，我们直到，关键就在于如果减少递归次数。

三数取中

核心思路就是，选取三个数中中间大的那个数字，作为key（基准），尽量从中间分割数组，从而减少递归次数。

方式也很简单，写一个getMid方法，返回一个靠中间的元素的下标即可：

private static int getMid(int[] arr,int left,int right){//一定是有效的闭区间
    int mid=(left+right)/2;
 //arr[left] arr[right] arr[mid]三个数组返回中间大的
    }
}

实际上就只有三大种情况：

依据mid的位置来写，就不容易乱了：


    private static int getMid(int[] arr,int left,int right){//一定是有效的闭区间
        int mid=(left+right)/2;
        if(arr[left]<arr[right]){
            if(arr[left]>arr[mid])return left;
            else if(arr[right]<arr[mid])return right;
            else return mid;//mid不小于left，也不大于right，那么就返回mid啊
        }else{//下面的写法逻辑和上面是一模一样的(arr[left])>arr[right]的情况)--》如果有有元素相同，返回任意一个，所以可以不关心“=”的情况
            if(arr[mid]<arr[right])return right;
            else if(arr[mid]>arr[left])return left;
            else return mid;
        }
    }

在使用，hoare方法的时候调用getMid方法，来获取基准即可：

private static int partitionHoare(int[] arr,int left,int right){//返回排序好元素的下标

    int i=left;
    int mid=getMid(arr,left,right);
    swap(arr,mid,left);//把获得的基准和最左侧交换，这样好管理，也好理解
    int stand=arr[left];//基准默认是最左边的元素

/*
下面就和之前的代码一模一样了*/
}

末尾换用直接插入排序

先来将两个引子：

第一个，我们先来看一下这颗树：

一共有7个节点，最后一层就占据了4个，是总结点数的一般还多，如果总结点数更大，这个占比可能更大。

第二个，学过直接插入排序，我们都知道，当一个数组趋近于有序，他的排序速度会很快（时间复杂度是O(n)）

学习了上面的直接快速排序，我们都知道，快排需要像二叉树一样递归进行，也会和第一个引子类似，在最后几层，递归次数非常大，而我们使用的又是递归，在测试用例很大的情况下，很可能出现栈溢出。

所以，能不能这样：

在最后几层我们就不递归了，改用，直接插入排序来代替，虽然直接插入排序最坏情况下，时间复杂度是O(O^2)，但是，实际上在最后几层，整个数组，已经被快速排序排列的差不多了，所以这个思路没有问题。


    private static void _insert(int[] arr,int left,int right){
        //把直接插入排序中，对0，和数组长度length的限制改成left,right的就可以了
        for (int i = left+1; i <=right ; i++) {
            int tmp=arr[i];
            int j=i-1;
            for ( ; j >=left ; j--) {
                if(arr[j]>tmp)arr[j+1]=arr[j];//一直和tmp比较啊啊啊啊啊，只要tmp小，就一直往前找到合适为止
                else break;//如果arr[j]<=arr[j+1]，那么数组已经“有序了”
            }
            arr[j+1]=tmp;//填好以后一个元素
        }
    }

如果直接插入排序还没有学的小伙伴可以看一下这个篇博客，有详细介绍：直接插入排序与希尔排序的详解及对比

只要把_insert方法，放到递归的方法中，设置一个条件来调用即可：


 private static void quickHoare(int[] arr,int left,int right){
        if(left>=right)return;//已经没有排序区间了，直接返回即可
 
        if(right-left<6){//如果递归区间小于某一个值，就直接插入排序，对于值的设置，没有严格要求，不要太大就可以
            _insert(arr,left,right);
            return;//记得返回，不然还会继续进行下面的程序，去递归
        }
      //下面代码，和之前一样，就不展示了
。。。。。。
 
    }

优化后快速排序的整体代码：


class TestSort{
 
    private static void swap(int[] arr,int a,int b){
        int t=2;
        t=arr[a];
        arr[a]=arr[b];
        arr[b]=t;
    }
 
    public static void quickSortHoare(int[] arr){
        quickHoare(arr,0,arr.length-1);
    }
 
    private static void quickHoare(int[] arr,int left,int right){
        if(left>=right)return;//已经没有排序区间了，直接返回即可
 
        if(right-left<6){
            _insert(arr,left,right);
            return;//记得返回，不然还会继续进行下面的程序，去递归
        }
        //下面这个partionHoare方法可以把基准放到排序好的位置，然后返回基准排好后的下标位置
        int mid=partitionHoare(arr,left,right);//left和right一定是合法有效的
 
        quickHoare(arr,left,mid-1);//递归基准左侧区间
        quickHoare(arr,mid+1,right);//递归基准右侧区间
    }
 
    private static int partitionHoare(int[] arr,int left,int right){//返回排序好元素的下标
 
        int i=left;
        int mid=getMid(arr,left,right);
        swap(arr,mid,left);//把获得的基准和最左侧交换，这样好管理，也好理解
        int stand=arr[left];//基准默认是最左边的元素
 
        while(left<right){
            //先右边下标走
            while(left<right&&arr[right]>=stand){
                right--;
            }
 
            while(left<right&&arr[left]<=stand){
                left++;
            }
 
            //程序到达这里时：arr[right]<stand 而arr[left]>stand
 
            swap(arr,right,left);            //交换arr[right]和arr[left]
        }
        //当程序到达这里，right==left了，此时这两个下标所指的位置，就是arr[i]有序时，因该在的位置
        swap(arr,i,left);
        return left;//返回right也是一样的
    }
 
    private static int partitionPit(int[] arr,int left,int right){//左右，都是有效的闭区间下标
        int tmp=arr[left];//先挖一个坑(在left的位置)，把土放进tmp
        while(left<right){
            while(left<right&&arr[right]>=tmp){
                right--;
            }
            arr[left]=arr[right];//填坑，然后arr[right]成了新的坑
            while(left<right&&arr[left]<=tmp){
                left++;
            }
            arr[right]=arr[left];//填坑，在挖坑
        }
        arr[left]=tmp;//把最后一个坑填上
        return left;
    }
 
    private static int getMid(int[] arr,int left,int right){//一定是有效的闭区间
        int mid=(left+right)/2;
        if(arr[left]<arr[right]){
            if(arr[left]>arr[mid])return left;
            else if(arr[right]<arr[mid])return right;
            else return mid;//mid不小于left，也不大于right，那么就返回mid啊
        }else{//下面的写法逻辑和上面是一模一样的(arr[left])>arr[right]的情况)--》如果有有元素相同，返回任意一个，所以可以不关心“=”的情况
            if(arr[mid]<arr[right])return right;
            else if(arr[mid]>arr[left])return left;
            else return mid;
        }
    }
 
    private static void _insert(int[] arr,int left,int right){
        //把直接插入排序中，对0，和数组长度length的限制改成left,right的就可以了
        for (int i = left+1; i <=right ; i++) {
            int tmp=arr[i];
            int j=i-1;
            for ( ; j >=left ; j--) {
                if(arr[j]>tmp)arr[j+1]=arr[j];//一直和tmp比较啊啊啊啊啊，只要tmp小，就一直往前找到合适为止
                else break;//如果arr[j]<=arr[j+1]，那么数组已经“有序了”
            }
            arr[j+1]=tmp;//填好以后一个元素
        }
    }
}

快速排序的稳定性：

不稳定

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/501220