Quicksort 霍尔分区

Question

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p)
        quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
    pivot := A[⌊(hi + lo) / 2⌋]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot
        do
            j := j - 1
        while A[j] > pivot
        if i ≥ j then
            return j
        swap A[i] with A[j]

我试图在 Quicksort/Hoare_partition_scheme 中找到以下问题的明确答案，但我找不到，尽管手动尝试一些示例表明以下很可能是正确的... 我的问题是，是否始终保证

partition returns 所选枢轴的位置
对 return i 或 j 重要吗，或者更确切地说，算法是否停止在 i==j
在 quicksort 中调用 (lo,p-1) and (p,hi) 与 (lo,p) and (p+1,hi)

Answer 1

第一个问题的答案在链接文章中：

In this scheme, the pivot's final location is not necessarily at the index that is returned, as the pivot and elements equal to the pivot can end up anywhere within the partition after a partition step.

一个简单的例子是对数组[2,0,1,3,4]进行分区。

枢轴为 1。
i 将停在 2.
j 将在第 1 处停止。
交换后数组为[1,0,2,3,4].
i 将再次移动到 2。
j会移动到0，返回0的位置

该示例数组也回答了第二个问题。分区后，j为1，i为2。

要回答第三个问题，我想你需要做的就是交换初始数组中的2和3。

Quicksort 霍尔分区

Quicksort Hoare's partition

sorting

algorithm

quicksort