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

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

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

        // base case
        if (n == 1) return new Complex[] { a[0] };

        // radix 2 Cooley-Tukey FFT
        if (n % 2 != 0) {
            throw new IllegalArgumentException("n is not a power of 2");
        }

        // fft of even terms
        Complex[] even = new Complex[n/2];
        for (int k = 0; k < n/2; k++) {
            even[k] = a[2*k];
        }
        Complex[] q = fft(even);

        // fft of odd terms
        Complex[] odd  = even;  // reuse the array
        for (int k = 0; k < n/2; k++) {
            odd[k] = a[2*k + 1];
        }
        Complex[] r = fft(odd);

        // combine
        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;
    }
}

使用方法：

Complex[] a = new Complex[8];
a[0] = new Complex(1, 0);
a[1] = new Complex(2, 0);
a[2] = new Complex(3, 0);
a[3] = new Complex(4, 0);
a[4] = new Complex(5, 0);
a[5] = new Complex(6, 0);
a[6] = new Complex(7, 0);
a[7] = new Complex(8, 0);

Complex[] b = FFT.fft(a);

for (int i = 0; i < b.length; i++) {
    System.out.println(b[i]);
}

其中，Complex类表示复数，可以自己实现或引用Java内置的Complex类。这里的fft方法实现了Cooley-Tukey FFT算法，时间复杂度为O(n log n)。