java - 双枢轴快速排序

Question

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

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/