Recursive QuickSort 多个错误

Question

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

代码使用三中值技术对 a[start] to 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

我觉得你的代码很奇怪。看看 http://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html 那里的代码对我来说似乎更清楚。

Answer 2

你有几个错误，主要的错误是我认为你还没有完全理解三位中位数应该做什么以及在哪里使用它。特别是 - 它应该用于 select 枢轴，而不是对数组进行任何交换。我假设您的交换方法工作正常。

你可以先忘掉三个枢轴的中位数 selection 并让你的程序运行的主要部分。三个枢轴的中位数 selection 只是为了提高性能，而不是选择数组的开头作为枢轴。因此，让我们首先更改您的代码：

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 然后需要return 数组开始、中间和结束的中值的索引。我建议这样改变你的方法（不是最紧凑的，但易于阅读）：

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.

Recursive QuickSort 多个错误

Recursive QuickSort multiple bugs

java

recursion

quicksort