To quantitatively evaluate the complexities and heterogeneities of pore structures in sandstone reservoirs, we apply single fractal theory and multifractal theory to explore the fractal characteristics of pore size distributions based on mercury intrusion porosimetry. The fractal parameters were calculated and the relationships between the petrophysical parameters (permeability and entry pressure) and the fractal parameters were investigated. The results show that the single fractal curves exhibit two-stage characteristics and the corresponding fractal dimensions D1 and D2 can characterize the complexity of pore structure in different sizes. Favorable linear relationships between log(ε) and log(μ,(ε)) indicate that the samples satisfy multifractal characteristics and ε is the sub-intervals with size ε = J × 2−k. The multifractal singularity curves used in this study exhibit a right shape, indicating that the heterogeneity of the reservoir is mainly affected by pore size distributions in sparse regions. Multifractal parameters, D(0), D(1), and Δf, are positively correlated with permeability and entry pressure, while D(0), D(1), and Δf are negatively correlated with permeability and entry pressure. The ratio of larger pores volumes to total pore volumes acts as a control on the fractal dimension over a specific pore size range, while the range of the pore size distribution has a definite impact on the multifractal parameters. Results indicate that fractal analysis and multifractal analysis are feasible methods for characterizing the heterogeneity of pore structures in a reservoir. However, the single fractal models ignore the influence of microfractures, which could result in abnormal values for calculated fractal dimension. Compared to single fractal analysis, multifractal theory can better quantitatively characterize the heterogeneity of pore structure and establish favorable relationships with reservoir physical property parameters.