/***************************************************************************

        这几日经过众网友的鼓励，终于把快排弄得几近明白。不过还是有点小问题：
     在快排中，我把V值定为*a或是数组的a[0],无法进行交换排序。还希望哪位高手
     帮忙解释。
     谢谢。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        本程序经WIN-TC测试正常运行，其它编译器下如有不同，请修改后运行。

***************************************************************************/
#include<stdio.h>
#include<string.h>
#define X {char c;while(c=getchar()!='\n');}
#define N 100
#define Y {printf("共进行了%d次交换。",k);printf("请按任意键继续：\n");getch();}
void jiaohuan(char *a,char *b) /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~交换函数*****/
{
        char t;
        t=*a;
        *a=*b;
        *b=t;
}
void maopao(char a[],int n)  /*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~冒泡法排序*****/
{
        int i,j,k=0;
        for(i=0;i<n;++i)
                for(j=i+1;j<n;++j)
                {
                        if(a[i]<a[j])
                                jiaohuan(&a[i],&a[j]);
                        ++k;
                        puts(a);
                }
        Y;

}
void xuanzhe(char p[],int n) /*~~~~~~~~~~~~~~~~~~~~~~~~~~选择法排序*******/
{
        int i,j,k=0;
        char V;
        for(i=0;i<n;++i)
        {
                V=i;
                for(j=i+1;j<n;++j)
                {
                        if(p[V]<p[j])
                                V=j;
                        if(V!=i)
                        {
                                jiaohuan(&p[V],&p[i]);
                                ++k;
                        }
                        puts(p);
                }
       }
       Y;
}
int kuaipai(char *a,int i,int j,int *k)   /*~~~~~~~~~~~~~~快速排序函数*/
{
        char V;
        int I=i;
        int J=j;
        V=*(a+(i+j)/2);
        while(1)
        {
                while(i<J&&*(a+i)>V)
                        i++;
                while(j>I&&*(a+j)<V)
                        j--;
                if(i>j)
                        break;
                if(i<j)
                {
                        jiaohuan((a+i),(a+j));
                        puts(a);
                        *k+=1;

                }
                i++;
                j--;
        }
        if(I<j)
                kuaipai(a,I,j,&k);
        if(i<J)
                kuaipai(a,i,J,&k);
        return k;

}
int caidan()
{
        int i=0;
        do
        {
                system("cls");
                printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"
                         "这是一个小程序，专门测试各种排序方法。\n"
                         "本程序以ascII降序排列。\n"
                         "请输入您的选择：\n"
                         "1.冒泡法；\n"
                         "2.选择法；\n"
                         "3.快排法；\n"
                         "4.退出。\n");
               scanf("%d",&i);
               X;
               if(i<0||i>4)
               {
                    printf("您的输入错误，请重新输入。\n");
                    sleep(1);
               }
        }
        while(i<0||i>4);

        return i;
}
int shuru(char a[])
{
        int n;
        printf("请输入待排序的数据，enter结束输入：\n");
        gets(a);
        n=strlen(a);
        return n;
}
int main(void)
{
        char a[N];
        int i,n,k;
        while(1)
        {
                i=caidan();
                switch(i)
                {
                        case 1: n=shuru(a);
                                maopao(a,n);
                                break;
                        case 2: n=shuru(a);
                                xuanzhe(a,n);
                                break;
                        case 3: k=0;
                                n=shuru(a);
                                kuaipai(a,0,n-1,&k);
                                Y;
                                break;
                        case 4: exit(0);

                }
        }
}








                        

~~~~~~~~~~~~~~~~~~~~~~~~~
    书上是有，可是书上没写排长度不定的字符串各需要多少步。比如说：排一个“abcdefg”的字符串，头两种都需要21步，而快排只需要3步就可以完成。排一个“0123456789”的字符串，头两种都需要45步，而快排只需要5步。

    呵，我写这个程序是想直观地比较一下各种排序法，时间复杂度我现在还没弄明白，但用这个方法就可以看出来哪个排法比较快捷。

    新手写代码，难免有不足之处，希望大家批评指正。

~~~~~~~~~~
    唉~这事小孩没娘说起来话长。如果想达到那样的程序，还需要进修一下英语才可以。我现在学C的时间都是硬挤出来的，英语——再缓缓吧。

    谢谢指教，待有了时机，一定把英语水平搞上去——也许程序写到一定程度，简单的常用英文也就可以随手拈来了。

~~~~~~~
    麻烦你一下，我这人性子急：你说话能不能说全，不要总说半句留半句的？“噢，我的上帝，你听谁说的？”……这就没了下文，你是吊人家胃口还是什么意思？

    我写的程序中，每一次交换都puts数组一次，所以我依据它的值才说的步数。也许是不对的，但你能不能更正一下啊？

    谢谢你啦，我的上帝。

~~~~~~~~~~~~
    唉~那就是时间复杂度的问题了，以后研究研究它吧。我所做的就是以交换步数体现效率吧，现在的水平我也只能作出这样的程序来了。不过学习中，相信会很快弄明白的。