With the proliferation of cloud computing, more and more functionally equivalent cloud services with varied quality of service (QoS) have emerged. Service selection for a SaaS (Software as a Service) has become a critical issue in cloud environments, and the transition from single-tenancy to multi-tenancy has made this issue more complicated. Existing approaches suffer from low efficiency in finding optimal solutions, especially in large-scale scenarios. As a result, QoS-aware service recommendation is becoming increasingly important for selecting services for a multi-tenant SaaS that simultaneously serves multiple clients with differentiated QoS requirements. In this paper, we propose a novel service recommendation approach that largely improves the efficiency of QoS-aware service selection for multi-tenant SaaS. Our approach significantly reduces the search space of the service selection problem by selecting representative candidate services based on the diversity and similarity in tenants' QoS requirements for the SaaS. The experimental results demonstrate the effectiveness and efficiency of our approach.