【DS】9.快速排序大总结！！！

左手的ㄟ右手 2024-04-01 09:44 55阅读 0赞

> ***基本思想***
> 
> ①首先设定一个分界值，我们把它叫做基准值，根据基准值将数组元素分为左右两部分。
> 
> ②将大于等于基准的值全部移动到数组右边，将小于基准的值移动到数组左边。完成此操作后，左边的数据全部小于基准，右边的数据全部大于等于基准。
> 
> ③之后，左边和右边的数据也可以进行独立排序。对于左边的数据，可以选一个分界值，大于等于的放在“子数组”的右边，小于放在“子数组”左边，右边同理。
> 
> ④重复上述操作，当两边都排好的时候，整个数组也就有序了。
> 
> 时间复杂度：最好：O（nlogn）；最坏：O（n^2）平均：O（nlogn）
> 
> 空间复杂度：O（logn）【递归压栈出栈，联系树的高度】
> 
> 稳定性：不稳定
> 
> 关于快排时间复杂度的分析：它的二叉树遍历有点相似，最好是完全二叉树logn的情况,最坏是单分支的n的情况，
> 
> 优先挖坑法、其次hoare法，最后前后指针法  
> 另后序可能还会再补充【思路分析、步骤拆分图、代码注释……】。

#### 文章目录 ####

*   *  一、Hoare版快排
     *   *  partition实现思路
         *  动图演示
         *  代码实现
     *  二、挖坑法快排
     *   *  partition实现思路
         *  动图演示
         *  代码实现
     *  三、前后指针法快排
     *   *  partition实现思路
         *  动图演示
         *  代码实现
     *  四、快速排序递归法的优化【三数取中法&插排】
     *   *  优化思路
         *  代码实现
     *  五、快速排序的非递归实现
     *   *  思想描述
         *  代码描述

### 一、Hoare版快排 ###

#### partition实现思路 ####

1.  每次处理问题之前保存子数组开始的下标（相对于元素组），令子数组的首元素做基准,begin为子数组的首元素，end为子数组的尾元素。
2.  外循环条件是左下标永远小于右下标，这保证当两个变量相遇的时候能够结束此次调整。
3.  两个内循环分别控制两个变量的移动，左变量永远找大于等于基准的值的下标，右变量永远找小于等于基准值的下标，一旦找到就停止内循环。**特别注意：内循环循环条件需要加上一个begin<end的边界条件并且必须在前边（逻辑与运算符的使用），不然可能在内循环时出现越界的/明显不符合条件的情况。**
4.  外循环一次交换一次，最后一次相遇了的时候，让原来的begin(即tmp)和现在的begin进行交换，这个时候相遇位置就是此次结束后基准的位置
5.  将begin返回给上一级，又是一个新的子问题。这样，子问题的划分就完成了。

另外还有两个问题需要特别强调一下：

1.为什么要从右边开始找比基准小的

> 左边的值如果没找到，左右哨兵有可能提前相遇，导致基准左边有比基准大的。例如：6、1、2、5、4、9、3

2.array\[right\] >= pivot 为什么取等号

> 使得相等的时候程序也能正常执行，否则会死循环

#### 动图演示 ####

![在这里插入图片描述][dfd8c7bfa7b74fa18a7a82f554e21fab.gif_pic_center]

#### 代码实现 ####

public static void quickSort(int[]array) {
        
        quickSortChild(array,0, array.length-1);
        return ;
    }
    private static void quickSortChild(int[]array, int left, int right){
        
        if(left>=right){
        
            return ;
        }
        int pivot= partitionHoare(array,left,right);
        quickSortChild(array,left,pivot);
        quickSortChild(array,pivot+1,right);
    }
    private static int partitionHoare(int[]array, int begin, int end){
        
        int tmp=begin;
        int pivot=array[begin];
        while(begin<end){
        
            while (begin<end&&array[end]>=pivot){
        
                end--;
            }
            while(begin<end&&array[begin]>=pivot){
        
                begin++;
            }
            swap(array,begin,end);
        }
        swap(array,tmp,begin);
        return begin;
    }
    private static void swap(int[]array,int a,int b){
        
        int tmp=array[a];
        array[a]=array[b];
        array[b]=tmp;
    }

### 二、挖坑法快排 ###

#### partition实现思路 ####

1.  还是原来的方法确定begin、end、pivot的值，但是这里我们是拿一个临时空间tmp拿到最开始begin位置的数据，相当于那里是个坑。
2.  然后end从右边开始找比pivot小的数，找到后，直接放到begin位置，相当于形成一个新的坑，begin从前往后找到的比pivot大的数放到那个坑中，然后end继续从后往前走又找到一个比pivot小的，重复直至begin和end相遇。
3.  此时，将tmp的值赋给相遇位置，结束！

#### 动图演示 ####

![在这里插入图片描述][b924563492684de48ccb72598587502c.gif_pic_center]

#### 代码实现 ####

