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

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) space 时间来完成此操作，同时仍保持 O(n) 时间，如果是这样，该算法将是什么长什么样子？

Answer 1

您正在寻找的算法称为稳定分区。在常量 space 中，它具有 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 returns 最左边的元素所在的位置。

Answer 2

论文...

Katajainen, J., Pasanen, T. 稳定最小 space 线性时间分区。 BIT 32, 580–585 (1992).
https://doi.org/10.1007/BF01994842

... 提出了一种在 O(n) 时间和 O(1) 额外时间内实现稳定就地分区的算法 space.

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

Is there an efficient in-place algorithm to separate an array into left and right by a given condition?

javascript

sorting

algorithm

bit-manipulation

data-structures