java - 使用随机枢轴元素而不是中间元素代码进行快速排序

Question

我有以下运行良好的代码，但任何人都可以告诉我如何更改算法以使用随机枢轴元素。

而不是下面，我想随机选择枢轴元素，任何帮助将不胜感激

      int pivot = arr[(left + right) / 2];

import java.util.Random;


public class QuickSort {

    /**
     * @param args
     */
    public static void main(String[] args) {

          int i;
          int array[] = {10,9,1,2,3,4,100,200,300,400};  
          System.out.println(" Quick Sort\n\n");
          System.out.println("Values Before the sort:\n");
          for(i = 0; i < array.length; i++)
          System.out.print( array[i]+"  ");
          System.out.println();
          quickSort(array,0,array.length-1);
          System.out.print("Values after the sort:\n");
          for(i = 0; i <array.length; i++)
          System.out.print(array[i]+"  ");
          System.out.println(); 

    }

    public static int partition(int arr[], int left, int right)
    {
          int i = left, j = right;
          int tmp;



          int pivot = arr[(left + right) / 2];

          while (i <= j) {
                while (arr[i] < pivot)
                      i++;
                while (arr[j] > pivot)
                      j--;
                if (i <= j) {
                      tmp = arr[i];
                      arr[i] = arr[j];
                      arr[j] = tmp;
                      i++;
                      j--;
                }
          };

          return i;
    }

    public static void quickSort(int arr[], int left, int right) {
          int index = partition(arr, left, right);
          if (left < index - 1)
                quickSort(arr, left, index - 1);
          if (index < right)
                quickSort(arr, index, right);
    }

}

Answer 1

将主变量赋值替换为:

int pivot = arr[left + rnd.nextInt(right - left)];

其中 rnd 是一个类 Random 对象，您可以将其设置为私有(private)静态最终字段。