function Y=zjfft(x)
x1=changeorder(x);
N=length(x1);
M=log2(N);
Y=zeros(1,N);
B=zeros(1,N);

Y=x1;

for i=1:M
    B=Y;
    for r=1:N
        %B=Y;
        zf=((-1).^floor((r-1)/(2.^(i-1))));
        W=exp(-j*2*pi*mod(r-1,2.^(i-1))/2.^i);
        Y(r)=zf*B(r)*W.^((zf-1)/(-2))+W.^((zf+1)/2)*B(r+zf*2.^(i-1));
    end
end



function xn=myfft(x)
N=length(x);%ȡĘý×鳤¶Č
M=log2(N);%ÇóĘý×鳤¶ČŇÔ2ÎŞµ×µÄĂÝ
%´Ë´¦˝«Ęý×éxĹĹĐňłÉxtmp
%»ů±ľËĽĎ룺˝«ĂżÎ»x(i)ÖеÄiµÄÖµ»»ËăłÉ2˝řÖĆŁ¬Ăż´Î˝«×îµÍλȡłö±Ł´ćµ˝ł¤¶ČÎŞMµÄĘý×éÖĐ
%¸ĂĘý×éµÄ´ÓµÚMλµ˝µÚ1λĹĹżŞľÍĘÇĹĹĐňşóµÄλÖõĶţ˝řÖƱíĘľ
%˝«¸ĂĘý×é»»ËăłÉĘ®˝řÖƵÄĘýľÍĘÇĐňĘýÖŘĹĹşóµÄĐňĘýposŁ¬ÔŮ˝«x(i)¸łÓčxtmp(pos)
%ÓÉÓÚmatlabÖĐĘý×é´Ó1żŞĘĽŁ¬ąĘӦΪx(pos+1)=x(i+1)
xtmp=zeros(1,N);
value=zeros(1,M);
for i=0:N-1
    repr=i;
    for t=1:1:M
        repr=bitshift(i,1-t);
        value(t)=bitand(repr,1);
    end
    pos=0;
    for k=1:1:M
        pos=pos+value(k)*2^(M-k);
    end
    xtmp(pos+1)=x(i+1);
end
%xtmp=x;

%fftÖ÷şŻĘý
%Ö÷ŇŞËĽĎ룺ą˛ÓĐM˛ăĽĆËă
%Ăż˛ă°üŔ¨widthżéĽĆË㣬ÿżéĽäĎŕľŕ2^iµÄľŕŔ루iÎŞµÚi˛ăŁ©
%ĂżżéĽĆËă°üŔ¨deepth¸öµűĐÎÔËËă
for i=1:M
    deepth=2^(i-1);
    width=2^(M-i);
    for t=1:2^i:N
        for k=1:deepth
            tmp=xtmp(t+k-1);
            wn=width*(k-1);
            xtmp(t+k-1)=tmp+exp(-j*2*pi*wn/N)*xtmp(t+k+deepth-1);
            xtmp(t+k+deepth-1)=tmp-exp(-j*2*pi*wn/N)*xtmp(t+k+deepth-1);
        end
    end
end
xn=xtmp;