双轴QuickSort

Question

我正在尝试使用双轴quickSort算法来使文本文件中的数字列表按降序排序。我目前将它设置为升序，但不知道如何切换。下面是让它按升序排序的代码。我认为这只是一个标志，但我不确定在哪里。

private void quickSort(int[] A, int left, int right){
    int temp;
    if(right-left>=1){
        int lp = A[left];
        int rp = A[right];
        if(lp>rp){
            temp = lp;
            lp = rp;
            rp = temp;

            temp = A[left];
            A[left] = A[right];
            A[right] = temp;
        }
        int l = left+1;
        int g = right-1;
        int k = l;
        while(k<=g){
            if(A[k]<lp){
               temp = A[k];
               A[k] = A[l];
               A[l] = temp;
                l++;
            }
            else{
                if(A[k]>rp){
                    while(A[g]>lp && k<g)
                        g--;
                    temp = A[k];
                    A[k]= A[g];
                    A[g] = temp;
                    g--;
                    if(A[k]<lp){
                        temp = A[k];
                        A[k] = A[l];
                        A[l] = temp;
                        l++;
                    }

                }
            }
            k++;
        }
        l--;
        g++;
        temp = A[left];
        A[left] = A[l];
        A[l] = temp;

        temp = A[right];
        A[right] = A[g];
        A[g] = temp;
        quickSort(A,left,l-1);
        quickSort(A,l+1,g-1);
        quickSort(A,g+1,right);
    }

}

Answer 1

我试图调整您的代码，使其降序排序，但不能成功。然而，我写了一个DualPivot QuickSort，你可以很容易地改变顺序。下面是代码。它是降序的，要更改顺序只需遵循代码中的注释。这段代码非常简单和有条理。

public class DualPivotQS
{

   private static void sort(int[] a, int lo, int hi)
   {
      if (hi <= lo)
         return;
      int lt = lo, gt = hi;
      int v = a[lo];
      int i = lo + 1;
      while (i <= gt)
      {

         if (v > a[i])          //   change here to change order
            swap(a, lt++, i++);
         else if (v < a[i])     //   change here to change order
            swap(a, i, gt--);
         else
            i++;
      }

      // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
      sort(a, lo, lt - 1);
      sort(a, gt + 1, hi);

   }

   private static void swap(int[] a, int i, int j)
   {
      int tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
   }

   public static void main(String[] args)
   {
      int[] num = { 5, 5, 0, 1, 7, 2, 99, 23, 56, 44, 32, 104, 4, 7, 8, 2, 7 };

      sort(num, 0, num.length - 1);

      for (int i = 0; i < num.length; i++)
         System.out.print(num[i] + ", ");

   }
}

参考：https://algs4.cs.princeton.edu/23quicksort/