java - 从三个项目的中位数中选择Pivot QuickSort(JAVA)

Question

我一直在研究我的一个与快速排序实现相关的程序。下面的代码是一个快速排序算法，它选择三个元素的中位数作为基准。但问题是我有兴趣选择数组的前三个元素作为基准，而不是(子数组的最低、中间和最高索引)。例如:如果我在数组中有数字 5、85、65、4、75，我将能够比较数组中的前三个元素 (5、85、65) 以获得中位数，在本例中为 65 . 对于此事的任何反馈，我将不胜感激。

public class QuickSort123
{

    public static void main(String[] args) 
    {
        int[] array = { 14, 9, 28, 3, 7, 63, 89, 5};

        // invoking methods
        printArray(array);
        sort(array);
        printArray(array);
    }

    public static void sort(int[] array)
    {
        quickSort(array, 0, array.length - 1);
    }

    public static void quickSort(int[] array, int low, int high)
    {

       if (low >= high)
       return;

       // Selecting the  pivot
       int middle = low + (high - low) / 2;
       int pivot = array[middle];

       while (low <= high) 
       {
            while (array[low] < pivot)
            {
                 low++;
            }

            while (array[high] > pivot) 
            {
                 high--;
            }

            if (low <= high)
            {
                 int temp = array[low];
                 array[low] = array[high];
                 array[high] = temp;
                 low++;
                 high--;
             }
         }

         //Sorting recursively
         if (low < high)
         quickSort(array, low, high);

         if (high > low)
              quickSort(array, low, high);
    }

     public static void printArray(int[] array) 
     {
         for (int input : array)
              System.out.print(input + " ");
      System.out.println();
     }
}

Answer 1

我想添加的第一件事是在快速排序中第一次调用之前的洗牌操作。除此之外，如果您想取前三个元素的中位数，这在您首先对元素进行洗牌的情况下会很好(在其他情况下 - 特别是如果数组已排序，您在快速排序上的性能将不会那么好)。

修改部分代码如下:

public static void sort(int[] array) {
    // Use collections shuffle 
    // (by converting to a List(extra memory) or any other shuffle method)
    shuffle(array);
    quickSort(array, 0, array.length - 1);
}

public static void quickSort(int[] array, int low, int high) {

   if (low >= high)
   return;

   // Selecting the  pivot
   int first = low;
   int second = low < high ? low + 1 : high;
   int third = low + 1 < high ? low + 2 : high;
   // median for first three
   int pivot = Math.max(Math.min(array[first],array[second]), 
                     Math.min(Math.max(array[first],array[second]),array[third]));

   while (low <= high) 
   {
        while (array[low] < pivot)
        {
             low++;
        }

        while (array[high] > pivot) 
        {
             high--;
        }

        if (low <= high)
        {
             int temp = array[low];
             array[low] = array[high];
             array[high] = temp;
             low++;
             high--;
         }
     }

     //Sorting recursively
     if (low < high)
     quickSort(array, low, high);

     if (high > low)
          quickSort(array, low, high);
}