java - 从概念上理解快速排序

Question

我正在尝试可视化快速排序的工作原理。主要是，我试图了解它的分区部分。我将在下面发布代码:

public int paritionIt(int left, int right, long pivot){
    leftPtr = left - 1;
    rightPtr = right + 1;

    while (true) {
        while (leftPtr < right && Array[++leftPtr] < pivot);
        while (rightPtr > left && Array[--rightPtr] > pivot);
        if (leftPtr <= rightPtr)
            break;
        else
            swap(leftPtr, rightPtr);
    } //end while loop
    return leftPtr;
}

我的最终问题是:为什么我们要返回 leftPtr？我觉得这不对……快速排序算法使用递归，如下所示:

public void recQuicksort(int left, int right){
    if(left - right <= 0)
        return 0;
    else{
        long pivot = array[right];
        int partition = partitionIt(left, right, pivot);
        recQuicksort(left, partition -1);
        recQuicksort(partition + 1, right);
    }
}

我只是很难将其概念化。

Answer 1

这个特定版本的分区的工作是重新排序列表，以便所有不大于主元的元素出现在所有不小于主元的元素之前。 (这意味着等于枢轴的元素可以散布在任何地方。而且它必须返回第二个子列表开始的索引。

很多订单都能满足这个要求。对于一个排序，多个返回值可能是有效的。这不会影响 Quicksort 的正常运行，所以不用担心。

对于您的示例数据 (3,9,4,7)，第一遍将以 left=1，right=3 停止，因此它将交换 7 和 9 以生成 (3,7,4,9)。接下来它会在 left = 3 和 right = 2 时停止，这会导致另一个循环中断。返回值为 3。这是正确的，因为它是初始子数组末尾的一步，现在完全小于或等于主元。

但是对于这个版本的分区，快速排序有一个错误。应该是:

public void recQuicksort(int left, int right) {
  if (left < right) {
    long pivot = array[right];
    int partition = partitionIt(left, right, pivot);
    recQuicksort(left, partition - 1);
    recQuicksort(partition, right);
  }
}