是否有一种有效的就地算法，可以根据给定条件将数组分为左右两边？

Question

[将一个阵列分成一对阵列，一侧通过而另一侧失败是很常见的。基本算法如下所示：

function partition(list, cond) {
    let left = [];
    let right = [];

    for (let item of list) {
        if (cond(item)) {
            left.push(item);
        } else {
            right.push(item);
        }
    }

    return [left, right];
}

在我的情况下，该条件更特殊-它只是一个等长的位集，其中每个位置的set = left，unset = right：

function partition(list, bitset) {
    let left = [];
    let right = [];

    for (let i = 0; i < list.length; i++) {
        if ((bitset[i >>> 5] & 1 << (i & 31)) !== 0) {
            left.push(list[i]);
        } else {
            right.push(list[i]);
        }
    }

    return [left, right];
}

事情是，我想就地执行此操作，只是使那些位集中的对应位在同一数组的左侧为true，而在位数组的右侧为false。 （条目确实需要保留其顺序-这很重要。否则，这很明显。）这是我到目前为止提出的最有效的版本：

// The return value is the start offset for the rejects
function partition(list, cond) {
    let right = [];
    let rightStart = 0;

    for (let i = 0; i < list.length; i++) {
        if ((bitset[i >>> 5] & 1 << (i & 31)) !== 0) {
            list[rightStart++] = list[i];
        } else {
            right.push(list[i]);
        }
    }

    for (let i = 0, j = rightStart; i < list.length; i++) {
        list[j] = right[i];
    }

    return right_start;
}

是否有可能仅使用O（1）空间，同时仍保持O（n）时间，如果这样，该算法将是什么样？

Answer 1

您正在寻找的算法称为稳定分区。在恒定空间中，其时间复杂度为O(n log n)。参见例如here（它使用C ++，但是在此情况下没有关系）。

一个实现可能看起来像

stable_partition(begin, end, predicate)
    if (end - begin == 0)
        return begin
    if (end - begin == 1)
        return predicate(*begin)? begin: end

    mid = begin + (end - begin)/2
    left_partition_point = stable_partition(begin, mid, predicate)
    right_partition_point = stable_partition(mid, end, predicate)
    return rotate(left_partition_point, mid, right_partition_point)

rotate返回最左元素着陆的位置。