算法|5.快速排序相关

超、凢脫俗 2024-03-16 09:27 9阅读 0赞

## 算法|5.快速排序相关 ##

### 1.荷兰国旗问题 ###

题意：给定一个数组arr，以arr\[R\]为划分值，请把arr\[R\]的数放在数组的左边，等于arr\[R\]的数放在数组的中间，大于arr\[R\]的数放在数组的右边，返回等于arr\[R\]的区间。要求额外[空间复杂度][Link 1]为O(1)，时间复杂度为O(n)

解题思路：

*  根据L和R的关系分三种情况讨论：L>R;L==R;L<R
 *  L>R==>\{-1,-1\} LR>\{L,R\}
 *  L<R: <区域右边界——less,>区域左边界——more,遍历指针index
 *  循环条件index<more(小于>区域右边界)：若arr\[index\]和arr\[R\]相等,index++；若arr\[index\]<arr\[R\],index位置和++less位置交换<区域右扩，指针加加；若arr\[index\]>arr\[R\]，index位置和–more位置交换
 *  注意：<时index–和++less（已经检验过了，等于的或者当前的），>时–more和index交换

核心代码：

public static int[] netherlandsFlag(int[] arr,int L,int R){
        
        if(L>R){
        
            return new int[]{
        -1,-1};
        }
        if(L==R){
        
            return new int[]{
        L,R};
        }
        int less=L-1;
        int more=R;
        int index=L;
        while(index<more){
        
            if(arr[index]==arr[R]){
        
                index++;
            }else if(arr[index]<arr[R]){
        
                swap(arr,index++,++less);
            }else{
        
                swap(arr,index,--more);
            }
        }
        swap(arr,R,more);
        return new int[]{
        less+1,more};
    }
    
    private static void swap(int[] arr, int i, int j) {
        
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }

测试代码：

//for test
    public static void main(String[] args) {
        
        int[] arr={
        100,2,37,8,96,4,2,6,7,9,3,45};
        int[] partition=netherlandsFlag(arr,0,arr.length-1);
        System.out.println("划分："+ Arrays.toString(partition));
        System.out.println(Arrays.toString(arr));
    }

测试结果：

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-z6GMDgu6-1685106795384)(F:\\typora插图\\image-20230526203747202.png)\]][img-z6GMDgu6-1685106795384_F_typora_image-20230526203747202.png]

### 2.快速排序3.0 ###

经典版本：小于指定值的放在左边，大于的放右边

递归实现：

//递归方式
    public static void quickSort1(int[] arr){
        
        if(arr==null||arr.length<2){
        
            return ;
        }
        process(arr,0,arr.length-1);
    }
    
    private static void process(int[] arr, int L, int R) {
        
        if(L>=R){
        
            return ;
        }
        //快速排序的优化手段之一——破坏可能存在的完全逆序
        swap(arr, (int) (L+Math.random()*(R-L+1)),R);//L~(R-L)-1
        int[] equalArea=netherlandsFlag(arr,L,R);
        process(arr,L,equalArea[0]-1);
        process(arr,equalArea[1]+1,R );
    }
    
    public static int[] netherlandsFlag(int[] arr,int L,int R){
        
        if(L>R){
        
            return new int[]{
        -1,-1};
        }
        if(L==R){
        
            return new int[]{
        L,R};
        }
        int less=L-1;
        int more=R;
        int index=L;
        while(index<more){
        
            if(arr[index]==arr[R]){
        
                index++;
            }else if(arr[index]<arr[R]){
        
                swap(arr,index++,++less);
            }else{
        
                swap(arr,index,--more);
            }
        }
        swap(arr,R,more);
        return new int[]{
        less+1,more};
    }
    
    private static void swap(int[] arr, int i, int j) {
        
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }

非递归实现：

//非递归方式
    public static class Op{
        
        public int l;
        public int r;
    
        public Op(int l, int r) {
        
            this.l = l;
            this.r = r;
        }
    }
    //顺序调整过程在荷兰国旗内部
    public static void quickSort2(int[] arr){
        
        if(arr==null||arr.length<2){
        
            return ;
        }
        int N=arr.length;
        swap(arr, (int) (Math.random()*N),N-1);//L~(R-L)-1
        int[] equalArea=netherlandsFlag(arr,0,N-1);
        Stack<Op> stack=new Stack<>();
        stack.push(new Op(0,equalArea[0]-1));
        stack.push(new Op(equalArea[1]+1,N-1));
        while(!stack.isEmpty()){
        
            Op op=stack.pop();
            if(op.l<op.r){
        
                swap(arr,op.l+ (int) (Math.random() * (op.r - op.l + 1)), op.r);
                equalArea=netherlandsFlag(arr,op.l, op.r);
                stack.push(new Op(op.l,equalArea[0]-1));
                stack.push(new Op(equalArea[1]+1,op.r ));
            }
        }
    }
    
    //荷兰国旗
    public static int[] netherlandsFlag(int[] arr,int L,int R){
        
        if(L>R){
        
            return new int[]{
        -1,-1};
        }
        if(L==R){
        
            return new int[]{
        L,R};
        }
        int less=L-1;
        int more=R;
        int index=L;
        while(index<more){
        
            if(arr[index]==arr[R]){
        
                index++;
            }else if(arr[index]<arr[R]){
        
                swap(arr,index++,++less);
            }else{
        
                swap(arr,index,--more);
            }
        }
        swap(arr,R,more);
        return new int[]{
        less+1,more};
    }
    
    private static void swap(int[] arr, int i, int j) {
        
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }

测试代码：

isEqual

测试结果：

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4oiDoLUt-1685106795385)(F:\\typora插图\\image-20230526205807883.png)\]][img-4oiDoLUt-1685106795385_F_typora_image-20230526205807883.png]

### 快速排序算法总结 ###

**算法描述：**

**复杂度分析及评价指标：**

*  时间复杂度：平均/最好：O(nlogn)
 *  空间复杂度：平均最好：O(nlogn)
 *  证明忽略
 *  不稳定

**划分：**

*  **荷兰国旗**——大于区左扩，小于区右扩，三个index调整

**例题总结：**

*  荷兰国旗总结：大于区左扩，小于区右扩，index<more，`swap(arr,index++,++less),swap(arr,index,--more);`
 *  快速排序递归实现：荷兰国旗替代M；优化破坏完全逆序结构： `swap(arr, (int) (L+Math.random()*(R-L+1)),R);//L~(R-L)-1`；  
    `pr`ocess(arr,L,equalArea\[0\]-1);`process(arr,equalArea[1]+1,R );`
 *  快速排序非递归实现：`new Op(op.l,op.r);` `if(op.`l<op.r)\{ ``swap(arr,op.l+ (int) (Math.random() \* (op.r - op.l + 1)), op.r);``equalArea=netherlandsFlag(arr,op.l, op.r);``stack.push(new Op(op.l,equalArea\[0\]-1));``stack.push(new Op(equalArea\[1\]+1,op.r ));`th.random() * (op.r - op.l + 1)), op.r);`  
    `equalArea=netherlandsFlag(arr,op.l, op.r);`  
    `stack.push(new Op(op.l,equalArea[0]-1));`  
    `stack.push(new Op(equalArea[1]+1,op.r ));`  
    \}\`

[Link 1]: https://so.csdn.net/so/search?q=%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6&spm=1001.2101.3001.7020
[img-z6GMDgu6-1685106795384_F_typora_image-20230526203747202.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/2e1d06baa88b4aa999d1a74f0778b9f9.png
[img-4oiDoLUt-1685106795385_F_typora_image-20230526205807883.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/50de64e71e8345d48c2a8666aa122676.png