预计阅读本页时间：-
我们来解决一个把字符串按字母表顺序排序的实际问题。准备花名册、建立索引以及很多其他情况下都会用到字符串的排序。这个程序的一个主要工具就是strcmp（） ，因为可以使用这个函数来决定两个字符串的顺序。一般的做法是读一个字符串数组、对它们进行排序并输出。先前，我们给出了一个读字符串的方案，我们就按那个方案开始该程序。输出字符串不会有什么问题。程序使用的标准排序算法，后面会进行解释。我们在其中采用了一个技巧，看看您能否弄明白它。程序清单11.25给出了程序。
程序清单11.25 sort_str.c程序
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
对于程序清单11.22，我们用一首咿咿呀呀的儿歌来测试：
嗯，看起来这首儿歌经过排序后似乎没有什么变化。
11.6.1 排序指针而不是字符串
程序的技巧部分在于它并不是重新安排字符串本身，而仅仅重新安排指向字符串的指针。让我们解释一下。起初，ptrst[0]被赋值为input[0]，等等。这就是说指针ptrst[i]指向数组input[i]的第一个字符。每个input[i]都是一个含有81个元素的数组，而每个ptrst[i]都是一个变量。排序过程重新安排ptrst，而不改变input。例如，如果input[1]在字母表中先于input[0]，程序就交换ptrsts，使ptrst[0]指向input[1]的开始，使ptrst[1]指向input[0]的开始。这要比使用strcpy（）来交换两个input字符串的内容简单多了。图11.6是这个过程的另一种表示。这种方法的优点还在于保留了原始的字符串顺序。
图11.6 排序字符串指针
11.6.2 选择排序算法
我们使用了选择排序（selection sort）算法来进行指针排序。其思想是使用一个for循环把每个元素轮流与第一个元素比较。如果被比较元素在顺序上先于当前第一个元素，程序就交换这二者。程序执行到循环结束时，第一个元素包含的指针指向在机器编码顺序中排在第一个的字符串。然后外部的for循环重复这个过程，这次是以input的第二个元素作为开始元素。内部循环完成时，ptrst的第二个元素包含的指针就指向顺序排第二的字符串。这个过程一直继续下去，直到所有的元素都已经排好序。
现在再仔细看一下选择排序。下面是用伪代码形式表示的纲要：
流程是这样的：首先以n=0开始。扫描整个数组，找出最大的数，把它和第一个元素交换位置。然后设n=l，扫描数组第一个元素以外的其他元素，找出剩余数中的最大数，并把它和第二个元素交换。继续这个过程，直到倒数第二个元素为止。现在只剩下两个元素，比较它们并把较大的一个放在倒数第二个位置上。最小的元素就放在最后一个位置上。
这看起来像是一个for循环可以完成的任务，但我们还必须更详细地描述这个“查找和放置”的过程。选择剩余最大值的一个办法就是比较剩余数组的第一和第二个元素。如果第二个元素大，就交换这两个数据。现在比较第一个和第三个元素。如果第三个大，就交换这两个数据。每一次交换都把大的元素移到上面。继续这种方法，直到比较第一个和最后一个元素。完成以后，最大的数就在剩余数组的第一个元素中。此时第一个元素已经排好了序，但是数组中的其他元素还很混乱。下面是该过程的伪代码：
这个过程看起来也像是一个for循环可以完成的任务，它会被嵌套在第一个for循环中。外部循环表明要填充哪一个数组元素，内循环找出该数组元素中要放置的值。把这两部分的伪代码结合在一起，并翻译成C，我们就得到了程序清单11. 25中的函数。顺便提一下，C库包含一个更高级的排序函数qsort（） ，它使用一个指向函数的指针来进行排序比较。第16章“C预处理器和C库”给出了这一应用的例子。
