数组元素换位算法

dirtydog

设a[0:n-1]是一个有n个元素的数组，k(0<=k<=n-1)是一个非负整数。试设计一个算法将子数组a[0:k]与a[k+1:n-1]换位。要求算法在最坏情况下所用的时间为O(n），且只用到O（1）的辅助空间

stoneboy4000

void swap(int a[], int b[], n){
  int i=0;
  int temp; /*O（1）的辅助空间*/
  for(; i < n; i++){
    temp = a[i];
    a[i] = b[i];
    b[i] = temp;
  }
}
void f(int a[], int n, int k){
  int first = k+1;   /*a[0:k]长度*/
  int second = n-first;   /*a[k+1:n-1]长度*/
  if(first==0 || second==0)
    return;
  else if(first <= second){
    swap(a,a+first,first);
    f(a+first,second,first-1);
  }
  else{
    swap(a,a+second,second);
    f(a+second,first,first-second-1);
  }
}
每次分成3段:[short,long-short,(k的位置)short]或是[short,(k的位置)short,long-short]
short和short两个互换，第一段short正确后剩余的两段递归，直到long=short，也可以用循环
类似辗转相减求最大公约数，最坏的情况应该是long和short最大公约数是1

设每次递归：a[]长度L(i) ，swap长度X(i) ，则：
2X(0) < L(0) = 数组总长n
2X(1) < L(1) = L(0)-X(0)
2X(i) < L(i) = L(i-1)-X(i-1) = L(0)-X(0)-X(1)-…-X(i-1)
最后：
2X(N) = L(N) = L(N-1)-X(N-1) = L(0)-X(0)-X(1)-…-X(N-1)
设X(0)到X(N)平均值为X,由于X(0)>X(1)>…>X(N),
所以L(i)=L(0)-X(0)-X(1)-…-X(i-1)<L(0)-X-X-…-X=L(0)-i*X
不等式相加：2*(N+1)*X < (N+1)*L(0)-[N(N+1)/2]*X
==> (2+N/2)*X < L(0)=n 所以时间复杂度(N*X*常数)就是O(n)

aog777ys

先反转a[0:k]
再反转a[k+1:n]
最后反转整个数组

bigfj1234

将a[k+1]...a[n-1]与a[k+1-m]..a[k]进行交换（m为n-1-k,即第2个子数组的个数）
保存k-m的位置给k,重复上述操作直到k<0
最大交换次数为n
void main()
{
        int k1,k,m,temp,i=0;
        const int n=13;
        int a[n]={1,2,3,4,5,6,7,8,9,10,11,12,13};
        cin>>k;

        k1=k;m=n-1-k;
        while(k1>0 && k1<n-1)
        {
                k1 = k+1-m<0 ? 0 : k+1-m;
                while(i!=m)
                {
                        temp = a[k1+i];
                        a[k1+i] = a[k+1+i];
                        a[k+1+i] = temp;
                        i++;
                }
                k = k1-1;
                i = 0;
        }
}

dirtydog

都这么牛！！
不过我觉得aog777ys 的方法更加巧妙！！学习了

还有，我觉得bigfj1234 的方法可能有些问题
a[k+1-m]可能会越界，m=n-1-k
k+1-m=k+1-(n-1-k)=2(k+1)-n
如果k<n/2-1,k+1-m就是小于0

hujintao

programming pearls有这道例题

dirtydog

TO  stoneboy4000：
     你给出的算法有个失误，递归函数f的else语句swap(a,a+second,second);
应为swap(a,a+first,second);
     两个short交换，第二段short的起始元素始终是a+k+1即a+first

菜鸟级高手

我的办法是一个一个位置的覆盖
#include <stdio.h>
//a[0]没有用,a[]有 n+1个元素
void cycle(int a[],int k,int n)
{
        int i, j;
        int tmp, cur,next;
        j=cur=n;
        tmp=a[cur];
        for(i=0;i<k;i++)
        {
                for(;j>k;j-=k)
                        a[j]=a[j-k];
                next=j+n-k;
                if(next==cur)
                {
                        a[j]=tmp;
                        cur--;
                        j=cur;
                        tmp=a[j];
                }
                else
                {
                        a[j]=a[next];
                        j=next;
                }
        }
}
void  main()
{
        int a[10]={0,1,2,3,4,5,6,7,8,9};
        int k;
        scanf("%d",&k);
        cycle(a,k,9);
        for(int i=1;i<10;i++)
                printf("%d\t",a[i]);
}

duxiaolhh

reverse(0, k);
reverse(k+1, n-1);
reverse(0, n-1);

stoneboy4000

确实错了，哎～～～最终还是免不了 cai 一把

2楼的比较好理解，总交换次数n/2 + n/2 = n不变，

bigfj1234的算法应该和我的类似，是从末尾开始，
总交换次数是n-(k+1和n-k-1的最大公约数)，每次交换次数都是放正位置的元素个数，递归到最后时，数组长度是最大公约数的2倍，进行1倍次数的交换后结束

不过一次交换就是三次赋值运算，
菜鸟级高手 的算法（不管正误，只是思路）效率应该是最高的，k个元素平均进行n/k次轮换赋值，总的大概就是k * n/k = n次赋值，但是n/k的余数问题，要理清楚还是很烦的，如果n是k的倍数，就简单了
总之，效率高了理解就麻烦