您可以为此使用标准的双色排序算法；只需编辑数组引用以将对数组前半部分的访问映射到实际数组中的偶数元素，并将对数组后半部分的访问映射到实际数组中的奇数元素（向后）。基本上，a[i]变成（假设size是偶数）：
a[i < size/2 ? i * 2 : (size - i) * 2 - 1]
我认为它不能一次性完成，除非“让他们留在原地”意味着“他们最终在哪里并不重要”。
这是我两次通过的尝试:)
void zeroone(int *arr, size_t n) {
int *ptr = arr;
size_t nn = n;
int s = 0;
/* if the array has an odd number of elements
** the number of 0's is different then the number of 1's */
if (n % 2) return;
/* 1st pass */
while (nn--) s += *ptr++;
/* if there are as many 0's as 1's */
if (s+s == n) {
/* 2nd pass */
for (nn = 0; nn < n; nn += 2) {
arr[nn] = 0;
arr[nn + 1] = 1;
}
}
}
int a[10] = {1, 1, 0, 1, 1, 0, 1, 1, 1, 0};
int i;
int count_0 = 0;
int count_1 = 0;
for(i = 0; i < 10; i++)
{
if(a[i] == 0)
{
if(count_1 > 0)
{
if(i % 2 == 0)
{
a[i-2*count_1+1] = 0;
a[i] = 1;
count_1--;
}
else
{
a[i-2*count_1] = 0;
a[i] = 1;
}
}
else
{
if(i % 2 == 0)
count_0++;
}
}
else
{
if(count_0 > 0)
{
if(i % 2 != 0)
{
a[i-2*count_0+1] = 1;
a[i] = 0;
count_0--;
}
else
{
a[i-2*count_0] = 1;
a[i] = 0;
}
}
else
{
if(i % 2 != 0)
count_1++;
}
}
}
循环遍历数组，维护 3 个变量和数组的不变量：
pos都已经整理好了。color是应该放置在的元素的颜色pos。pos和之间next的所有东西都具有相同的颜色。无论如何，它似乎工作。
def odd_even_sort(xs):
color = 0
pos = 0
next = pos + 1
while next < len(xs):
if xs[pos] == color:
pos += 1
if pos >= next:
next = pos + 1
color = not color
elif xs[next] == color:
xs[pos], xs[next] = xs[next], xs[pos]
next += 1
pos += 1
color = not color
else:
next += 1
xs = [0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1]
odd_even_sort(xs)
print xs
This will do it. The result is different from the proposed output, but is equal to the rules given (the text of the problem doesn't include the word "sort", only that at the end you have to move all the 0 you can in even positions and the 1 you can in odd positions. You don't need to "compact" them). It's a little more complex to do it "compacting".
static void Main(string[] args)
{
var input = new[] { 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1 };
var lastEvenToMove = -1;
var lastOddToMove = -1;
for (int i = 0; i < input.Length; i++)
{
bool needEven = i % 2 == 0;
bool isEven = input[i] == 0;
if (needEven == isEven)
{
continue;
}
if (needEven)
{
if (lastEvenToMove != -1)
{
var old = input[lastEvenToMove];
input[lastEvenToMove] = 1;
input[i] = 0;
lastEvenToMove = old;
}
else
{
input[i] = lastOddToMove;
lastOddToMove = i;
}
}
else
{
if (lastOddToMove != -1)
{
var old = input[lastOddToMove];
input[lastOddToMove] = 0;
input[i] = 1;
lastOddToMove = old;
}
else
{
input[i] = lastEvenToMove;
lastEvenToMove = i;
}
}
}
while (lastEvenToMove != -1)
{
var old = input[lastEvenToMove];
input[lastEvenToMove] = 0;
lastEvenToMove = old;
}
while (lastOddToMove != -1)
{
var old = input[lastOddToMove];
input[lastOddToMove] = 1;
lastOddToMove = old;
}
Console.WriteLine(@"{{{0}}}", String.Join(", ", input.Select(p => p.ToString())));
}
I keep a stack of the odds and a stack of the even elements that need moving, and I use these when I need an odd/even number. The two stacks are keeped in the input array, so no extra space (except the two "heads" of the two stacks, that are two extra integers). I think the worst case is O(1.5n) for time (for example all the elements are 1, half of the elements are "put" in the stack and then need resetting because there wasn't an empty space), and O(1) for space.
Output:
{0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1}
#include<iostream>
using namespace std;
//////////////////////////////////////////
int a[]={1,1,0,1,0,1,1,1,0,1,0,1,0,0,0,0,1,1,1,1,0,0} ;
int main()
{
int zero = 0, one = 1;
int n = sizeof(a)/sizeof(*a);
int i = 0;
while ( zero < n && one < n)
{
if(a[zero] != 0 && a[one] != 1)
{
swap(a[zero],a[one]);
}
if(a[zero] == 0)
{
zero=zero+2;
}
if(a[one] == 1)
{
one=one+2;
}
}
}
这可以单程完成。
这是另一种使用单通道的解决方案。这个想法是保留两个索引pos_0，pos_1其中保存下一个0或1要放置在数组中的位置。i将用于遍历数组。
//
//array a[] and length are members of the class AlternateZeroAndOne
//
void AlternateZeroAndOne::sortArray()
{
int pos_0 = 0;
int pos_1 = 1;
for (int i=0; i<length; ++i)
{
//
// We have been waiting for a zero to be placed at the correct location.
//
if (pos_0 < pos_1)
{
if (a[i] == 0)
{
swap(pos_0, i);
pos_0+=2;
//
// If we had a 1 already at the right place, increment pos_1.
//
if (a[pos_1] == 1)
pos_1+=2;
}
}
//
// We have been waiting for a one to be placed at the correct location.
//
else
{
if (a[i] == 1)
{
swap(pos_1, i);
pos_1 += 2;
//
// If we had a 0 already at the right place, increment pos_0.
//
if (a[pos_0] == 0)
pos_0+=2;
}
}
}
}
因为它只有 1 和 0，所以您可以计算它们的数量差异，并且排序将非常容易：
int size = arr.length();
int diff = 0, i;
for(i = 0; i < size; i++) // put 0 in odd places and 1 in even and count the extra changes
if(i % 2 == 0)
if(arr[i] == 1){
arr[i] = 0;
diff++;
}
else
if(arr[i] == 0){
arr[i] = 1;
diff--;
}
for(i--; diff != 0; i--){ //make the tail
if(diff > 0) //if we owe 1's put in on 0's
if(arr[i] == 0){
arr[i] = 1;
diff--;
}
if(diff < 0) //if we owe 0's put in on 1's
if(arr[i] == 1){
arr[i] = 0;
diff++;
}
}
很容易看出为什么它是正确的，所以我不会解释。时间复杂度：O(arr.length()) 或 O(n)
#include<stdio.h>
void swap(int *p,int *q)
{
int temp=*p;
*p=*q;
*q=temp;
}
int main()
{
int a[]={0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1};
int z=0,o=1,i;
while(z<17&&o<17)
{
if(a[z]==1&&a[o]==0)
swap(&a[z],&a[o]);
if(a[z]==0)
z+=2;
if(a[o]==1)
o+=2;
}
if(z<17&&a[z]==1)
{
while(z<15)
{
swap(&a[z],&a[z+2]);
z+=2;
}
}
if(o<17&&a[o]==0)
{
while(o<15)
{
swap(&a[o],&a[o+2]);
o+=2;
}
}
for(i=0;i<17;i++)
printf("%d ",a[i]);
}