public static void quickSort(int[]array) {
        
        quickSortChild(array,0, array.length-1);
    }
    private static void quickSortChild(int[]array, int left, int right){
        
        if(left>=right){
        
            return ;
        }
        int pivot= partitionHoare(array,left,right);
        quickSortChild(array,left,pivot);
        quickSortChild(array,pivot+1,right);
    }
    private static int partitionDigHole(int[]array, int begin, int end){
        
        int pivot=array[begin++];
        while(begin<end){
        
            while (begin<end&&array[end]>=pivot){
        
                end--;
            }
            array[begin]=array[end];
            while(begin<end&&array[begin]>=pivot){
        
                begin++;
            }
            array[end]=array[begin];
        }
        array[begin]=pivot;
        return begin;
    }

### 三、前后指针法快排 ###

#### partition实现思路 ####

1.  定义两个指针，一个prev，一个cur，prev初值是begin的位置，cur初值是begin+1的位置
2.  prev每次都指向从左到右第一个大于基准的数
3.  如果cur的值大于基准值，cur++；如果cur指向的值小于基准值，prev++；判断是不是与cur的位置相同，不相等，交换cur和prev的值，直到cur>end
4.  交换prev和基准的值，这样基准的位置也确定了

#### 动图演示 ####

![在这里插入图片描述][58428f0fa36c4341a61f91703235bbaf.gif_pic_center]

#### 代码实现 ####

public static void quickSort(int[]array) {
        
        quickSortChild(array,0, array.length-1);
        return ;
    }
    private static void quickSortChild(int[]array, int left, int right){
        
        if(left>=right){
        
            return ;
        }
        int pivot= partitionHoare(array,left,right);
        quickSortChild(array,left,pivot);
        quickSortChild(array,pivot+1,right);
    }
    private static int partitionDoublePointers(int[]array, int begin, int end){
        
        int pivot=array[begin];
        int prev=begin;
        int cur=begin+1;
        while(cur<=end){
        
            if(array[cur]<=pivot&&++prev!=cur){
        
                swap(array,prev,cur);
            }
            cur++;
        }
        swap(array,prev,begin);
        return prev;
    }
    private static void swap(int[]array,int a,int b){
        
        int tmp=array[a];
        array[a]=array[b];
        array[b]=tmp;
    }

### 四、快速排序递归法的优化【三数取中法&插排】 ###

> 为什么要优化？原来的效率差在哪里？
> 
> 当数据有序的时候，快速排序的时间复杂度可以达到O（n^2），时间复杂度也会变大。
> 
> 相当于变成一棵单分支的树，这时我们的end基本要遍历所有的数组元素，每次差不多都是这样，这时效率极大降低。
> 
> 另外，当数据量非常小的时候，可以采用插入排序

#### 优化思路 ####

1.  事先对数据进行处理，取一个大小比较接近中位数的数做基准
2.  我们一般是取开头，中间，结尾的中位数，这里我们写了一个函数findMidValIndex
3.  拿到对应下标后，将left和index进行交换，在quickSortChild部分对处理区间进行调整

只给出quickSortChild部分代码，partition部分代码不需要调整。

#### 代码实现 ####

private static void quickSortChildOptimize(int[]array, int left, int right){
        
       if(left>=right){
        
           return ;
       }
       if(right-left+1<=15){
        
           insertSort(array,left,right);
           return;
       }
       int index=findMidVlOfIndex(array,left,right);
       swap(array,left,index);
       int pivot= partitionHoare(array,left,right);
       quickSortChild(array,left,pivot);
       quickSortChild(array,pivot+1,right);
    }
    private static void insertSort(int[]array,int left,int right){
        
       for (int i = left+1; i <= right; i++) {
        
           int j=i-1;
           int tmp=array[i];
           for (;  j>=left ; j--) {
        
               if(array[j]>tmp){
        
                   array[j+1]=array[j];
               }else{
        
                   break;
               }
           }
           array[j+1]=tmp;
       }
    }

### 五、快速排序的非递归实现 ###

#### 思想描述 ####

1.  用栈来模拟递归

#### 代码描述 ####

public static void quickSort(int[] array) {
        
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        int end = array.length-1;
        int pivot = partition(array,start,end);
        //1.判断左边是不是有2个元素
        if(pivot > start+1) {
        
            stack.push(start);
            stack.push(pivot-1);
        }
        //2.判断右边是不是有2个元素
        if(pivot < end-1) {
        
            stack.push(pivot+1);
            stack.push(end);
        }
        while (!stack.isEmpty()) {
        
            end = stack.pop();
            start = stack.pop();
            pivot = partition(array,start,end);
            //3.判断左边是不是有2个元素
            if(pivot > start+1) {
        
                stack.push(start);
                stack.push(pivot-1);
            }
            //4.判断右边是不是有2个元素
            if(pivot < end-1) {
        
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }

[dfd8c7bfa7b74fa18a7a82f554e21fab.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/fc619b886fff4c24812f17a9bb47c79d.gif
[b924563492684de48ccb72598587502c.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f9a1214e91454d2086a2fa8c202cbdef.gif
[58428f0fa36c4341a61f91703235bbaf.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f982fae8ebe54264bf30b04276f1c585.gif