排序布尔值，O(N)时间，O(1)空间

Question

对于家庭作业，我被要求使用一种使用O（1）空间和O（N）时间复杂性的方法对布尔数组进行排序。可以提供一些提示吗？我在想一些关于快速排序算法的枢轴方法的东西。-谢谢！

Answer 1

1. 在前面和后面留一个索引
2. 检查当前前端索引，如果为false，则增加前端索引
3. 如果是真的，则与后索引交换并递减后索引
4. 继续执行步骤2和3，直到前后索引相等为止

Answer 2

如果您有一个布尔值数组，您可以简单地计算true（或false）值。让我们假设这个结果为k。然后将数组的第一个k元素设置为true，其余false。

该算法在数组中迭代两次（因此其时间复杂度为O（N）），并且只使用一个计数器，因此所需空间为O（1）。

Answer 3

由于布尔只有两个可能的值，您只需计算"true"s和"false"s，然后修改原始数组，以便首先在其中放置适当数量的false值，然后用true填充其余值。根据需要，这在时间上是O(n)，在空间上是O(1)。C代码如下：

void sortbool(int *b, size_t n)
{
    size_t k = 0;
    for (size_t i = 0; i < n; i++) {
            if (!b[i])
                    k++;
    }
    for (size_t i = 0; i < n; i++) {
            b[i] = !(i < k);
    }
}