完美洗牌算法（1）

题目描述;
    有一个长度为2n的数组{a1,a2,a3,...,an,b1,b2,...,bn}，希望排序后变成{a1,b1,a2,b2,...an,bn}.
解法1：
位置置换算法
设定数组下标从1开始

原始序列	A1	A2	A3	A4	B1	B2	B3	B4
数组下标	1	2	3	4	5	6	7	8
最终序列	B1	A1	B2	A2	B3	A3	B4	A4

通过对比原始序列与最终前后位置的变化
前n个元素中（1->2,2->4,2->6,4->8)
推广到一般情况，前n个元素中，第i个元素去了第2i个元素的位置
后n个元素中（5->1,6->3,7->5,8->7）
推广到一般情况，后n个元素中，第i个元素去了第2(i-n)-1=2i-(2n+1)=2i%(2n+1)
综合到任意情况，任意的第i个元素都最终换到了(2i)%(2n+1)的位置
c代码如下：

#include<stdio.h>
#include<stdlib.h>
#define N 9
#define swap(t,x,y) (t = (x),x = (y),y = (t))
int b[N];
void LocationReplace(int *a,int n)
{
    int i = 0,n1 = 2*n,temp = 0;
    for (i = 1;i <= n1 ;i++)
    {
        b[(2*i)%(2*n+1)] = a[i];//这里不要写成2i,2n,忘了*
    }
    for (i = 1;i <= n1 ;i++ )
    {
        a[i] = b[i];
    }
    for (i = 2;i<= n1 ;i += 2 )//交换a[1]和a[2],a[3]和a[4]...
    {
        swap(temp,a[i-1],a[i]);
    }
}
int main()
{
    int a[9] = {0,1,2,3,4,5,6,7,8};
    LocationReplace(a,4);
    int i = 0;
    for (i = 1;i <=8;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;
}

运行结果如下：
[root@localhost ~]# ./a.out
1 5 2 6 3 7 4 8
[root@localhost ~]#   
此程序的时间复杂度是o(n),空间复杂度也是o(n).