c - 快速排序分区

Question

我正在尝试理解和实现快速排序: 所以我一直在读这个:

http://www.geeksforgeeks.org/iterative-quick-sort/

我不明白分区代码。

/* A typical recursive implementation of quick sort */

/* This function takes last element as pivot, places the pivot element at its
   correct position in sorted array, and places all smaller (smaller than pivot)
   to left of pivot and all greater elements to right of pivot */
int partition (int arr[], int l, int h)
{
    int x = arr[h];
    int i = (l - 1);

    for (int j = l; j <= h- 1; j++)
    {
        if (arr[j] <= x)
        {
            i++;
            swap (&arr[i], &arr[j]);
        }
    }
    swap (&arr[i + 1], &arr[h]);
    return (i + 1);
}

/* A[] --> Array to be sorted, l  --> Starting index, h  --> Ending index */
void quickSort(int A[], int l, int h)
{
    if (l < h)
    {        
        int p = partition(A, l, h); /* Partitioning index */
        quickSort(A, l, p - 1);  
        quickSort(A, p + 1, h);
    }
}

所以可以说我有这个数组，[3,8,7] 所以它以最后一个元素作为枢轴。即 7。

配分函数的第一步是(对于 l=0 和 h=2):

x = 7
i = -1

然后在循环中，arr[j] <= x将会是真的。因为 3 <= 7。 所以会增加i乘以 1，然后将 3 与 3 交换？这没有意义。这只会返回相同的数组

Answer 1

让我们看看会发生什么:

x = 7
j = 0:

  3 <= 7: swap(arr[0], arr[0]) => nothing happens

j = 1:

  8 <= 7 is false => nothing happens

现在，请注意 i == 0，我们有以下行:

swap (&arr[i + 1], &arr[h]);

这意味着我们将 arr[1] 与 arr[2] 交换，您的数组将是 3 7 8。您在分析中没有考虑到这一行。

这是正确的，并且返回的枢轴位置 i + 1 == 1 也是正确的。

您可以在每行之后添加打印语句，或者使用调试器逐步执行以更好地了解正在发生的情况。在纸上执行此操作可能会导致此类错误，您会意外地跳过步骤，尤其是在学习某些内容时(说实话，我花了几分钟才意识到您错过了那条线)。