快速排序分区的特殊问题

Question

今天，在尝试快速排序时，我没有将最后一个元素作为主元和分区，而是将第一个元素作为主元，但它没有产生正确的分区输出。

int pivot = ar[0];
int pindex = 0;

for(int  i = 0;i < ar.size();i++)
{
    if(ar[i] <= pivot)
    {
        swap(ar[i],ar[pindex]);
        pindex++;
    }
}
swap(ar[pindex],ar[ar.size()-1]);

我不明白为什么，我总是用它来分区，但是当我把第一个元素作为分区时，它不起作用。

但即使我将第一个元素作为分区，这仍然有效

int i, j, pivot, temp;
pivot = ar[0];
i = 0;
j = ar.size()-1;
while(1)
{
    while(ar[i] < pivot && ar[i] != pivot)
        i++;
    while(ar[j] > pivot && ar[j] != pivot)
        j--;
    if(i < j)
    {
        temp = ar[i];
        ar[i] = ar[j];
        ar[j] = temp;
    }
    else
    {
        break;
    }
}

它们有什么区别

Answer 1

最后发现，这个方法是Hoare的划分法，而我们都遵循的典型的快速排序方法是lomuto的划分法。

查看此 wiki 页面，其中包含所有详细信息https://en.wikipedia.org/wiki/Quicksort

快速排序分区的特殊问题

Peculiar issue with quicksort partition

partitioning

quicksort