从快速排序 (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);
}

Answer 2

import java.io.*;
import java.util.*;
public class QuickSort
{
 public static void swap(int[] arr,int a,int b)
 {
    int temp=arr[a];
    arr[a]=arr[b];
    arr[b]=temp;    
 }
 void quicksortfunc(int[] arr,int left,int right)
 {
    // System.out.println("Calling:"+Arrays.toString(arr));
     int size=right-left+1;
     if(size<=3)
         manualsort(arr,left,right);
     else
     {
     int pivot=medianof3(arr,left,right);
     System.out.println("Pivot is:"+pivot);
  //System.out.println(Arrays.toString(arr));
     int p_index=partitionfunc(arr,left,right,pivot);
     System.out.println("The p_index is:"+p_index);
     quicksortfunc(arr,left,p_index-1);
     quicksortfunc(arr,p_index+1,right);
     }
 }
 public static int medianof3(int[] arr,int left,int right)
 {
  int mid=(left+right)/2;
  if(arr[mid]<arr[left])
   swap(arr,mid,left);
  if(arr[right]<arr[left])
  swap(arr,right,left);
  if(arr[mid]>arr[right])
  swap(arr,mid,right);
  swap(arr,mid,right-1);
  return arr[right-1];
 }
 int partitionfunc(int[] arr, int left,int right,int pivot)
 {
     int i=left+1;
     int j=right-2;
     while(i<j)
     {
     while(arr[i]<pivot)
         i++;
     while(arr[j]>pivot)
         j--;
     if(i<j)
         swap(arr,i,j);
     }
     swap(arr,i,right-1);
             return i;
 }
 public static void manualsort(int[] arr,int left,int right)
 {
     int size=right-left+1;
     if(size<=1)
         return;
     if(size==2)
     {
         if(arr[right]<arr[left])
             swap(arr,left,right);
             return;
     }
     else
     {
     if(arr[right-1]<arr[left])
         swap(arr,right-1,left);
     if(arr[right]<arr[left])
         swap(arr,right,left);
     if(arr[right-1]>arr[right])
         swap(arr,right-1,right);
     }
 }
 public static void main(String[] args)
 {
  int[] arr={1,3,5,7,9,11,2,2,4,6,8,10,12,12};
  QuickSort obj=new QuickSort();
  obj.quicksortfunc(arr,0,13);
  System.out.println("The sorted array is:"+Arrays.toString(arr));
 }
}