quicksort函数在quicksort算法中是如何工作的？

Question

我已经理解了quicksort算法中的分区部分是如何完成的，但是我在理解quicksort递归函数时遇到了麻烦。谁能一步一步地给我解释一下它是怎么工作的吗？这里粘贴的是C++代码。

using namespace std;

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int myArray[], int low, int high) {
    int i = (low - 1);
    int pivot = myArray[high];

    for (int j = low; j <= high - 1; j++) {
        if (myArray[j] < pivot) {
            i++;
            swap(&myArray[i], &myArray[j]);
        }
    }
    swap(&myArray[i + 1], &myArray[high]);
    return (i + 1);
}

void quickSort(int myArray[], int low, int high) {

    if (low < high) {
        int pi = partition(myArray, low, high);

        quickSort(myArray, low, pi - 1);
        quickSort(myArray, pi + 1, high);
    }
}

void cinArray(int myArray[], int n) {
    for (int p = 0; p < n; p++) {
        cin >> myArray[p];
    }
}

void print(int myArray[], int n) {
    for (int z = 0; z < n; z++) {
        cout << myArray[z] << "\t";
    }
}

int main() {
    int myArray[10];
    int size = sizeof(myArray) / sizeof(myArray[0]);
    cout << "Write 10 numbers: ";
    cinArray(myArray, size);
    quickSort(myArray, 0, size - 1);
    print(myArray, size);
    return 0;
}

我的逻辑到目前为止（一步一步）是这样的：

1. if（低 将始终为true。第一次，低（0）和高（9）值取自int main。
2. pi将等于分区函数的返回值(I+1)，我认为为了返回该值，函数必须首先运行。
3. 我们调用quicksort函数，两次为该函数提供新参数。一次用于原始分区之前的值，一次用于原始分区i+1之后的值。我想重点讨论第一个问题，即值在I+1之前的问题。
4. 函数再次启动，if语句为true（始终为），pi调用函数分区并返回i+1，pi等于i+1。如果此时值仍未排序呢？我假设quicksort函数再次重新启动（感觉像是一个循环）。但既然IF语句将始终为真，那么这种循环情况何时才会停止呢？
5. 同样，假设我在第4点的逻辑是正确的，那么代码第一次是如何运行的？它是否从第一个quicksort(myArray,low,pi-1)；函数调用开始，循环直到某个东西停止它，然后对第二个调用quicksort(myArray,pi+1,high）；执行相同的操作？还是在i+1之前进行分区，然后在i+1之后重新启动函数？

我知道这是一个基本的问题，但我真的很难把我的头围绕在这个算法上。




Answer 1

if（低<高）始终为true。

不正确。这在第一次调用时是正确的，但是QuickSort调用自己是递归的，在low和high之间的间隔逐渐变小。这个if是算法最终终止的原因--您将在下面询问这个问题。

pi将等于分区函数的返回值(i+1)

对啊。pi是数据透视索引的缩写，即所选数据透视在分区后结束的位置。

如果此时值仍未排序，该怎么办？

分区后，您知道左侧分区中没有值大于透视值，右侧分区中没有值小于透视值。这就是你所知道的全部，算法为了最终成功需要知道的全部。每个分区都被递归分区，直到其中只有一个元素。

此循环情况何时停止？

看我的第一点。