Sandstone reservoir is one of the main types of oil and gas reservoirs in China. It has porous microstructure, which directly affects the transport properties of a sandstone. Hence, the study of porous microstructure is important to the exploration and exploitation of oil and gas. Three-dimensional microstructure of a sandstone can be reconstructed using the simulated annealing method based on statistical properties of its two-dimensional micrograph. The aim of reconstruction is to minimize the discrepancy between the statistical properties of the reconstructed microstructure and those of the two-dimensional image. To accelerate the rate of convergence, we proposed a different-phase neighbours (DPNs)-based pixel selection rule to replace the random pixel selection rule of the simulated annealing reconstruction. In this rule, pixels with the largest number of DPNs have the largest selection probability. The selection probabilities of other pixels are proportional to their DPNs. Microstructure reconstructed with the DPNs-based rule is compared with those with the random selection rule and two other biased pixel selection rules. The DPNs-based rule is the most effective in enhancing convergence. Permeability of the microstructure reconstructed with the DPNs-based rule is estimated by the Kozeny-Carman formula and is in good agreement with the one reconstructed with the random pixel selection rule.