查找快速排序算法的所有枢轴值

Question

我似乎对快速排序的正确实现有点困惑。

If I wanted to find all of the pivot values of QuickSort, at what point do I stop dividing the subarrays?

QuickSort(A,p,r):
    if p < r:
        q = Partition(A,p,r)
        Quicksort(A,p,q-1)
        Quicksort(A,q+1,r)

Partition(A,p,r):
    x = A[r]
    i = p-1
    for j = p to r-1:
    if A[j] ≤ x:
        i = i + 1
        swap(A[i], A[j])
    swap(A[i+1], A[r])
    return i+1

意思是，如果我有一个数组： A = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6]

随着快速排序将其分解成其组成部分...

A = [2, 5, 3] [12, 7, 14, 9, 10, 11]

再一步就到了迷茫的地步...

A = [2, 5] [7, 12, 14, 9, 10, 11]

左边的子数组到这里了吗？还是它 (quickSort) 最终调用 quickSort 并将 5 作为最终的主元值？

我认为我们继续直到所有子数组都是单个项目是有意义的——但我的一位同事告诉我不是这样。

Answer 1

您的示例的支点为：6, 3, 11, 10, 9, 12。关于

Does the subArray on the left stop here?

最好检查源代码。当您的递归子数组变为 [2, 5, 3] 时，将使用 p = 0 和 r = 2 调用函数 QuickSort。让我们继续：Partition(A,0,2) 将 return q = 1，因此接下来的两个调用将是 Quicksort(A,0,0) 和 Quicksort(A,2,2)。因此，Quicksort(A,0,1) 将永远不会被调用，因此您将永远没有机会检查子数组 [2, 5] - 它已经排序！

查找快速排序算法的所有枢轴值

Find all pivot values of quickSort algorithm

algorithm

partitioning

quicksort