当前位置：移动技术网 > IT编程>开发语言>Java > 荐 java算法-快排-快排的三种方式（单向、双向、三区、非递归、快排稳定化实现、螺母螺丝问题）

荐 java算法-快排-快排的三种方式（单向、双向、三区、非递归、快排稳定化实现、螺母螺丝问题）

2020年07月22日 | 移动技术网IT编程 | 我要评论

快排

单向
双向
三路划分快排
非递归形式
快排稳定化
快排稳定化2
螺丝与螺帽问题

单向

在这里插入图片描述

代码：

    private  int partition(int[] arr, int L, int R){
        //随机基准值
        int randomIndex = new Random().nextInt(R-L+1)+L;
        swap(arr,L,randomIndex);
        int pivot = arr[L];
        int lt = L;
        // 循环不变量：
        // all in [L + 1, lt] < pivot
        // all in [lt + 1, i-1) >= pivot
        for (int i=L+1; i<=R ;i++){
            if (arr[i]<pivot){
                lt++;
                swap(arr,i,lt);
            }
        }
        swap(arr,L,lt);
        return lt;
    }

双向

在这里插入图片描述

写法一：

    private  int partition(int arr[], int L, int R){
        int randomIndex = new Random().nextInt(R-L+1)+L;
        swap(arr,L,randomIndex);
        int pivot = arr[L];
        int lt = L+1;
        int gt = R;
        // 循环不变量：
        // all in [left + 1, lt) <= pivot
        // all in (gt, right] >= pivot
        while (true){
        //与pivot相等的两边都不动，如果相等都换到对面，则交换后必须lt++，gt--，否则会出现死循环
            while (lt<=R && arr[lt]<=pivot) lt++;
            while (gt>L && arr[gt]>=pivot) gt--;
            if (lt>=gt) break;
            swap(arr,lt,gt);
            lt++;
            gt--;
        }
        //最终gt停在<=P的地方，与P交换保持循环不变量
        swap(arr,L,gt);
        return gt;
    }

写法二：
在这里插入图片描述

private  int partitionII(int arr[], int L, int R){
        int randomIndex = new Random().nextInt(R-L+1)+L;
        swap(arr,L,randomIndex);
        int pivot = arr[L];
        //注意此处i必须从L开始，比如只有两个值，会立即结束循环，
        // 此时j可能停在大于Pivot的地方，交换L、j将破坏循环不变量
        int i = L;
        int j = R;
        //循环不变量
        //arr[L+1,i] <= P
        //arr[j,R] >= P
        while (i<j){
            //最好两个都写等号，这样与pivot相等的不动，j可以写成>,但i值必须<=，否则L值会产生移动，破坏循环不变量
            while (i<j && arr[j]>= pivot) j--;
            while (i<j && arr[i]<= pivot) i++;
            // 情况1：各自找到符合条件的，交换后保持循环不变量；
            // 情况2：i、j相遇，交换自身，保持循环不变量
            swap(arr,i,j);
        }
        //结束循环的条件必定是i==j
        //必须是j先向左移动，
        //分两种情况：
        // 1、j向左移动时遇到i停下，终止循环，此时j所在值 <=P,swap(arr,L,j)能保持循环不变量
        // 2、j找到小于P的停下，然后i向右遇到j，终止循环，此时j所在值 < P,swap(arr,L,j)能保持循环不变量
        //但如果i先向右移动，遇到j后停下，i/j所在值 >=P ,swap(arr,L,j)后就不能保持循环不变量
        swap(arr,L,j);
        return j;
    }

写法三：
写法三与二类似，只是交换方式改为挖坑填数法
在这里插入图片描述

    private  int partitionIII(int arr[], int L, int R) {
        int randomIndex = new Random().nextInt(R - L + 1) + L;
        swap(arr, L, randomIndex);
        int pivot = arr[L];
        int i = L;
        int j = R;
        //循环不变量
        //arr[L，i] <= P
        //arr[j,R] >= P
        while (i<j){
            while (i<j && arr[j]>=pivot) j--;
            if (i<j){
                arr[i] = arr[j];
                i++;
            }
            while (i<j && arr[i]<=pivot) i++;
            if (i<j){
                arr[j] = arr[i];
                j--;
            }
        }
        arr[j] = pivot;
        return j;
    }

三路划分快排

在这里插入图片描述

