有了上面的排列规律，我们很容易地写出下面的FFT算法伪代码：

　　

　　void FFT(Comp* x, int M)
　　// x 是存有输入数据的复数数组，元素个数为2M
　　// FFT变换结果存入数组x中返回
　　{
　　　计算数组元素数目；
　　　按二进制倒读次序对输入数据进行整序； // 使得输入结果为自然次序
　　　计算旋转因子并保存到数组W中； // 避免旋转因子的重复运算

　　　对各级进行如下处理　
　　　　{
　　　　　计算当前级内的组数与组内单元数；
　　　　　依次处理级内各组　
　　　　　　｛
　　　　　　　依次处理组内各蝶形单元　
　　　　　　　　｛
　　　　　　　　　分别计算当前蝶形单元所含的两个元素在数据数组中的位置；
　　　　　　　　　从旋转因子数组中取出当前蝶形单元对应的旋转因子；
　　　　　　　　　计算旋转因子与蝶形单元第二元素的复数乘积；
　　　　　　　　　按蝶形运算关系，计算最终结果,存入数组的原先位置；
　　　　　　　　}　// 群内循环
　　　　　　}　// 级内循环
　　　　　} // 所有各级的循环
　　　　　// 至此，数组x中已经是原输入数据的DFT运算结果了
　　　　}

　　前面我们讨论了FFT的算法实现。那么IDFT又如何实现快速算法呢？这就要解决IFFT的实现了。
　　其实，上面关于离散傅里叶变换的快速算法原理，同样也是适用于求逆变换的（通常以IFFT来表示）。它们的差别仅仅在于，当求IDFT时，旋转因子改为 （而不是 ），而且由定义式，最终的运算结果都应除以系数N。
　　显然，按上面的分析，IFFT的实现完全可以与FFT共享同一个流程（框架）。一个简单的实现技巧就是：在函数调用时，传入一个指示符，表示当前要进行的正变换，还是逆变换。根据不同的需求，使用不同的旋转因子，并决定是否对最终结果除以系数N，而程序中的其它部分都就必修改了。
　　FFT真是不错！你是不是觉得感觉好极啦？