algorithm - 带有 Hoare 分区方案的 QuickSelect

Question

是否可以使用 Hoare 分区实现 QuickSelect 算法？

至少乍一看似乎无法完成，因为 Hoare 分区不一定返回主元的索引。

我错过了什么吗？

Answer 1

使用 Hoare 分区方案，由于主元或等于主元的元素可以在分区步骤后的任何位置结束，因此当分区大小减小为单个元素时，会出现基本(终止)情况。示例代码。 QuickSelectr 是实际功能。 QuickSelect 验证参数。

int QuickSelectr(int a[], int lo, int hi, int k )
{
    if (lo == hi)                           // recurse until lo == hi
        return a[lo];
    int p = a[(lo+hi)/2];                   // Hoare partition
    int i = lo - 1;
    int j = hi + 1;
    while (1){
        while (a[++i] < p);
        while (a[--j] > p);
        if (i >= j)
            break;
        std::swap(a[i], a[j]);
    }
    if(k <= j)
        return QuickSelectr(a, lo, j-0, k); // include a[j]
    else
        return QuickSelectr(a, j+1, hi, k); // exclude a[j]
}

// parameter check
int QuickSelect(int *a, int lo, int hi, int k)
{
    if(a == (int *)0 || k < lo || k > hi || lo > hi)
        return 0;
    return QuickSelectr(a, lo, hi, k);
}

---

使用 i 而不是 j 进行拆分:

int QuickSelectr(int a[], int lo, int hi, int k )
{
    if (lo == hi)                           // recurse until lo == hi
        return a[lo];
    int p = a[(lo+hi+1)/2]; // Carefully note the +1 compared
                            // to the variant where we use j
    int i = lo - 1;
    int j = hi + 1;
    while (1){
        while (a[++i] < p);
        while (a[--j] > p);
        if (i >= j)
            break;
        std::swap(a[i], a[j]);
    }
    if(k < i)
        return QuickSelectr(a, lo, i-1, k); // exclude a[i]
    else
        return QuickSelectr(a, i+0, hi, k); // include a[i]
}