最近一直在看傅里叶变换，看到FFT算法，其实算法的关键之一，蝶形运算，只要看懂了，编码实现并不难。反倒是其中位码倒序的环节，看很容易看懂，但是编码实现不是那么容易的。在网上参考了很多资料后，决定把下面这个算法分享给大家，在这里要感谢百度文库用户letsgotoyy123提供的《快速傅里叶变换FFT及其应用》一文（http://wenku.baidu.com/view/7e9f6e6ea1c7aa00b42acb84）还要感谢星星同学，在一些基础知识上的指点，谢谢。
#include<iostream>
#include<cmath>
using namespace std;
const int N=16;
int main()
{
int src[N]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
cout<<"原始数组为："<<endl;
for(int i=0;i<N;i++)
{
cout<<src[i]<<" ";
}
cout<<endl;
int k;
int j;
int count=0;
//i和j就是需要交换的数组元素的索引
//i是从第二个元素一直增加到倒数第二个元素
//关键是求j
//当i<j时交换，以避免重复交换。
for(i=1,j=N/2;i<=N-2;i++)
{
if(i<j)
{
//交换
int t=src[j];
src[j]=src[i];
src[i]=t;
}
k=N/2;
cout<<"i="<<i<<",j="<<j<<",k="<<k<<endl;
//求下一个j
while(k<=j)
{
j=j-k;
k=k/2;
}
//这就是下一个j
j=j+k;
//输出每次交换后的数组
cout<<"第"<<++count<<"次变换后的数组："<<endl;
for(int m=0;m<N;m++)
{
cout<<src[m]<<" ";
}
cout<<endl;
}
cout<<"位码倒序后的数组为："<<endl;
for(int n=0;n<N;n++)
{
cout<<src[n]<<" ";
}
cout<<endl;
return 0;
}
/*****
