以中间元素为轴的快速排序

Question

我一直在尝试在 Java 中实现快速排序，但我找不到一种方法来实现以枢轴作为中间元素。

数组：

String[] arr = {"D", "C", "B", "A", "A", "Z", "g", "F", "e", "d", "c", "b"};

输出：

A A B C D F g Z b c d e

private static void quickSort(String[] arr, int start, int end) {
    if (end <= start) return;

    int pivot = partition(arr, start, end);
    quickSort(arr, start, pivot - 1);
    quickSort(arr, pivot + 1, end);
}

private static int partition(String[] arr, int start, int end) {
    String pivot = arr[start + (end - start) / 2];
    int i = start;
    int j = end;

    while (i < j)
    {
        if (arr[i].compareTo(pivot) < 0)
            ++i;
        
        else if (arr[j].compareTo(pivot) > 0)
            --j;

        else if (arr[i].equals(pivot))
            ++i;

        else if (arr[j].equals(pivot))
            --j;

        else
        {
            String temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    
    String temp = arr[i];
    arr[i] = pivot;
    arr[start + (end - start) / 2] = temp;

    return i;
}

当我做其他数组，其中小于枢轴的元素不在右侧时，它工作得很好。如：

数组：

String[] arr = {"D", "C", "B", "a", "A", "Z", "g", "f", "e", "d", "c", "b"};

输出：

A B C D Z a b c d e f g

任何解决方案？

Answer 1

问题代码中，

partition()

是Hoare分区方案的变体，但有一些错误（比较应该是< and >而不是<= or >=），而

quickSort()

是Lomuto分区方案的变体。 Hoare 分区方案返回的索引不是主元的索引，因为主元或等于主元的值可以在数组中的任何位置结束，所以

quickSort()

不能使用

pivot-1

和

pivot+1

。

具有索引后递增和后递减的 Hoare 分区方案示例，全部在一个函数中。类似于原来的快速排序，递归用于较小的分区，而代码循环返回用于较大的分区：

    public static void qsort(int[] array, int left, int right) {
        int l = left;
        int r = right;
        int pivot = array[(l+r)/2];
          while (l <= r) {
            while (array[l] < pivot)
                l++;
            while (array[r] > pivot)
                r--;
            if (l <= r) {
                int temp = array[l];
                array[l] = array[r];
                array[r] = temp;
                l++; 
                r--;
            }
        }
        if (left < r)
            qsort(array, left, r);
        if (l < right)
            qsort(array, l, right);
    }

典型的 Hoare 分区方案，带有索引的预增和预减，没有检查更小 | 的代码更大的分区。

    @SuppressWarnings("empty-statement")
    public static void qsort(int[] a, int lo, int hi)
    {
        if(lo >= hi)
            return;
        int  p = a[lo+(hi-lo)/2];
        int  i = lo-1;
        int  j = hi+1;
        int t;
        while(true){
            while(a[++i] < p);
            while(a[--j] > p);
            if(i >= j)
                break;
            t     = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        qsort(a, lo, j);
        qsort(a, j+1, hi);
    }