如何理解或解释QuickSort中对partition的第一次调用？

Question

这包括https://stackoverflow.com/help/on-topic中的“软件算法”，或者在本例中是对一组数字进行排序的quicksort算法。

这里是我正在使用的quicksort算法代码（摘自破解编码面试第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相同的元素应该去哪里有规则吗？

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

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

有人能帮我解释第一次调用Partition的结果吗？

Answer 1

我想我的困惑是QuickSort的整个想法。如果还有人在为这件事而苦苦挣扎，我现在会这样解释。

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

 · · 和nbs将对数组进行关于枢轴的分区，在本例中，枢轴是索引。它保证左的一切都小于枢轴，而枢轴右的一切都大于枢轴。

现在我们看看这段代码

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

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