java - 首先递归快速排序的小边

Question

我正在尝试调试此代码 I found用于进行快速排序，首先对较小的分区进行排序。

public static void quicksortSmallSide(int[] a, int p, int r)
{
    int q = p;
    while(p<r)
    {
        q = partition(a,p,r);
        if(q < (p + (r-p)/2))
        {
            quicksortSmallSide(a,p,q);
            p = q+1;
        }
        else
        {
            quicksortSmallSide(a,q+1,r);
            r = q-1;
        }
    }
} 

输入 [20, 19, 20] 曾经给出错误的输出 [20, 19, 20]，我意识到了。我想我通过将其更改为以下代码来修复它，但我认为它还没有消除错误

public static void quicksortSmallSide(int[] a, int p, int r)
{
    if(r-p< 1)
        return;
    int q = p;
    while(p<r)
    {
        q = partition(a,p,r);
        if(q < (p + (r-p)/2))
        {
            quicksortSmallSide(a,p,q);
            p = q+1;
        }
        else
        {
            quicksortSmallSide(a,q+1,r);
            r = q-1;
        }
        System.out.println();
    }
                    quicksortSmallSide(a,p,q);
} 

例如
{70, 24, -74, 9, 58, -61, -86, 7, -78, 11, -73, 13, -93}
排序为
[-93、-86、-74、-73、7、-61、9、11、-78、24、58、13、70]

Answer 1

您的代码看起来不正确，所以也许我的分区方法与您的稍有不同，但此代码按我的预期工作。此代码没有考虑到分区值的实例可能不止一个。

private static void quickSort(int[] arr, int lo, int hi){
  if(lo >= hi) return;

  int p = partition(arr, lo, hi);

  // modified to choose small partition first

  if((p - lo )<=(hi-p)){
    System.out.println(String.format("Sorting left first %d %d %d",lo,p,hi)) ;
    quickSort(arr, lo, p);
    quickSort(arr, p+1, hi);
  }else {
    System.out.println(String.format("Sorting right first %d %d %d",lo,p,hi)) ;
    quickSort(arr, p+1, hi);
    quickSort(arr, lo, p);
  }
}