快速排序分区

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？这没有意义。那将只是 return 相同的数组

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也是正确的。

您可以在感兴趣的每一行之后添加打印语句，或者使用调试器逐步执行以更好地了解正在发生的事情。在纸上这样做可能会导致这样的错误，您会不小心跳过步骤，尤其是在学习某些东西时（老实说，我花了几分钟才意识到您错过了那一行）。

快速排序分区

Quicksort Partition

c

algorithm

quicksort