java实现快速傅里叶变换FFT（附完整源码）

以下是Java实现快速傅里叶变换FFT的完整源码示例：

public class FFT {
    public static Complex[] fft(Complex[] x) {
        int n = x.length;

        // 递归终止条件
        if (n == 1) {
            return new Complex[] { x[0] };
        }

        // 计算偶数项和奇数项的DFT
        Complex[] even = new Complex[n/2];
        Complex[] odd = new Complex[n/2];
        for (int i = 0; i < n/2; i++) {
            even[i] = x[2*i];
            odd[i] = x[2*i + 1];
        }
        Complex[] q = fft(even);
        Complex[] r = fft(odd);

        // 合并两个DFT
        Complex[] y = new Complex[n];
        for (int k = 0; k < n/2; k++) {
            double kth = -2 * k * Math.PI / n;
            Complex wk = new Complex(Math.cos(kth), Math.sin(kth));
            y[k] = q[k].plus(wk.times(r[k]));
            y[k + n/2] = q[k].minus(wk.times(r[k]));
        }
        return y;
    }

    public static void main(String[] args) {
        Complex[] x = { new Complex(1, 0), new Complex(2, 0), new Complex(3, 0),
                        new Complex(4, 0), new Complex(0, 0), new Complex(0, 0),
                        new Complex(0, 0), new Complex(0, 0) };
        Complex[] y = fft(x);
        for (int i = 0; i < y.length; i++) {
            System.out.println(y[i]);
        }
    }
}

class Complex {
    private final double re;
    private final double im;

    public Complex(double real, double imag) {
        re = real;
        im = imag;
    }

    public Complex plus(Complex b) {
        double real = re + b.re;
        double imag = im + b.im;
        return new Complex(real, imag);
    }

    public Complex minus(Complex b) {
        double real = re - b.re;
        double imag = im - b.im;
        return new Complex(real, imag);
    }

    public Complex times(Complex b) {
        double real = re * b.re - im * b.im;
        double imag = re * b.im + im * b.re;
        return new Complex(real, imag);
    }

    public String toString() {
        return "(" + re + ", " + im + ")";
    }
}

在上述示例中，我们定义了一个Complex类来存储复数。fft()方法实现了快速傅里叶变换，它使用递归算法计算输入序列的DFT。最后，我们使用main()方法来测试fft()方法，输出变换后的结果。