In Wi-Fi based indoor localization, the fingerprint approach is one of the most popular solutions to achieving satisfactory positioning performance based on the requirements of many commercialized applications. However, the performance of such an approach heavily relies on the density of reference points collected offline. Previous efforts have tried to use regression based approaches to alleviate the influence caused by the sparsity of fingerprints and enhance the localization accuracy. Nevertheless, we observe that regression based methods are not applicable in complex environments. We first verify this observation based on experiments and give insight into the problem. Then a general framework is proposed to handle fingerprint sparsity in complex environments (HFSCE). In HFSCE, the density-based spatial clustering of applications with noise (DBSCAN) algorithm is adopted to reduce the impact of complex indoor environments on regression. The purpose is to distinguish uncorrelated Received Signal Strength (RSS) data and cluster similar RSS data. After the clustering of RSS data, regression approaches are applied to estimate the continuous space and hence the localization model is built with finer pattern of the environment. Note that the proposed HFSCE framework can accommodate any regression model. In the online phase, we design an algorithm selection scheme, which chooses the most suitable localization approach and regression model for current RSS input. Series of experiments show our proposed approach has significant improvement in localization accuracy when compared with the state-of-the-art approaches.