Abstract: In this paper, PDS and ENNS methods are firstly plugged in the search stage of K-Means iteration.Then by using the indexes obtained from previous iterations, we propose a priority search list (PSL) in order to achieve a smaller value of initial minimum sooner to accelerate K-Means clustering.The experimental results show that the improvements are remarkable without degrading the output performance of K-Means algorithm using 4 test data sets, and the proposed method can reduce computational time to 8.6%~14.5% in the case of generating different size codebooks using the image "Lena".