欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-15 19:16:46
快排单向双向三路划分快排非递归形式快排稳定化快排稳定化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;...

单向

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

代码:

    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;
    }

双向

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

写法一:

    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;
    }

写法二:
java算法-快排-快排的三种方式(单向、双向、三区、非递归、快排稳定化实现、螺母螺丝问题)

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;
    }

写法三:
写法三与二类似,只是交换方式改为挖坑填数法
java算法-快排-快排的三种方式(单向、双向、三区、非递归、快排稳定化实现、螺母螺丝问题)

    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;
    }

三路划分快排

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

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;
    }

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

快排稳定化

快速排序丢失了稳定性,如果需要稳定的快速排序,需要具体定义比较函数,这个过程叫「稳定化」
java算法-快排-快排的三种方式(单向、双向、三区、非递归、快排稳定化实现、螺母螺丝问题)
这里用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)相对顺序改变,而快排无法区分其相对顺序。
但如果利用额外空间先储存待交换的数据,结束循环后再整体平移是不是就能不打乱相对顺序了呢

  1. 左侧大于基准值的放于额外空间左侧,后一位数左移;右侧小于基准值的放于额外空间右侧,后一位右移
    java算法-快排-快排的三种方式(单向、双向、三区、非递归、快排稳定化实现、螺母螺丝问题)
  2. 继续相同操作
    java算法-快排-快排的三种方式(单向、双向、三区、非递归、快排稳定化实现、螺母螺丝问题)
  3. 结束循环将基准值放于移动指针结束处,额外空间中大于基准值的平移到原数组右侧,小于基准值的平移到原数组左侧
    java算法-快排-快排的三种方式(单向、双向、三区、非递归、快排稳定化实现、螺母螺丝问题)
  4. 最后形成的数组中,相同值的相对顺序不变。继续下一轮递归
    java算法-快排-快排的三种方式(单向、双向、三区、非递归、快排稳定化实现、螺母螺丝问题)

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

螺丝与螺帽问题

java算法-快排-快排的三种方式(单向、双向、三区、非递归、快排稳定化实现、螺母螺丝问题)
思路:

  1. 将螺丝螺帽分为两堆,分别是n个螺丝,定为 bolts[n],n个螺母,定为nuts[n]
  2. 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