带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]
}

Answer 2

我认为现有的答案提供了一个次优的解决方案。您可以简单地修改Hoare的算法以返回枢轴的索引，re：

，因为Hoare分区不一定返回枢轴的索引。

为此，您选择数组的第一个元素作为枢轴，然后基本上忽略它，按照通常的方式对剩余的子数组arr[1:]进行分区。然后，在最后，用通常返回的索引元素交换arr[0]。

这是因为(vanilla) Hoare的算法返回索引idx，因此：

arr[j] <= arr[idx]

• for

• for all j in [lo, idx]， all j in [idx, hi]，arr[idx] <= arr[j]

使用arr[j]上的元素交换枢轴可以保持此不变。

下面是一个用稳健性编写的示例实现(因为我过去必须在智能契约中实现这样的东西)：

function partition
(
  uint256[] memory arr,
  uint256 lo,
  uint256 hi
)
  public
  pure
  returns (uint256)
{
  uint pivot = arr[lo];
  uint i = lo;
  uint j = hi + 1;

  while (true) {
    do {
      i++;
    } while (i < arr.length && arr[i] < pivot);
    do {
      j--;
    } while (arr[j] > pivot);
    if (i >= j) {
      // swap with pivot
      (arr[lo], arr[j]) = (arr[j], arr[lo]);
      return j;
    }
    (arr[i], arr[j]) = (arr[j], arr[i]);
  }
}