c - 2色抖动

Question

我有一个包含 0 和 1 的混合数组。我想重新排列数组的内容，使数组中尽可能多的偶数位置包含 0 和奇数位置包含 1 尽可能多的约束条件是0 和 1 不变。这意味着如果 0 的数量超过 1 的数量，反之亦然，那么在重新排列的数组的末尾将有一个 block ，该 block 由所有 - 0 或全 1。我如何一次性完成此操作，就地修改数组？

例如:

Input:  {0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1}
Output: {0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1}

Answer 1

您可以为此使用标准的双色排序算法；只需编辑数组引用以将对数组前半部分的访问映射到实际数组中的偶数元素，并将对数组后半部分的访问映射到实际数组中的奇数元素(向后)。基本上，a[i] 变成(假设 size 是偶数):

a[i < size/2 ? i * 2 : (size - i) * 2 - 1]