algorithm - 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]

上面的伪代码取自Wikipedia .让我们将它与您的代码进行比较。

问题是您必须在交换后移动索引。伪代码使用 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--;

            }
        }