Java，将快速排序改为随机快速排序

Question

将下面的Java快速排序改为随机快速排序。

public class QuickSort {

    /*快速排序函数*/
    public static void quickSort(int[] arr, int left, int right) {
        
        //如果队首元素小于队尾元素
        if (left < right) {
            
            //定义基准数，记录队列的始末。
            int pivot = arr[left];
            int begin = left;
            int end = right;

            while (right > left) {

                //当队尾元素小于基准数就将队尾插到队首
                if (arr[right] < pivot) {
                    arr[left] = arr[right];
                    left++; //队首索引后移
                } 

                //当队尾元素大于基准数就将队尾索引前移，继续从队尾比较
                else {
                    right--;
                    continue;
                }

                while (right > left) {
                    
                    //当队首元素大于基准数就将队首插到队尾
                    if (arr[left] > pivot) {
                        arr[right] = arr[left];
                        right--;//队尾索引前移
                        break;
                    }

                    //当队首元素小于基准数就将队首索引后移，继续从队首比较
                    else {
                        left++;
                    }
                }
            }
            
            //队首和队尾索引重合，就将基准数插入此位置
            arr[left] = pivot;
 
            quickSort(arr, begin, left - 1);
            quickSort(arr, left + 1, end);
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {8, 45, 0, 30, 49, 16, 20, 20};
        
        //定义队首、队尾位置的索引
        int left = 0;
        int right = arr.length - 1;
        
        System.out.print("排序前的数组：");
        for (int i : arr)
            System.out.print(i+" ");
        System.out.println();
            
        quickSort(arr, left, right);
        
        System.out.print("排序后的数组：");
        for (int i : arr)
            System.out.print(i+" ");
    }
}

我也自己尝试了一下，但是输出的排序不对。

import java.util.Random;

public class RandomQuickSort {

    /* 随机快速排序函数 */
    public static void randomQuickSort(int[] arr, int left, int right) {
        
        // 如果队首元素小于队尾元素
        if (left < right) {
            
            // 随机选取基准数，记录队列的始末。
            int pivot = arr[left + new Random().nextInt(right - left + 1)];
            int begin = left;
            int end = right;

            while (right > left) {

                // 当队尾元素小于基准数就将队尾插到队首
                if (arr[right] < pivot) {
                    arr[left] = arr[right];
                    left++; // 队首索引后移
                } 

                // 当队尾元素大于基准数就将队尾索引前移，继续从队尾比较
                else {
                    right--;
                    continue;
                }

                while (right > left) {
                    
                    // 当队首元素大于基准数就将队首插到队尾
                    if (arr[left] > pivot) {
                        arr[right] = arr[left];
                        right--;// 队尾索引前移
                        break;
                    }

                    // 当队首元素小于基准数就将队首索引后移，继续从队首比较
                    else {
                        left++;
                    }
                }
            }
            
            // 队首和队尾索引重合，就将基准数插入此位置
            arr[left] = pivot;
 
            randomQuickSort(arr, begin, left - 1);
            randomQuickSort(arr, left + 1, end);
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {8, 45, 0, 30, 49, 16, 20, 20};
        
        // 定义队首、队尾位置的索引
        int left = 0;
        int right = arr.length - 1;
        
        System.out.print("排序前的数组：");
        for (int i : arr)
            System.out.print(i+" ");
        System.out.println();
        
        randomQuickSort(arr, left, right);
        
        System.out.print("排序后的数组：");
        for (int i : arr)
            System.out.print(i+" ");
    }
}

Answer 1

【以下回答由 GPT 生成】

我希望在选择基准数时进行随机化，以实现随机快速排序。

【相关推荐】

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7793093
• 你也可以参考下这篇文章：编写Java程序，将数组中最小的数输出。
• 您还可以看一下 徐无忌老师的Java进阶高手课-深入浅出Java网络编程课程中的 案例实战：浏览器打开一个网址，整个过程是怎么样的？小节, 巩固相关知识点
  
• 除此之外, 这篇博客: Java：用户输入矩形的长和宽，使用带返回值的方法求该矩形的面积并输出中的 运行结果： 部分也许能够解决你的问题。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^