如何在快速排序中选择枢轴值？

Question

我研究了几个小时的快速排序，对选择主元值感到困惑。枢轴值是否需要存在于数组中？

例如，如果数组是 1,2,5,6 ，我们可以使用值 3 或 4 作为基准吗？

我们使用枢轴的位置将数组划分为子数组，但我有点困惑，当我们将值 < 5 移到数组左侧并将值 > 5 移到数组右侧后，枢轴位置是什么？

7,1,5,3,3,5,8,9,2,1

我用枢轴 5 空运行算法并得到以下结果：

1,1,5,3,3,5,8,9,2,7
1,1,5,3,3,5,8,9,2,7
1,1,5,3,3,5,8,2,9,7

我们可以看到值2还是没有放在正确的位置。我究竟做错了什么？对不起，如果这是一个愚蠢的问题。

我想出了以下代码，但它仅在 pivot = left 时有效，我不能使用随机 pivot。

template <class T>
void quickSort(vector <T> & arr, int p, int r, bool piv_flag) {
    if (p < r) {
        int q, piv(p); counter++;

        //piv = ((p + r) / 2); doesn't work

        q = partition(arr, p, r, piv);
        quickSort(arr, p, q - 1, piv_flag); //Sort left half
        quickSort(arr, q + 1, r, piv_flag); //Sort right half
    }

    return;
}

int partition(vector <T> & arr, int left, int right, int piv) {
    int i{ left - 0 }, j{ right + 0 }, pivot{ arr[piv] };

    while (i < j) {
        while (arr[i] <= pivot) { i++; }
        while (arr[j] > pivot) { j--; }
        if (i < j) (swap(arr[i], arr[j]));
        else {
            swap(arr[j], arr[piv]);
            return j;
        }
    } 
}

谢谢。

Answer 1

在许多应用程序中，主元被选择为数组中的某个元素，但它也可以是您可以用来将数组中的数字一分为二的任何值。如果您选择的枢轴值是数组中的特定元素，您需要在将数组分成两部分后将其放在这两个组之间。如果没有，您可以通过正确调用索引来继续递归排序过程。（即记住数组中没有主元，只有两组值）

请参阅 this response 类似问题，了解一些广泛使用的枢轴选择方法的简明解释。

枢轴最重要的功能是充当我们在快速排序的分区阶段尝试创建的组之间的边界。这里的 goal/challenge 是以大小相等或几乎相等的方式创建这些组，以便快速排序可以有效地工作。这一挑战是构想出如此多枢轴选择方法的原因。（也就是说，至少在 大多数 情况下，数字将被分成大小相似的组）

关于问题的第二部分，即分区完成后枢轴的位置将如何变化，请参阅下面的示例分区阶段。

假设我们有一个包含元素 [4,1,5,3,3,5,8,9,2,1] 的数组 A，我们选择枢轴作为第一个元素，即 4。字母 E下面使用的表示小于枢轴的元素的末尾。（即最后一个小于主元的元素）

   E
[4,1,5,3,3,5,8,9,2,1]

     E
[4,1,3,5,3,5,8,9,2,1]

       E
[4,1,3,3,5,5,8,9,2,1]

         E
[4,1,3,3,2,5,8,9,5,1]

           E
[4,1,3,3,2,1,8,9,5,5]

[1,1,3,3,2,4,8,9,5,5] // swap pivot with the rightmost element that is smaller than its value

经过这次分区，元素显然还没有排序。但是 4 左边的所有元素都小于 4，而它右边的所有元素都大于 4。为了对它们进行排序，我们递归地对这些组使用快速排序。

根据您的代码，下面是基于我上述过程的示例分区代码。你也可以观察它的执行 here.

template <class T>
int partition(vector<T>& arr, int left, int right, int piv) {
    int leftmostSmallerThanPivot = left;

    if(piv != left)
        swap(arr[piv], arr[left]);
    for(int i=left+1; i <= right; ++i) {
        if(arr[i] < arr[left])
            swap(arr[++leftmostSmallerThanPivot], arr[i]);
    }
    swap(arr[left], arr[leftmostSmallerThanPivot]);
    return leftmostSmallerThanPivot;
}

template <class T>
void quickSort(vector<T>& arr, int p, int r) {
    if (p < r) {
        int q, piv(p);

        piv = ((p + r) / 2); // works

        q = partition(arr, p, r, piv);
        quickSort(arr, p, q - 1); //Sort left half
        quickSort(arr, q + 1, r); //Sort right half
    }
}

如何在快速排序中选择枢轴值？

How to choose pivot value in QuickSort?

arrays

sorting

quicksort