快速排序 - Middle Pivot实现奇怪的行为

Question

我正在尝试使用透视值实现快速排序作为向量的中间元素，使用在线提供的各种教程。即使它适用于某些样本，也有一个我无法获得分类矢量的样本。

示例 - 输入{5,3,8,6,1,0,4}但输出为{0,3,4,5,1,6,8}

QuickSort实施

void quickSortMiddle(vector<int> &a, int left, int right)
{
    if(left >=right) return;

    int leftI = left;
    int rightI = right;

    int pivot = left + (right - left)/2;

    while(leftI<=rightI)
    {
        while(a[leftI] < a[pivot] )leftI++;
        while(a[rightI] > a[pivot])rightI--;

        if(leftI <=rightI)
        {
            swap(a[leftI], a[rightI]);
            leftI++;
            rightI--;
        }
    }

    if(left <= rightI)quickSortMiddle(a,left,rightI);
    if(leftI <= right)quickSortMiddle(a,leftI,right);
}

以下是我在每次实施后得到的输出

5340168

0345168

0345168

0345168

final : 
0345168

Answer 1

问题是使用[pivot]而不是设置pivot = a [left +（right - left）/ 2]。您使用此修复程序的版本：

void quickSortMiddle(vector<int> &a, int left, int right)
{
    if(left >=right) return;
    int leftI = left;
    int rightI = right;
    int pivot = a[left + (right - left)/2]; // set pivot to value
    while(leftI<=rightI)
    {
        while(a[leftI]  < pivot )leftI++;   // use pivot by value
        while(a[rightI] > pivot )rightI--;  // use pivot by value
        if(leftI <=rightI)
        {
            swap(a[leftI], a[rightI]);
            leftI++;
            rightI--;
        }
    }
    if(left < rightI)quickSortMiddle(a,left,rightI); // < not <=
    if(leftI < right)quickSortMiddle(a,leftI,right); // < not <=
}

标准Hoare分区方案，虽然你的版本适用于pivot fix：

void quickSortMiddle(vector<int> &a, int left, int right)
{
    if(left >= right) return;
    int pivot = a[left + (right - left)/2];
    int leftI = left-1;
    int rightI = right+1;
    while(1)
    {
        while(a[++leftI] < pivot);
        while(a[--rightI] > pivot);
        if(leftI >= rightI)break;
        swap(a[leftI], a[rightI]);
    }
    quickSortMiddle(a,left,rightI);
    quickSortMiddle(a,rightI+1,right);
}