快速排序 - 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);
}

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

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 分区方案，尽管您的版本在枢轴修复下运行良好：

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);
}

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

Quick Sort - Middle Pivot implementation strange behaviour

c++

sorting

algorithm

quicksort