New partial relay selection schemes for cooperative diversity based on amplify-and-forward (AF) relaying are proposed in Nakagami-m fading channels. Their performances are compared with the conventional partial selection scheme. Numerical results show that the new schemes have performance gains of up to 5 dB over the conventional scheme. In some cases, their performances are indistinguishable from the full selection scheme, but they have much simpler structures. Numerical results also show that it is more important to choose the idle user for the hop with a small average signal-to-noise ratio (SNR) or an m parameter in partial selection. Based on this observation, a new adaptive partial selection scheme based on the average SNR, and the m parameter is derived. A complexity analysis also shows that the new schemes reduce the complexity in some cases.