我想在一次迭代中对 bool 数组进行排序。我正在尝试从 C++ 执行此操作。我尝试通过初始化一个新数组然后将 False 值附加到数组末尾并将 True 值附加到数组开头来做到这一点。但是我正在为如何在不覆盖 C++ 的情况下附加数据而苦苦挣扎。有没有更好的算法可以做到这一点请赐教。
最佳答案
我会用两个指针扫描整个数组:一个从头开始，另一个从尾开始。当每个指针向数组的中间移动时，检查值是否乱序，如果是，则交换它们。指针何时/何地相交，值是有序的。
请注意，与交换大多数其他类型的值不同，在这种情况下，无需在复制值的地方进行典型的交换。让我们暂时假设您正在排序，所有 true 值排在第一位，所有 false 值排在第二位。在这种情况下，如果您必须乱序取值，它只能是一个 false 出现在一个 true 之前，并且当它们被交换时，它只能是一个true 在 false 之前。而不是典型的交换，你只是在左边寻找一个 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;
假设您希望 true 排在 false 之前。如果你想反转它，你将 if (*b) 更改为 if (! *b) 并将 *out++ = false 更改为 *out++ = true;.
关于c++ - 如何在数组的一次迭代中对 bool 数组进行排序(仅遍历数组一次)？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33591840/