  We study non-Hermitian Aubry-Andr\'{e}-Harper models with p-wave pairing,
where the non-Hermiticity is introduced by on-site complex quasiperiodic
potentials. By analysing the $\mathcal{PT}$ symmetry breaking, winding numbers
of energy spectra, localization and fractal dimensions of states, and fate of
Majorana fermions, a complete phase diagram on Anderson localization and
topological phase transitions is obtained. In particular, the non-Hermitian
topological nature of Anderson localization phase transitions from extended to
critical and then to localized phases is identified, using both analytical and
numerical methods. In the critical phase the complex spectrum is topological
nontrivial with a fractional winding number. In the localized phase the
analytical localization length of states can apply to the Hermitian case, which
is absent so far. Both the non-Hermiticity and disorder are detrimental to
Majorana fermions.
