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

Question

这涵盖了 https://whosebug.com/help/on-topic 中的 "a software algorithm"，或者在本例中，是对一组数字进行排序的快速排序算法。

这是我正在使用的快速排序算法代码（来自破解编码面试第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

现在看起来很合理。对于等于枢轴元素的元素，包括枢轴元素本身，此分区可能会很奇怪，它可以将此类元素放入左右子数组中的任何一个，但它仍然允许左子数组中小于或等于枢轴的值以及大于或等于在右子数组中相等，并且 returns 右子数组中第一个元素的索引。它仍然可能不会阻止算法工作，因为它只是在处理子数组时将这些元素移动到中间。

真的没有那么错。如果分区将所有相等的元素移动到子数组之一，当有许多重复元素时，由于重复移动到一侧导致子数组大小不成比例，将导致性能低下。

还有所谓的 3 路分区，它比通常的分区稍微复杂一些，但处理重复的方式更合理。

Answer 2

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

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

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

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

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

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

与此代码段的逻辑完全相同（适用于枢轴右侧）

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

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

How to make sense of or interpret the first call to partition in Quicksort?

java

arrays

algorithm

sorting

quicksort