压缩数组而不创建子数组

Question

是否可以 "zip" 一个数组而不使用 2 个子数组？通常压缩 2 个数组的结果看起来像这样

a1 = [1,2,3]
a2 = [4,5,6]
a3 = zip(a1, a2)
a3 == [1,4,2,5,3,6]

但是，我没有 2 个子数组，我得到的只是一个输入（假设目前无法创建数组），我想将数组压缩到位。例如

a1 = [1,2,3,4,5,6]
zip(a1)
a1 == [1,4,2,5,3,6]

我当前的算法没有正确执行此操作（它导致序列的前半部分正确压缩，但后半部分反向压缩）

array = [1,2,3,4,5,6,7,8]
a = array[0]
b = array[1]
i = 0, j = array.length / 2
while (i + 2 < j)
    array[i] = a
    array[i + 1] = b
    swap(array, i + 1, i + 2)
    swap(array, i + 1, j)
    i += 2, j += 1
    a = b
    b = array[i + 1]

array == [1,5,2,6,4,8,3,7]

不需要完整的答案 - 最好有大致方向的指南。

Answer 1

最简单的方法是为每个元素打开空间交换，向右移动：

void swap(int *array, int left, int right) {
     int tmp = array[right];
     while (right > left)
          array[right] = array[--right];
     array[right] = tmp;
}

现在你只需要调整你的 for 循环索引：

void zip(int *array, int sz) {
     int i, j;
     for (i = 1, j = sz/2; j < sz; i += 2, ++j)
          swap(array, i, j);
}

压缩数组而不创建子数组

zip an array without creating subarrays

arrays

sorting

shuffle

in-place