java - 快速排序分区

Question

我有以下数组:

int[] arr = { 19, 4, 2, 3, 9, 2, 10, 2, 7, 12, 5, 16, 8, 3, 11, 14, 0, 5 };

现在我使用快速排序的分区来使用主元元素 7 对数组进行分区:

    public static void partition(int[] arr, int low, int high) {
    int pivot = arr[low + (high - low) / 2];
    int i = low;
    int j = high;
    while (i <= j) {
        // If the current value from the left list is smaller then the pivot
        // element then get the next element from the left list
        while (arr[i] < pivot) {
            i++;
        }
        // If the current value from the right list is larger then the pivot
        // element then get the next element from the right list
        while (arr[j] > pivot) {
            j--;
        }

        // If we have found a values in the left list which is larger then
        // the pivot element and if we have found a value in the right list
        // which is smaller then the pivot element then we exchange the
        // values.
        // As we are done we can increase i and j
        if (i <= j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
}

我对结果感到困惑:

5 4 2 3 0 2 3 2 5 12 7 16 8 10 11 14 9 19 

我认为每个元素<=pivot(7)都必须在左边，每个元素>比pivot元素必须在右边。但为什么 12 还剩 7 呢？

Answer 1

此实现不能保证您所期望的效果。它所做的只是以下内容(前提是您按照 Achintya Jha 的建议更改为 arr[i] <= pivot ，否则它甚至无法保证):

对于每对值a, b与 a <= pivot < b ，保证a将剩下 b到底。但是，您不能保证 pivot 的确切位置任何。在最终数组中(只是它是所有较大值的左侧)。