※ 引述《jeunder ()》之铭言： : 就是将 x 的偶数项依序放到 x[0 ~ N-1], : 将 x 的奇数项依序放到 x[N ~ 2N-1]. : 希望能够做到时间复杂度为 O(N), 这显然很容易办到. : 但是我又希望空间复杂度能够是 O(1), 也就是不可以有随 N 而变大的暂存变数. : 这是否有可能办到? : 感觉上似乎和离散数学里面的 permutation group 有关? : 想请教大家的想法. 谢谢. :) 如果只是不要有随 N 变大的暂存变数，则可以用递回。 以下的方法应该是空间 O(logN), 时间 O(N*logN), 不使用变动大小的暂存变数。 但若站在技术性的实用的立场，可能还是我的上一个方法比较好。 而相对於那个漂亮的 space O(1), time O(N^2) 转置矩阵方法，在 N = 1000 时 swap 数量为 8188 : 499500. --------------------------------------------------------------------- #include <stdio.h> #include <malloc.h> int* x; int n; int k = 0; void swap(int* d, int a, int b) { int t = d[a]; d[a] = d[b], d[b] = t; k++; } void p(int* d, int c) { int t = c / 2; int e = (t + 1) % 2; int i; for(i = 0; i < t; i += 2) swap(d, i, i + t + e); if(e) for(i = 0; i < c; i += 2) swap(d, i, i + 1); if(t < 3) return; p(d + e, t - 1 - e); p(d + t + 1, t - 1 - e); } void main(int argc, char* argv[]) { int i, t; if(argc < 2) return; sscanf(argv[1], "%d", &t); if(t <= 0) return; n = t * 2; x = malloc(n * sizeof(int)); for(i = 0; i < n; i++) x[i] = i; p(x + 1, n - 2); printf("swap number = %d\n", k); } -- ※ 编辑: semop 来自: 59.116.1.213 (11/23 01:29)