如何在数组的一次迭代中对布尔数组进行排序（遍历数组只遍历一次）？

Question

我想在一次迭代中对布尔数组进行排序。我正在尝试从C++做到这一点。我尝试通过初始化一个新数组，然后将False值附加到数组的结尾并将真值添加到数组的起始位置来实现此目的。但我正在努力如何追加数据而不用C++覆盖。有没有更好的算法来做到这一点，请赐教。

Answer 1

我会用两个指针扫描数组：一个从头开始，另一个从结束。当每个指针走向数组的中间时，检查这些值是否无序，如果是，交换它们。指针相遇的时间/地点的值是按顺序排列的。

请注意，与交换大多数其他类型的值不同，在这种情况下，不需要在复制值时进行典型交换。让我们暂时假设你正在排序，所以所有的true值都是第一位的，而所有的false值都是第二位。在这种情况下，如果您必须按顺序排列值，则它只能是之前出现的true，当它们交换时，它只能是在false之前出现的true。您只需在左侧寻找false，而在右侧寻找true，而您找到它们时，则需要在左侧分配true，在右侧分配false。

如果你想在一个单独的数组输出，你可以采取一个更简单的方法：从头到尾遍历输入数组。对于每个true，您会发现，将输出数组中的下一个值设置为true并前进到下一个位置。当你到达输入数组的结尾，在输出值的其余部分设置为false：

// ... 
for (bool *b = input; b != input_end; ++b) 
    if (*b) 
     *out++ = true; 
while (out != output_end) 
    *out++ = false; 

这是假设你想truefalse之前排序。如果您想反转，请将if (*b)改为和*out++ = false改为*out++ = true;。

Answer 2

如果您在就地排序布尔值数组，您需要做的就是遍历数组，并使用数组末尾的值替换您看到的任何错误值（使用递减计数器）（或换掉真正的价值，如果在你的定义true后出现错误）。

void function sort(const bool *array, int n) { 
    int i = 0, j = n - 1; 
    while(i <= j) { 
    if(array[i] == false) { 
     bool temp = array[i]; 
     array[i] = array[j]; 
     array[j] = temp; 
     --j; 
    } else { 
     ++i; 
    } 
    } 
} 

Answer 3

或算了算trues与trues覆盖阵列*计数和falses * - 根据您的排序顺序

Answer 4

计数真/假值的数量总是这样的伎俩上（尺寸数）。像这样的东西。

int main() 
{ 
int a[]={1,0,1,1,0,1,1,0,1,0,0,1,0}; 
int size=sizeof(a)/4,count1=0,i; 

for(i=0;i<size;i++) 
    if(a[i]==1) 
     count1++; 

for(i=0;i<size;i++) 
{ 
    if(i<count1) 
     a[i]=1; 
    else 
     a[i]=0; 

    printf("%d ",a[i]); 
} 
return 0; 
}