随机快排

思路

• 随机找数组中一个数做基准数；
  
• 颠末一个partition操纵，到达基准数左边的数都比它小，右边的数都比它大。以此固定基准数的位置；
  
• 基准数左侧部门递归做partition操纵；
  
• 基准数右侧部门递归做partition操纵；
  
• 递归的出口是只剩一个元素。
  

partition

功能：颠末一系列比力交换后，使base基准数左边的数都比它小，右边的数都比它大
流程：

• 规定less下标的左边为小于base的区域，more下标的右边为大于base的区域
  
• 用index指针遍历元素，从数组的L遍历到R
  
• 遍历到的数小于base，less右移，less位置和index位置元素交换，index右移
  
• 遍历到的数便是base index右移
  
• 遍历到的数大于base，more左移，more位置与index位置元素交换，index不动
  

代码

1.         /**     * 随机快排     */        public static void quickSort(int[] arr, int left, int right) {        if (left >= right) {            return;        }        int base = arr[new Random().nextInt(arr.length)];        int[] cut = partition(arr, base, left, right);        quickSort(arr, left, cut[0]);        quickSort(arr, cut[1], right);    }    /**     * partition，即荷兰国旗问题     */    public static int[] partition(int[] arr, int base, int left, int right) {        int less = left - 1;        int more = right + 1;        int index = left;        while (index < more) {            if (arr[index] < base) {                less++;                exchange(arr, less, index);                index++;            } else if (arr[index] == base) {                index++;            } else {                more--;                exchange(arr, more, index);            }        }        return new int[]{less, more};    }    public static void exchange(int[] arr, int minIndex, int index) {        int temp = arr[minIndex];        arr[minIndex] = arr[index];        arr[index] = temp;    }

复制代码

来源：https://blog.csdn.net/weixin_44713050/article/details/111992591
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！