算法-随机快排及荷兰国旗优化

文章目录

- 算法介绍 :
- 1. 随机快排解析
- 2. 荷兰国旗问题
- 3. 随机快排优化
- 4. 总结随机快排

算法介绍 :

随机快速排序和传统的快速排序的逻辑本质是一致的,都是找到一个值作为划分的中间位置,左边数值均小于该数值,右边数值均大于该数值,但是与传统的快排又不一致的是,我们的这个位置是通过随机获得的,对于随机行为的时间复杂度不能简单的按照最坏的情况解读

1. 随机快排解析

下面是我们随机快排的代码实现

public class Sort {
    public static void quickSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        quickSort(nums, 0, nums.length - 1);
    }

    //下面是经典版本随机快排的函数主体
    private static void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        //在left -- right范围上随机出来一个数字
        int randn = nums[left + (int) (Math.random() * (right - left + 1))];
        int boundary = partiton(nums, left, right, randn);
        quickSort(nums, left, boundary - 1);
        quickSort(nums, boundary + 1, right);
    }

    //经典快排的partition过程
    private static int partiton(int[] nums, int left, int right, int randn) {
        //逐个遍历的下标
        int i = left;
        //用来区别 <= randn的边界位置(已经越界了)
        int j = left;
        //记录找到的x的位置(用于交换)
        int randIndex = left;
        while (i <= right) {
            if (nums[i] <= randn) {
                swap(nums, i, j);
                if (nums[j] == randn) {
                    randIndex = j;
                }
                i++;
                j++;
            } else {
                i++;
            }
        }
        swap(nums, j - 1, randIndex);
        return j - 1;
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

下面主要解析一下上述代码的逻辑是什么
首先我们通过
(int)(Math.random()*(right - left + 1)) + left
这段代码可以随机产生一个left – right的下标值
然后我们就拿到该位置的随机数作为划分
之后通过partiton过程来进行快排的逻辑,其中定义了两个指针,一个遍历数组下标,一个进行边界位置的扩大,当遍历到随机数的时候我们就记录下来该随机数的下标,然后通过左右区间调用递归过程完成排序, 但是这个快排的逻辑在leetcode上是跑不过全部的,因为你一轮只能排出来一个数据

2. 荷兰国旗问题

在这里插入图片描述
荷兰国旗问题可以为我们的接下来的排序优化打下基础, 上面的排序说了我们创造了一个左边界线, 那为什么不创建一个有边界线呢 ? 荷兰国旗就是这样解决的,但是要注意的是,在移动右边界线的时候,遍历的下标值不可以移动,在移动左边界线却可以, 因为左边已经遍历过一轮了, 可以确定交换过来的元素属性,但是右边是不确定的, 代码实现如下

class Solution {
    public void sortColors(int[] nums) {
        int first = 0;
        int last = nums.length - 1;
        int i = 0;
        while(i <= last){
            if(nums[i] == 0){
                swap(nums,i++,first++);
            }else if(nums[i] == 1){
                i++;
            }else{
                swap(nums,i,last--);
            }
        }
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

3. 随机快排优化

有了上面的荷兰国旗的基础,我们的快排优化也是这样做的,逻辑也是定出来两个边界,然后逐个进行移动…
代码实现如下


    /**
     * 下面是根据荷兰国旗问题的改进版本(分为三个区间, 一次搞定一批)
     * 下面这个两个属性是左右边界的越界位置
     */
public class Sort{
    public int first = 0;
    public int last = 0;

    public void quickSortImprove(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        quickSortImprove(nums, 0, nums.length - 1);
    }

    public void quickSortImprove(int[] nums,int left,int right){
        if (left >= right) {
            return;
        }

        int randn = nums[left + (int) (Math.random() * (right - left + 1))];
        partitonImprove(nums,left,right,randn);
        int fir = first;
        int la = last;
        quickSortImprove(nums,left,fir - 1);
        quickSortImprove(nums,la + 1, right);
    }
    private void partitonImprove(int[] nums,int left,int right,int randn){
        first = left;
        last = right;
        int i = left;
        while(i <= last){
            if(nums[i] < randn){
                swap(nums,i++,first++);
            }else if(nums[i] == randn){
                i++;
            }else{
                swap(nums,i,last--);
            }
        }
    }
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}