Java 快速排序二次运行时行为

Question

我试图在 Java 中实现一个高效的排序算法。为此，我还实现了快速排序，使用了如下代码：

public class Sorting {
    private static Random prng;

    private static Random getPrng() {
        if (prng == null) {
            prng = new Random();
        }
        return prng;
    }

    public static void sort(int[] array) {
        sortInternal(array, 0, array.length - 1);
    }

    public static void sortInternal(int[] array, int start, int end) {
        if (end - start < 50) {
            insertionSortInternal(array, start, end);
        } else {
            quickSortInternal(array, start, end);
        }
    }

    private static void insertionSortInternal(int[] array, int start, int end) {
        for (int i=start; i<end - 1; ++i) {
            for (int ptr=i; ptr>0 && array[ptr - 1] < array[ptr]; ptr--) {
                ArrayUtilities.swap(array, ptr, ptr - 1);
            }
        }
    }

    private static void quickSortInternal(int[] array, int start, int end) {
        int pivotPos = getPrng().nextInt(end - start);
        int pivot = array[start + pivotPos];
        ArrayUtilities.swap(array, start + pivotPos, end - 1);
        int left = start;
        int right = end - 2;
        while (left < right) {
            while (array[left] <= pivot && left < right) {
                ++left;
            }
            if (left == right) break;
            while (array[right] >= pivot && left < right) {
                right--;
            }
            if (left == right) break;
            ArrayUtilities.swap(array, left, right);
        }
        ArrayUtilities.swap(array, left, end - 1);
        sortInternal(array, start, left);
        sortInternal(array, left + 1, end);
    }
}

ArrayUtilities.swap 只是交换数组中的两个给定元素。从这段代码中，我预计 O(n log(n)) 运行时行为。但是，一些不同长度的数组排序给出了以下结果：

10000 个元素：32 毫秒

20000 个元素：128 毫秒

30000 个元素：296 毫秒

每种情况测试运行次100次，然后计算运行次的算术平均值。但很明显，与预期的行为相反，运行时间是 O(n^2)。我的算法有什么问题？

Answer 1

在您的插入排序实现中，您的数组将按降序排序，而在您的快速排序中，数组将按升序排序。所以替换（降序）：

for (int ptr=i; ptr>0 && array[ptr - 1] < array[ptr]; ptr--)

和

for (int ptr=i; ptr>0 && array[ptr - 1] > array[ptr]; ptr--)

您的索引似乎也不正确。尝试替换：

sortInternal(array, 0, array.length - 1);

与：

sortInternal(array, 0, array.length);

并且在插入排序中首先 for 循环你不需要做 end - 1，即使用：

for (int i=start; i<end; ++i)

最后，在快速排序方法的开头添加if (start >= end) return;。

正如@ljeabmreosn 提到的，50 有点太大了，我会选择 5 到 20 之间的值。

希望对您有所帮助！

Answer 2

对于长度小于 50 个元素的数组，带有插入排序的快速排序 "optimized" 似乎是个问题。

想象一下，我有一个大小为 65 的数组，并且枢轴恰好是该数组的中位数。如果我通过您的代码运行数组，您的代码将对枢轴左右两侧的两个 32 长度子数组使用插入排序。这将导致 ~O(2*(n/2)^2 + n) = ~O(n^2) 平均情况。使用快速排序并为第一个主元实现 a pivot picking strategy，时间平均情况将是 ~O((nlog(n)) + n) = ~O(n( log(n) + 1)) = ~O(n*log(n))。不要使用插入排序，因为它仅在数组几乎排序时使用。如果您使用插入排序仅仅是因为对小数组进行排序的实际运行宁时间可能运行比标准快速排序算法（深度递归）快，您始终可以使用非递归快速排序比插入排序快运行秒的算法。

也许把“50”改成“20”然后观察结果。

Java 快速排序二次运行时行为

Java Quicksort quadratic runtime behaviour

java

algorithm

big-o

quicksort