inversort.cpp

FFT 倒序排列算法 自创递归调用实现哈

/************************************************************************/
/*冯启航 2008-3-17 FFT倒序排列算法试验  采用递归方法    
it seems ok!                                                                 */
/************************************************************************/
/*

  [IN] sortin   待排序的数组
  [out] sortout	排序后的输出
  [in] M  排序的阶数
*/
// typedef int INTSORT;
#include <math.h>
#include <iostream.h>
void InverseSort(int *sortin,int M)
{  
	if (M == 1)
	{
		return;
	}
	int n = pow(2,M);//求出需要排列的个数
	int sum = sortin[0] + sortin[n - 1];//这个数是对称数字相加的和
	int i;
	for (i = 0 ; i < (n / 2);i++)
	{
		sortin[i] = sortin[ 2 * i];
	}
	InverseSort(sortin,M - 1);
	for (i = 0 ; i < (n / 2);i++)
	{
		sortin[i + n / 2] = sum - sortin[n / 2 - 1 -i];
	}
	return ;
}

void main()
{
	int i; 
// 	int M = 4;

	int sort[16];
	for (i = 0 ; i < 16; i++)
	{
		sort[i] = i;
	}
	InverseSort(sort,4);
	for (i = 0 ; i < 16; i++)
	{
		cout<<" "<<sort[i];
	}
	return;
}