arrays - 如何就地洗牌

Question

有一个奇数和偶数相等的数组。这些数字没有特定的顺序存储。是否可以就地洗牌（O(1)额外空间）数组，以便偶数指向偶数索引，奇数指向奇数索引？

当然，使用辅助存储来实现是微不足道的，不使用辅助存储的限制使它变得困难。另外，没有模式，在将数组改组[a1,a2,a3..an,b1,b2...bn...n1,n2,n3...nn]到的问题中[a1,b1,c1..n1,a2,b2,c2...n2,...an,bn...nn]，有一个固定的映射，可以做到这一点。但是这里没有这样的模式，它完全可行吗？

Answer 1

编写两个迭代器。一个在偶数位置迭代所有奇数的数组索引。另一个在奇数位置迭代所有偶数。

同时迭代两者，并交换迭代器指向的项目，直到数组的末尾。应该有 O(n) 的性能。

Answer 2

保留两个索引，一个用于奇数，一个用于偶数，并始终定位具有奇/偶内容的第一个偶/奇索引，然后交换：

int even = 0, odd = 1;
do {
    while(even < size && array[even] % 2 == 0) even += 2;
    while(odd < size && array[odd] % 2 == 1) odd += 2;
    if (even < size && odd < size) {
        int temp = array[even];
        array[even] = array[odd];
        array[odd] = temp;
    }
}while(even < size && odd < size);