Test case prioritization (TCP) attempts to improve fault detection effectiveness by scheduling important test cases earlier, where important is determined by some criteria and strategy. Adaptive random sequences (ARSs) may be applied to improve the effectiveness of TCP in black-box testing. In this paper, to improve the effectiveness of TCP for object-oriented software, we present an ARS approach based on clustering techniques. In the proposed approach, test cases are clustered according to the number of objects and methods, using two clustering algorithms - K-means and K-medoids. Our proposed sampling strategy can construct ARSs within the clustering framework, constructing two ARS sequences based on the two clustering algorithms, which results in generated test cases with different execution sequences. We also report on experimental studies to verify the proposed approach, with the results showing that our approach can enhance the probability of earlier fault detection, and deliver higher effectiveness than random prioritization.