纠错：Java随机快速排序

Question

Java随机快速排序，代码能跑，但是结果不对。

import java.util.Random;

public class QuickSort {

    /* 快速排序函数 */
    public static void quickSort(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;
 
            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+" ");
    }
}

Answer 1

import java.util.Random;
public class QuickSort {
  /* 快速排序函数 */
  public static void quickSort(int[] arr, int left, int right) {
    // 如果队首元素小于队尾元素
    if (left < right) {
      // 定义基准数，记录队列的始末。
      int pivot = arr[left]; //here 不用随机
      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[] arr = {1,2,7,4,6,5,3};
    // 定义队首、队尾位置的索引
    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 + " ");
  }
}