给你一堆标上数字的牌,一个通常的排序方法是选择并且拿走最大的牌,然后重复这个过程直到所有的牌都被拿走。这个方法描述了选择排序的过程,如例4-8所示。
例4-8:选择排序的C语言实现
选择排序在本章描述的算法中是最慢的,即使在最好情况下(如数组已经有序)它都需要二次方时间。它重复地进行着几乎相同的工作,而不会从每一次迭代中学到什么东西。在数组A选择最大的元素max需要n-1次比较,选择第二大的需要n-2次比较。很多比较都是浪费的,因为如果一个元素比第二大的元素小,那么它不可能是最大的元素,所以就不会对max的选择有任何影响。我们将不会阐述关于这个低效算法的更多细节,现在我们看看堆排序,这个算法展示了如何高效地应用选择排序背后隐藏的原理。