25-选择排序算法

11.6.2　选择排序算法

我们采用选择排序算法（selection sort algorithm）来排序指针。具体做法是，利用 for 循环依次把每个元素与首元素比较。如果待比较的元素在当前首元素的前面，则交换两者。循环结束时，首元素包含的指针指向机器排序序列最靠前的字符串。然后外层 for 循环重复这一过程，这次从 input 的第2个元素开始。当内层循环执行完毕时， ptrst 中的第2个元素指向排在第2的字符串。这一过程持续到所有元素都已排序完毕。

现在来进一步分析选择排序的过程。下面是排序过程的伪代码：

for n = 首元素至 n = 倒数第2个元素,
     找出剩余元素中的最大值，并将其放在第n个元素中

具体过程如下。首先，从 n = 0 开始，遍历整个数组找出最大值元素，那该元素与第1个元素交换；然后设置 n = 1 ，遍历除第1个元素以外的其他元素，在其余元素中找出最大值元素，把该元素与第2个元素交换；重复这一过程直至倒数第2个元素为止。现在只剩下两个元素。比较这两个元素，把较大者放在倒数第 2 的位置。这样，数组中的最小元素就在最后的位置上。

这看起来用 for 循环就能完成任务，但是我们还要更详细地分析“查找和放置”的过程。在剩余项中查找最大值的方法是，比较数组剩余元素的第1个元素和第2个元素。如果第2个元素比第1个元素大，交换两者。现在比较数组剩余元素的第1个元素和第3个元素，如果第3个元素比较大，交换两者。每次交换都把较大的元素移至顶部。继续这一过程直到比较第1个元素和最后一个元素。比较完毕后，最大值元素现在是剩余数组的首元素。已经排出了该数组的首元素，但是其他元素还是一团糟。下面是排序过程的伪代码：

for n - 第2个元素至最后一个元素,
     比较第n个元素与第1个元素，如果第n个元素更大，交换这两个元素的值

看上去用一个 for 循环也能搞定。只不过要把它嵌套在刚才的 for 循环中。外层循环指明正在处理数组的哪一个元素，内层循环找出应存储在该元素的值。把这两部分伪代码结合起来，翻译成C代码，就得到了程序清单11.29中的 stsrt() 函数。顺带一提，C库中有一个更高级的排序函数： qsort() 。该函数使用一个指向函数的指针进行排序比较。第16章将给出该函数的用法示例。