Quicksort - Hoare使用重复值进行分区

Question

我为Quicksort实现了经典的Hoare分区算法.它适用于任何唯一数字列表[3,5,231,43].唯一的问题是当我有一个重复的列表[1,57,1,34].如果我得到重复值,我进入一个无限循环.

private void quicksort(int[]a, int lo, int hi) {
    if (lo < hi) {
        int q = hoare_partition(a, lo, hi);
        quicksort(a, lo, q - 1);
        quicksort(a, q + 1, hi);
    }
}

private int hoare_partition(int[] a, int lo, int hi) {

    int pivot = a[hi];
    int i = lo;
    int j = hi;

    while (true) {

        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;

        if (i < j) swap(a, i, j);
        else return j;
    }
}

Hoare的实现是否可能不正确并且无法应对重复？

我知道这已被多次询问(我尝试了所有这些)但我很难找到这个实现的解决方案.

Answer 1

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo – 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j – 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

上面的伪代码取自维基百科.我们将它与您的代码进行比较.

问题是你必须在交换后移动索引.伪代码使用do-while循环而不是while循环来在交换后移动索引.另外要注意的初始值i和j.

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi)

对于递归步骤,您可能需要处理边缘情况(即索引).如果你改变它应该工作quicksort(a, lo, q-1)到quicksort(a, lo, q).

我写的一个完整的工作版本:

import java.util.Arrays;

public class Test {

    public static void main(String[] args) throws Exception {
        int[] input = {1, 57, 1, 34};
        quicksort(input, 0, input.length - 1);
        System.out.println(Arrays.toString(input));
    }

    private static void quicksort(int[]a, int lo, int hi) {
        if (lo < hi) {
            int q = hoare_partition(a, lo, hi);
            quicksort(a, lo, q);
            quicksort(a, q + 1, hi);
        }
    }

    private static int hoare_partition(int[] a, int lo, int hi) {

        int pivot = a[lo];
        int i = lo - 1;
        int j = hi + 1;

        while (true) {
            do {
                i++;
            }
            while (a[i] < pivot);

            do {
                j--;
            }
            while (a[j] > pivot);

            if (i >= j) {
                return j;
            }
            swap(a, i, j);

        }
    }

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

}

如果您更喜欢while循环而不是do-while:

private static int hoare_partition(int[] a, int lo, int hi) {

            int pivot = a[lo];
            int i = lo;
            int j = hi;

            while (true) {

                while (a[i] < pivot) i++;

                while (a[j] > pivot) j--;

                if (i >= j) {
                    return j;
                }
                swap(a, i, j);
                i++;
                j--;

            }
        }