11.6 字符串示例：字符串排序

处理一个按字母表顺序排序字符串的实际问题。准备名单表、创建索引和许多其他情况下都会用到字符串排序。该程序主要用strcmp()函数来确定两个字符串的顺序。一般的做法是读取字符符函数、排序字符串并打印出来。之前，设计过一个读取字符串的方案。打印字符串没问题。程序使用标准的排序算法。

//sort_str.c    --读入字符串，并排序字符串
#include<stdio.h>
#include<string.h>
#define SIZE 81
#define LIM 20          //可读入的最多行数
#define HALT ""       //空字符串停止输入
void stsrt(char *strings[],int num);
char *s_gets(char *string,int n);
int main(void)
{
    char input[LIM][SIZE];      //存储输入的数组 
    char *ptstr[LIM];           //内含指针变量的数组
    int ct = 0;                 //输入计数
    int k;                      //输出计数

    printf("Input up to %d lines,and I will sort the them.\n",LIM);
    printf("To stop, press the Enter key at a lines's start.\n");
    while(ct < LIM && s_gets(input[ct],SIZE)!=NULL && input[ct][0]!='\0')
    {
        ptstr[ct] = input[ct];      //设置指针指向字符串
        ct ++; 
    }
    stsrt(ptstr,ct);            //字符串排序函数
    puts("\nHere's the sorted list:\n");
    for(k = 0;k<LIM;k++)
        puts(ptstr[k]);

    return 0;
}
char *s_gets(char *string,int n)
{
    char *ret_val;
    int i = 0;

    ret_val = fgets(string,n,stdin);
    if(ret_val)
    {
        while(string[i]!='\n'&&string[i]!='\0')
            i++;
        if(string[i]=='\n')
            string[i]='\0';
        else
            while(getchar()!='\n')
                continue;
    }

    return ret_val; 
 } 
void stsrt(char *strings[],int num)         //字符串-指针-排序函数 
{
    char *temp;
    int top,seek;

    for(top = 0;top<num-1;top++)
        for(seek = top+1;seek<num;seek++)
            if(strcmp(strings[top],strings[seek])>0)
                {
                    temp = strings[top];
                    strings[top] = strings[seek];
                    strings[seek] = temp;
                }
}

11.6.1 排序指针而非字符串

该程序的巧妙之处在于排序的是指向字符串的指针，而不是字符串本身。
具体分析：
最初，ptrst[0]被设置为input[0],ptrst[1]被设置为input[1],以此类推。这意味着指针ptrst[i]指向数组input[i]的首字符。每个input[i]都是一个内含81个元素的数组，每个ptrst[i]都是一个单独的变量。排序过程中把ptrst重新排列，并未改变input。例如，如果按照字母顺序input[1]在input[0]前面，程序便交换它们的指针（即ptrst[0]指向input[1]）的开始，而ptrst[1]指向input[0]的开始）。这样做比用strcpy交换两个input字符串的内容简单的多，而且保留了input数组中的原始顺序。

11.6.2 选择排序算法

我们采用选择排序算法（selection sort algorithm）来排序指针。具体做法是，利用for循环依次把每个元素与首元素比较。如果待比较的元素在当前首元素的前面，则交换两者。循环结束时，首元素包含的指针指向机器排序序列最靠前的字符串。然后外层for循环重复这一过程，这次从input的第2个元素开始。当内层循环执行完毕时，ptrst中的第2个元素指向排在第2的字符串。这一过程持续到所有元素都已排序完毕。
现在来进一步分析选择排序的过程：
for n = 首元素 至n = 倒数第2个元素
    找出剩余元素中的最大值，并将其放在第n个元素中
具体过程：
首先，从0开始，遍历整个数组找出最大值元素，那该元素与第1个元素交换；然后设置n = 1，遍历除第1个元素以外的其他元素，在其余元素中找处最大值元素，把该元素与第2个元素交换；重复这一过程，直到倒数第2个元素为止。现在只剩下两个元素。比较这两个元素，把较大者放在倒数第2的位置。这样，数组中的最小元素就在最后的位置上。
这看起来用for循环就能完成任务，但是我们还要更详细地分析“查找合放置”的过程。在剩余项中查找最大值的办法是，比较数组剩余元素的第一个元素合第2个元素。如果第2个元素比第1个元素大，交换两者。现在比较数组剩余元素的第1个元素合第3个元素，如果第3个元素比较大，交换两者。每次交换都把较大的元素移到顶部，这一过程直到比较低1个元素合最后一个元素。比较完毕后，最大值元素现在是剩余数组的首元素。已经排出了该数组的首元素。但是其他元素还是一团糟，下面是过程的伪代码：
for n-第2个元素至最后一个元素，
    比较第n个元素与第1个元素，如果第n个元素更大，交换这两个元素
看上去用一个for循环也能搞定，只不过要把它嵌套在刚才的for循环中。外层循环指明了正在处理数组元素的哪一个元素，内层循环找出应存储在该元素的值。
qsort()

//冒泡排序
//buffersort.c
#include<stdio.h>
void sort(char *ar,int n);
void max(char *ar,int n);
int main(void)
{
    int i;
    char ar[]= {9,1,2,3,4,5,6,7,8};
    sort(ar,9);
    for(i = 0;i < 9;i++ )
        printf("%d ",ar[i]);
    return 0;
}
void max(char *ar,int n)
{

    int i;
    int temp;
    for(i=0;i<n-1;i++)
        if(ar[i]>ar[i+1])
        {
            temp = ar[i];
            ar[i] = ar[i+1];
            ar[i+1] = temp;
        }
}
void sort(char *ar,int n)
{
    int i;
    for(i=n;i>0;i--)
        max(ar,i);
}