了解以下快速排序实现

Question

我有以下两种方法：

public static void QuickAlgo(int[] a, int left, int right) {

        int index = partition(a, left, right);

        if (left < index - 1) {
            QuickAlgo(a, left, index - 1);
        }
        if (index < right) {
            QuickAlgo(a, index, right);
        }

    }

    static int partition(int[] a, int left, int right) {

        int pivot = a[(left + right) / 2];

        while (left <= right) {

            while (a[left] < pivot) {
                left++;
            }
            while (a[right] > pivot) {
                right--;
            }

            if (left <= right) {

                int temp = a[left];
                a[left] = a[right];
                a[right] = temp;
                left++;
                right--;

            }

        }

        return left;
    }

假设我有以下针对上述问题的未排序数据：

_______________________________________
65  | 72 | 23 | 36 | 99 | 20 | 1 | 44 |

比方说，我这里的支点是36。

调用partition方法时，我理解是在以下循环中检查数组索引值 while(left <= right)

现在，对于以下代码片段：

if (left <= right) {

                int temp = a[left];
                a[left] = a[right];
                a[right] = temp;
                left++;
                right--;

            }

不应该是这样吗:

1) a[left] 应首先与 pivot 进行比较，如我的示例 65 > 36，因此有资格交换。同样，pivot 必须与 a[right] 进行比较，在我的示例中，它是 44，并且由于 pivot(36) < 44，指针递减并移动到 1，因此 1 有资格进行交换，因为 pivot(36) > 1。

而我提到的上面的代码片段是直接比较索引值和交换数字。

可能是我没看懂。谁能解释一下？

谢谢

Answer 1

我们这样做是为了确保枢轴左侧的所有元素都小于枢轴，而枢轴右侧的所有元素都大于枢轴。现在，如果您看到 </code>if (a[left] < pivot )<code> 之前的两个 while 循环，它们用于遍历直到元素较少的点than pivot from beginning 和 other 用于获取大于 pivot from end 的元素。现在考虑：3 4 19 7 21 2 作为我们的数组，7 是枢轴。这里我们将有 left = 2 和 right = 5 ...所以我们交换这两个元素。并在左侧进行分区，因为我们确定左侧的所有元素都小于左侧。

Answer 2

当你到达交换点时，与你提到的枢轴的比较已经完成。第一个 while 循环在找到大于主元的值时结束，第二个循环在找到小于主元的值时结束。这意味着左右指针都找到了错误一侧的值，因此，这两个值都可以交换。

if (left <= right) 只是为了确保在左光标通过右光标后不会交换值。当左游标超过右游标时，表示分区完成，因此不应再进行交换。

了解以下快速排序实现

Understanding the following Quicksort Implementation

java

quicksort