java - 如何理解或解释 Quicksort 中对分区的第一次调用？

Question

这涵盖了来自 https://stackoverflow.com/help/on-topic 的“软件算法”或者在这种情况下，快速排序算法对一组数字进行排序。

这是我正在使用的快速排序算法代码(来自破解编码面试第5版)

static void quickSort(int[] arr, int left, int right) {
    int index = partition(arr, left, right);
    if(left < index - 1) {
        //sort left half
        quickSort(arr, left, index - 1);
    }
    if(index < right) {
        //sort right half 
        quickSort(arr, index, right);
    }
}
static int partition(int[] arr, int left, int right) {
    int pivot = arr[ (left + right) / 2];
    while(left <= right) {
        while(arr[left] < pivot) {
            left ++;
        }
        while(arr[right] > pivot) {
            right --;
        }
        if(left <= right) {
            swap(arr, left, right);
            left ++;
            right --;
        }
    }
    return left;
}
static void swap(int arr[], int one, int two) {
    int temp = arr[one];
    arr[one] = arr[two];
    arr[two] = temp;
} 

我知道quicksort算法的一个总结就是所有小于pivot的元素都在pivot的左边，所有大于pivot的元素都在pivot的右边。顺便问一下，对于与 pivot 相同的元素应该去哪里有规则吗？

所以我的测试运行是来自 https://www.hackerrank.com/challenges/angry-children 的未排序数组

{10, 100, 300, 200, 1000, 20, 30}

第一次调用分区后，这是我的数组的状态

[10, 100, 30, 20, 1000, 200, 300]

我根据这个算法选择的基准值是 200。但是在第一次调用之后，我不知道如何理解它，因为 200 左边的所有内容都不少于 200(1000)。我知道这个算法有效，因为我得到了最终结果排序数组。

谁能帮我解释第一次调用 partition 的结果？

Answer 1

我认为我的困惑在于快速排序的整个概念。如果其他人正在为此苦苦挣扎，这就是我现在要解释的方式。

int index = partition(arr, left, right);

将根据枢轴对数组进行分区，在本例中为索引。保证左边的所有内容都小于主元，而主元右边的所有内容都大于主元。

现在，如果我们看一下这段代码

if(left < index - 1) {
    quickSort(arr, left, index - 1);
}

基本上是在询问枢轴左侧是否有任何东西？如果有，则将所有内容排序到数据透视表的左侧。请注意，如果 left = index - 1 或枢轴左侧只有一个元素，则此测试将不会通过。无需排序。

和这段代码完全一样的逻辑(应用于pivot的右边)

 if(index < right) {
        //sort right half 
        quickSort(arr, index, right);
    }