/************************************************************************/
/*數字k將數組a分成兩部分:a[0:k-1]，a[k:n-1] 分別記為U,V;換位算法要求將
UV變為VU 。3次反轉算法先將U反轉為U(-1),再將V反轉為V(-1),最后將U(-1)V(-1)
反轉為VU。3次反轉算法用了floor(k/2)+floor((n-k)/2)+floor(n/2)<=n次數組單元
交換運算。每個數組單元交換需要3次元素移動，因此在最壞情況下，3次反轉算法用了3n
次元素移動，顯然用到了O(1)的輔助空間。*/
/************************************************************************/
#include <stdio.h>
#include <algorithm>
using namespace std;
template <typename T>
void reverse(T a[],int i,int j)
{
	while (i<j)
	{
		swap(a[i],a[j]);
		i++;
		j--;
	}
}
template <typename T>
void exch1(T a[],int n,int k)
{
	reverse(a,0,k-1);
	reverse(a,k,n-1);
	reverse(a,0,n-1);
}
void main()
{
	int x[10]={0,1,2,3,4,5,6,7,8,9};
    printf("before exchanged:\n");
	for (int i=0;i<10;i++)
	{
		printf("%d ",x[i]);
	}
	exch1(x,10,3);
	printf("\nafter exchanged:\n");
	for (i=0;i<10;i++)
	{
		printf("%d ",x[i]);
	}
	printf("\n");
		
}