public void quickSort(int[] arr,int L,int R){
        if (L < R){
            int randomIndex = new Random().nextInt(R-L+1)+L;
            swap(arr,L,randomIndex);
            int pivot = arr[L];
            int lt = L;
            int i = L+1;
            int gt = R+1;
            //循环不变量
            //arr[L+1,lt]<P
            //arr[lt+1,i-1]=P
            //arr[gt,R]>P
            while (i<gt){
                if (arr[i]<pivot){
                    lt++;
                    swap(arr,lt,i);
                    i++;
                }else if (arr[i]==pivot){
                    i++;
                }else {
                    gt--;
                    swap(arr,i,gt);
                }
            }
            swap(arr,L,lt);
            //下次递归左右边界大大减少，arr[lt,gt-1]=P;
            quickSort(arr,L,lt-1);
            quickSort(arr,gt,R);
        }
    }

参考：
深入理解快速排序和STL的sort算法
 循环不变式，和快速排序算法的多种实现
 力扣

非递归形式

partition与递归完全相同，区别在于非递归使用栈或队列保存每次partition后得到的左右两边的边界，注意栈和队列存取左右边界的顺序。队列是BFS，栈是DFS
完整代码：

    public int[] sort(int[] arr){
        quickSort(arr,0,arr.length-1);
        return arr;
    }
    public void quickSort(int[] arr,int start,int end){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        queue.offer(end);
        while (!queue.isEmpty()){
            int L = queue.poll();
            int R = queue.poll();
            if (L<R){
                int mid = partition(arr,L,R);
                //左边左边界、有边界
                queue.offer(L);
                queue.offer(mid-1);
                //右边左边界、有边界
                queue.offer(mid+1);
                queue.offer(R);
                //下一次迭代
            }
        }
    }
    public int partition(int[] arr,int L,int R){
        int randomIndex = new Random().nextInt(R-L+1)+L;
        swap(arr,L,randomIndex);
        int pivot = arr[L];
        int i = L;
        int j = R;
        while (i<j){
            //循环不变量
            //arr[L,i-1]<=P
            //arr[j+1,R]>=P
            while (i<j && arr[j] >= pivot) j--;
            if (i<j){
                arr[i] = arr[j];
                i++;
            }
            while (i<j && arr[i] <= pivot) i++;
            if (i<j){
                arr[j] = arr[i];
                j--;
            }
        }
        arr[j] = pivot;
        return j;
    }
    public void swap(int[] arr,int L,int R){
        int temp = arr[L];
        arr[L] = arr[R];
        arr[R] = temp;
    }

参考：快速排序的递归方式和非递归方式

快排稳定化

快速排序丢失了稳定性，如果需要稳定的快速排序，需要具体定义比较函数，这个过程叫「稳定化」
在这里插入图片描述
这里用PackingInt类封装数据和数组索引，定义了比较函数，这样任意数都不肯相等，最终得到稳定的快速排序结果。快排方法使用三路快排

全部代码：

public class StableQuickSort {
    public int[] sort(int[] arr){
        //封装原整型数组
        PackingInt[] newArr = new PackingInt[arr.length];
        for (int i = 0; i < newArr.length; i++) {
            newArr[i] = new PackingInt(arr[i],i);
        }
        System.out.println("newArray未排序："+Arrays.toString(newArr));
        quick_sort(newArr,0,arr.length-1);
        System.out.println("newArray已排序："+Arrays.toString(newArr));
        for (int i = 0; i < newArr.length; i++) {
            arr[i] = newArr[i].val;
        }
        return arr;
    }
    //三路划分快速排序
    public void quick_sort(PackingInt[] arr,int start,int end){
        if (start<end){
            //划分
            //随机基准值
            int randomIndex = new Random().nextInt(end-start+1)+start;
            swap(arr,start,randomIndex);
            PackingInt pivot = arr[start];
            int lt = start;
            int gt = end + 1;
            int i = start+1;
            while(i<gt){
                if (arr[i].compareTo(pivot)<0){
                    lt++;
                    //交换的是处理过的等于pivot值或i自身，i++
                    swap(arr,i,lt);
                    i++;
                }else if (arr[i].compareTo(pivot)>0){
                    gt--;
                    //交换的是未处理区的数据，不用i++
                    swap(arr,i,gt);
                }else {
                //这种情况不会出现，因为每个数的索引唯一
                    i++;
                }
            }
            swap(arr,start,lt);
            //分治
            //严格小于基准值的继续递归排序
            quick_sort(arr,start,lt-1);
            //严格大于基准值的继续递归排序
            quick_sort(arr,gt,end);
        }
    }

