java - 递归快速排序多个错误

Question

我已经尝试修复这个递归快速排序程序大约三天了，我相信它有错误，因为它对较小尺寸的数组进行排序，但对较大数组进行错误排序。

该代码使用三中位数技术对数组从 a[start] 到 a[end] 进行排序。我认为问题出在分区上。请看一下

    import java.util.*;
public class QuickSort
{
  public static void main(String [] args)
  {
    int [] arr = {6,4,1,14, 13,20,7,10,9,2,17};
    System.out.println(Arrays.toString(arr));
    quickSort(arr, 0,arr.length-1);
    System.out.println(Arrays.toString(arr));
    System.out.println("is the array sorted? " + isSorted(arr));
  }
public static void quickSort(int[] a, int start, int end)
  {
    if(end-start > 0) //base case for zero or one element? 
    {
        int pivotPosn = partition(a,start,end);
        quickSort(a,start, pivotPosn-1);
        quickSort(a,pivotPosn+1, end);
    }

  }
   /***
   * swap - Swaps two values in an array.
   ***/
  private static void swap(int [] a, int index1, int index2)
  {
    int temp = a[index1];
    a[index1] = a[index2];
    a[index2] = temp;
  }
  private static boolean isSorted(int [] a)
  {

    int i = a.length;
    boolean result = true;
    for(int j = 1; j<i; j++)
    {
      if(a[j-1] > a[j])
      {
        result = false;
      }
    }
    return result;
  }
  private static int medianOfThreeIndex(int [] a, int start, int end)
  {
    int mid= start + (end-start)/2; //find the middle of the array

    int vs = a[start];
    int vm = a[mid];
    int ve = a[end];

    if (vs >= vm  && vm >= ve)
    {
      return mid;
    }
    else if (vm >= vs  && vs >= ve)
    {
      return start;
    }
    else
    {
      return end;
    }
  }
  private static int partition(int [] a, int start, int end)
  {
    int boundary,pivot,pivotPosn;
    pivotPosn = medianOfThreeIndex(a,start,end);
    pivot = a[pivotPosn];
    boundary = start;

    swap(a,pivotPosn,end);//moving pivot to the right
    for(int curr = start+1; curr<=end;curr++)
    {
      if(a[curr]<pivot)
      {
        boundary++;
        swap(a,boundary,curr);
      }
    }
    swap(a,end,boundary); //swap pivot value back to its final place
    return boundary;
  }
}

输出为[6,4,1,9,7,13,14,10,17,20,2] 我不知道我做错了什么:(

Answer 1

您有几个错误，主要的一个是我认为您不太了解三位中位数应该做什么以及在哪里使用它。特别是 - 它应该用于选择枢轴，而不是在阵列上进行任何交换。我假设您的交换方法工作正常。

您可以首先忘记三个主元选择的中位数，然后让程序的主要部分正常工作。三个主元选择的中位数只是为了提高性能，而不是选择数组的开头作为主元。因此，让我们首先更改您的代码来执行此操作:

private static int partition(int [] a, int start, int end)
{
    int boundary,pivotPosn, pivot,bigStart;

    pivotPosn = start;
    pivot = a[pivotPosn];
    boundary = start;

    //Got rid of bigStart - it's not needed...
    swap(a,pivotPos,end); //Move your pivot value to the "right" or end of array

    // Note - it is fine to store the pivot at the "left" or start as
    // the OP originally did - in which case the following for
    // loop should run from start+1 to end inclusive and the 
    // boundary++ would come before the swap.

    for(int curr = start; curr<end;curr++)
    {
        if(a[curr]<pivot)
        {

            swap(a,boundary,curr);
            boundary++;
        }
    }
    swap(a,end,boundary); //swap your pivot value back to its final place
    return boundary;
}

然后看看你的快速排序方法。请记住，我们现在忽略了medianOfThree。你遇到了一个你并不真正需要的边缘情况 - 2 成员数组。更简单的是:

public static void quickSort(int[] a, int start, int end)
{
    if(end-start > 0) //base case for zero or one element? already 
    {
        int pivotPosn = partition(a,start,end);
        quickSort(a,start, pivotPosn-1);
        quickSort(a,pivotPosn+1, end);
    }
}

这样就可以了:)

但是 - 您可能想返回medianOfThree。还记得我们把pivotPosn = start放在哪里吗？

将其更改为 pivotPosn =medianOfThree(a,start,end); (或任何您喜欢的内容，只要它在数组内 - 可以尝试)。

medianOfThree 然后需要返回数组开始、中间和结尾的中值的索引。我建议改变你的方法(不是最紧凑的，但易于阅读):

private static int medianOfThreeIndex(int [] a, int start, int end)
{
    int mid= start + (end-start)/2; //find the middle of the array

    int vs = a[start];
    int vm = a[mid];
    int ve = a[end];

    if (vs >= vm  && vm >= ve)
    {
        return mid;
    }
    else if (vm >= vs  && vs >= ve)
    {
        return start;
    }
    else
    {
        return end;
    }

}

这样 - 你就完成了。我四处寻找教程，以防您不清楚算法并发现 the Wikipedia article on this is pretty good.