arrays - 给出一个复杂度为 O(N) 的算法来重新排列真/假列表，使所有假元素都在真元素之前

Question

我有一个包含 N 个元素的数组，其中只包含两个不同的键，true 和 false。我正在尝试编写一个 O(N) 算法来重新排列列表，以便所有错误元素都在真实元素之前。该算法的一个特定要求是我只能遍历数组一次(这意味着我不能对数组进行两次遍历；一次是计算真/假的数量，另一次是将值赋给数组)。我也不允许创建外部临时数组。

最初我想使用计数排序，但意识到我不能这样做，因为此分配的要求是我不能创建外部/临时数组。

然后，由于只有两个可能的值，我想遍历一次并对它们进行计数。然后第二次迭代并设置顺序(进行排序)。但是，我也不能这样做，因为我只能进行一次迭代。

所以我自己尝试实现一种算法，该算法将只对数组进行一次迭代并同时进行排序。到目前为止，我的想法如下(这只是一个或多或少写成伪代码的想法)

array = T T T T F F F F
int len = length of array.
counter = 0
For item in array
    counter += 1
    If counter <= len/2
       if T change to F
    else
       if F change to T

就在我完成此操作时，我意识到只有当所有 T 值都在数组的一侧，而所有 F 值都在另一侧时，这才有效。

我的问题是，有人可以告诉我可以使用哪种 O(n) 排序算法对数组中的每个项目进行排序并对其进行排列，以便所有错误元素都在正确元素之前吗？

Answer 1

可以试试快速排序的思路:同时从头尾遍历数组，将顺序不正确的元素调换。 IE。如果您在数组的左半部分找到 true，请将其替换为右半部分的 false。

因为您只有 2 个不同的值，所以单次传递就足够了。

例子:

bool[] array = ...;
int low = 0;
int high = array.Length - 1;
do
{
    while (array[low] == false)
        low++;

    while (array[high] == true)
        high--;

    if (low <= high)
    {
        bool temp = array[low];
        array[low] = array[high];
        array[high] = temp;
    }
}
while (low < high);

这为您提供了单次通过，即 O(N)。