    // 交换函数也要些微改变
    public void swap(PackingInt[] arr ,int i ,int j){
        PackingInt temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

/**
 * @Description 封装int数，加上其索引值
 */
class PackingInt implements Comparable{
    int val;
    //待排序数组的索引
    int index;

    public PackingInt() {
    }
    public PackingInt(int val, int index) {
        this.val = val;
        this.index = index;
    }

    @Override
    public String toString() {
        return "val="+this.val+",index="+this.index;
    }

    //先比较val，在比较索引
    @Override
    public int compareTo(Object pint) {
        PackingInt pi = (PackingInt) pint;
        if (pi.val != this.val){
            return this.val-pi.val;
        }else {
            return this.index-pi.index;
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5,2,1,3,2,5,1,5,2,1,3,2,5,1,5,2,1,3,2,5,1,5,2,1,3,2,5,1,5,2,1,3,2,5,1};
        StableQuickSort stableQuickSort = new StableQuickSort();
        stableQuickSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

打印结果：

newArray未排序：[val=5,index=0, val=2,index=1, val=1,index=2, val=3,index=3, val=2,index=4, val=5,index=5, val=1,index=6, val=5,index=7, val=2,index=8, val=1,index=9, val=3,index=10, val=2,index=11, val=5,index=12, val=1,index=13, val=5,index=14, val=2,index=15, val=1,index=16, val=3,index=17, val=2,index=18, val=5,index=19, val=1,index=20, val=5,index=21, val=2,index=22, val=1,index=23, val=3,index=24, val=2,index=25, val=5,index=26, val=1,index=27, val=5,index=28, val=2,index=29, val=1,index=30, val=3,index=31, val=2,index=32, val=5,index=33, val=1,index=34]
newArray已排序：[val=1,index=2, val=1,index=6, val=1,index=9, val=1,index=13, val=1,index=16, val=1,index=20, val=1,index=23, val=1,index=27, val=1,index=30, val=1,index=34, val=2,index=1, val=2,index=4, val=2,index=8, val=2,index=11, val=2,index=15, val=2,index=18, val=2,index=22, val=2,index=25, val=2,index=29, val=2,index=32, val=3,index=3, val=3,index=10, val=3,index=17, val=3,index=24, val=3,index=31, val=5,index=0, val=5,index=5, val=5,index=7, val=5,index=12, val=5,index=14, val=5,index=19, val=5,index=21, val=5,index=26, val=5,index=28, val=5,index=33]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]

结论：利用额外空间，具体定义比较函数可以实现快速排序稳定化

快排稳定化2

还有一种思路是：原先交换会使偏左的跑到偏右，如果有相同值就会改变相对顺序，比如
[(2,0),(4,1),(4,2),(1,3),(1,4)]，
第一次排序后：[(2,0),(1,4),(4,2),(1,3),(4,1)]，
第二次排序：[(2,0),(1,4),(1,3),(4,2),(4,1)]，

显然(1,4),(1,3)相对顺序改变，而快排无法区分其相对顺序。
但如果利用额外空间先储存待交换的数据，结束循环后再整体平移是不是就能不打乱相对顺序了呢

左侧大于基准值的放于额外空间左侧，后一位数左移；右侧小于基准值的放于额外空间右侧，后一位右移
继续相同操作
结束循环将基准值放于移动指针结束处，额外空间中大于基准值的平移到原数组右侧，小于基准值的平移到原数组左侧
最后形成的数组中，相同值的相对顺序不变。继续下一轮递归

具体思路和代码参考：稳定快速排序算法研究·邵顺增·2011

螺丝与螺帽问题

在这里插入图片描述
思路：

将螺丝螺帽分为两堆，分别是n个螺丝，定为 bolts[n]，n个螺母，定为nuts[n]
从bolts[n]选出一个螺丝pivot_bolt作为螺母数组的基准值进行一次快排，完全匹配的pivot_nut作为螺丝数组的基准值进行一次快排，这样就排序了一对螺母螺丝，递归快排即可完成全部匹配

完整代码：

public class NutAndBolt {
    public static void main(String[] args) {
        int[] nuts = new int[]{1,1,5,1,6,3,2,5,2,5,1,6,3,2,5,3,3,3,3,3,3,3,3,3};
        int[] bolts = new int[]{3,2,5,3,3,3,1,1,2,5,1,6,3,3,3,3,3,3,5,1,6,3,2,5};
        NutAndBolt nutAndBolt = new NutAndBolt();
        nutAndBolt.sort(nuts,bolts);
        System.out.println(Arrays.toString(nuts));
        System.out.println(Arrays.toString(bolts));
    }
    public void sort(int[] nuts,int[] bolts){
        quickSort(nuts,bolts,0,bolts.length-1);
    }
    public void quickSort(int[] nuts,int[] bolts,int start,int end){
        if (start<end){
            //取nuts的一个值作为bolts的基准值,直接定为start
            int pivot = nuts[start];
            //返回划分中值
            int mid_bolts = partition(bolts,start,end,pivot);
            //同样以pivot作为nuts的基准值，进行快排，返回mid值相同
            int mid_nuts = partition(nuts,start,end,pivot);
            System.out.println(mid_bolts +","+mid_nuts);
            //继续递归排序
            quickSort(nuts,bolts,start,mid_bolts-1);
            quickSort(nuts,bolts,mid_bolts+1,end);
        }
    }
    //根据指定pivot划分数组
    public int partition(int[] arr,int start,int end,int pivot){
        int pivot_index = -1;
        //注意这里从start搜索到end，找到以一个等于pivot的索引，与start进行交换
        //一定要注意不是从0开始到数组尾
        for (int i = start; i <= end; i++) {
            if (pivot == arr[i]) {
                pivot_index = i;
                break;
            }
        }
        swap(arr,start,pivot_index);
        int i = start;
        int j = end;
        while (i<j){
            //等于基准值的都放右侧，防止与基准值相同的处于两侧，使两数组长度不一致
            while (i<j && arr[j]>=pivot) j--;
            if (i<j){
                arr[i] = arr[j];
                i++;
            }
            //注意不要写等号
            while (i<j && arr[i]<pivot) i++;
            if (i<j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[j] = pivot;
        return j;
    }
    public void swap(int[] arr,int start,int end){
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }
}

打印：

...//mid_bolts 与 mid_nuts 都相同
19,19
22,22
20,20
[1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 6, 6]
[1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 6, 6]

结果正确

本文地址：https://blog.csdn.net/weixin_44013533/article/details/107483636

您可能感兴趣的文章:

如对本文有疑问，点击进行留言回复！！

两大注册中心比较（Zookeeper,Eureka）

简介Eureka是一款由Netflix提供的开源的服务注册和发现的产品，并能够提供相应的Java封装。在实现的时... [阅读全文]
unity的错误解决办法：NullReferenceException: Object reference not set to an instance of an object；tiny proje

普通unity项目正常的项目中，这是个非常初级的错误。比较常见的原因是就是在对象被引用前没有实例化。即是说，你要... [阅读全文]
Hadoop 之 HDFS (HDFS 数据流的读写流程)

文章目录四、HDFS 的数据流（面试重点）4.1 HDFS 的数据流程4.1.1 剖析文件写入4.1.2 网络... [阅读全文]
听说你一读Spring源码就懵逼？我帮你把架子搭好了，你填就行！

最近断更了一段时间，因为公司比较忙，周五的时候在公司做了一个关于Netty的分享，后续会总结一下分享出来！最近一... [阅读全文]
Spring概述

文章目录1 什么是Spring2 Spring框架的优点3 Spring的体系结构3.1 Core Contai... [阅读全文]
Mybatis培训笔记

Mybatis课堂笔记1.学习内容SSM三大框架： Spring SpringMVC Mybatis (ib... [阅读全文]
朱老师嵌入式S5PV210时钟系统学习笔记

朱老师嵌入式S5PV210时钟系统学习笔记前期准备工作一、SoC时钟系统简介1.1、什么是时钟？SoC为什么需要... [阅读全文]
首席架构师推荐：金融保险领域数字化转型实践--如何优雅地修改业务中台中分层应用Maven多模块的版本号?(命令导入式)

我们在中台构建中提供了底层的中台能力服务的基础中间件构建，其应用架构沿用阿里的风格，使用了分包的应用架构方式。在... [阅读全文]
[JVM学习之路]一、初识JVM，了解其结构、模型及生命周期

JVM入门简介一、JVM位置JVM是运行在操作系统之上的，与硬件之间没有直接的联系二、JVM的整体结构方法区和堆... [阅读全文]
从 Exadata 到 TiDB，中通快递 HTAP 实践

作者介绍：朱志友，中通快递大数据架构师。中通快递背景介绍中通快递业务的规模目前是世界第一，是第一个达成年百亿业务... [阅读全文]