算法分析_3次反转算法.cpp

来自「三次反转算法 是一个线性时间算法 实现数组的反转 有详细的注释」· C++ 代码 · 共 44 行

/************************************************************************/
/*数字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");
		
}