With the rapid development of electric vehicles (EVs), the impacts on power grids arising from EV charging have drawn increasing attention worldwide. Uncoordinated charging of large-scale EVs will inevitably elevate load peaks at rush hours, therefore, poses serious challenges to the stability and security of power grid. Coordinated charging is expected to alleviate these negative impacts by utilizing the surplus power in the lower-demand hours with the help of the so-called valley filling algorithm. Nevertheless, when the amount of EVs involved reaches 1 million or above, the complexity of the scheduling method becomes a critical issue. In this paper, a very high efficient valley-filling strategy is proposed. Two key indexes, viz., capacity margin index and charging priority index are defined, the former one is used to select the target time slots on which the power grid has abundant surplus power for EV charging, and the latter one is used to determine the charging priority of EVs on each time slot. The simulation results demonstrate that the coordinated charging scheme with the proposed valley-filling strategy significantly outperforms the uncoordinated charging in the aspect of suppressing the elevated peak loads of power grid. Moreover, the complexity analysis shows that the proposed algorithm is much high-efficient than its existing counterparts.