中文摘要：

FFT整序的关键是逆序号的求取，用预先存贮的逆序表可提高FFT整序的效率．算法结合分治与贪婪策略，用最少的交换次数得到逆序表．算法避免了常规整序中顺序号与逆序号的比较运算，提高了FFT整序的效率．为了比较相关算法在Windows操作系统下的运行效率，编制了相应的C＋＋程序．实验表明，求取长2^N的逆序表时，算法的交换次数为数组长的一半（2^N-1或2^N-1 -2），其效率优于传统的整序算法．

英文摘要：

How to rapidly obtain the inverse number is one of the most important steps in FFT permutation. With an array storing some inverse order numbers of the indices beforehand, the permutation algorithm performance may be improved. This paper presents an algorithm with divide-and-conquer and greedy strategy, and the inverse order array can be obtained with least exchange times. The algorithm avoids the comparison operations that need to be implemented in general permutation algorithm. Therefore, the algorithm performance is superior to that of the general. In order to test its performance in windows operation system, several relative algorithms are programmed with C ＋＋ language at the VC2003. net platform, and their operation times are compared. The experiments show the exchange times will be 2^N-1 - 1 or 2^N-1 -2 if the inverse order array length is 2^N, which means that the performance of this algorithm introduced in the paper is better than that of the traditional permutation algorithms.