快速排序参数

Question

我正在尝试将快速排序片段应用于我的程序；但是，none 我发现的大量教程或示例以通俗易懂的方式解释了我对第二个和第三个参数的使用，通常称为左和右；解释不够简单，我看不懂。

下方是逐字摘录；如果有任何问题，我深表歉意。

void quickSort(int arr[], int left, int right) 
{
    int i = left, j = right;
    int tmp;
    int pivot = arr[(left + right) / 2];
      /* partition */
    while (i <= j) 
    {
        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;
        if (i <= j)
        {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    };

      /* recursion */
    if (left < j)
    quickSort(arr, left, j);

    if (i < right)
    quickSort(arr, i, right);
}

我知道第一个参数是要排序的数组，但是我为 "left" 和 "right?"

传递的是什么参考数组

我已经编码了几年，但我没有得到最好的指导，所以如果这对你有帮助，请教育我，因为我仍处于学习阶段。

Answer 1

left 和 right 是要为当前调用的快速排序调用排序的数组的索引。

当您第一次在顶层调用快速排序时，left 和 right 是完整的数组。例如：

int arr[] = { 3,4,6,2,5,6,6,7,4,4,6,5,3,6,7,8,8,6,4,3 };

quicksort(arr, 0, 19);

Answer 2

在我回答之前有一点，

while (i <= j) 
{
    while (arr[i] < pivot)
        i++;
        while (arr[j] > pivot)
            j--;
            if (i <= j) 
            {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
};

您的这部分代码有一个缩进不正确的 while 循环，因此有点混乱。

所以左边和右边指的是你想要的数组的最左边和右边的索引。

假设我们有一个数组 [1, 4, 5, 6, 3] 快速排序的排序部分会将数组排列成 [1, 4, 3, 6, 5]

之后发生的是你将递归调用 quickSort(arr, 0, 2) quickSort(arr, 3, 4) 因此，一个 quickSort 将根据左（索引 0）到右（索引 2）对它们进行排序，另一个将快速排序从左（索引 3）到右（索引 4），直到数组达到长度 < 1

快速排序参数

Quick sort parameters

c++

quicksort