前一段时间有位朋友要求用链表找出中位数,闲来无事写了个链表的快排.但我想我这应该不算是真正意义上的快排,因为多了一个检查指针位置的函数,时间复杂度上应该是超了.

    另外,如果用这个思路写中位数,应该再多一个从链表头查找第 K 位数的函数,时间复杂度上也应该是超了.

    总之,程序贴出来,请大家多多指教,请高手们不吝指教,本菜多多学习才是,谢谢大家了.

#include <stdio.h>
#include<stdlib.h>

typedef struct tmp
{
    int num;
}tmp;

typedef struct st
{
    tmp *q;
    struct st *ago;
    struct st *after;
}st;

st *make_line();   //  建立链表
st *len_line(st *head);  // 查找链表的尾部
void line_sort(st *head,st *p,st *r);  //  排序
void wap(st *head,st *a,st *b);  // 交换链表的数据
void print(st *head);    // 输出
void del_line(st *head);  // 销毁链表
int check(st *p,st *r);  // 检查指针的位置

int main(void)
{
    st *head,*len;

    head=make_line();
    len=len_line(head);
    line_sort(head,head->after,len);
    print(head->after);
    del_line(head);

    return 0;
}

st *make_line()
{
    st *head,*p,*t;
    tmp *l;
    int n,i=0;

    p=t=NULL;
    while((head=(st *)malloc(sizeof(st)))==NULL);
    head->ago=head->after=NULL;
    while((scanf("%d",&n))==1)
    {
        while((p=(st *)malloc(sizeof(st)))==NULL);
        while((l=(tmp *)malloc(sizeof(tmp)))==NULL);
        l->num=n;
        p->q=l;
        if(!i)
        {
            head->after=p;
            p->ago=head;
            t=p;
            i=1;
        }
        else
        {
            t->after=p;
            p->ago=t;
            t=p;
        }
    }
    p->after=NULL;

    return head;
}

st *len_line(st *head)
{
    st *p=head;

    while(p->after)
    {
        p=p->after;
    }

    return p;
}

void line_sort(st *head,st *p,st *r)
{
    st *i,*j,*d;
    int x;

    if(check(p,r))
    {
        i=p->ago;
        x=r->q->num;
        d=p;
        for(j=p;j!=r;j=j->after)
        {
            if(j->q->num<=x)
            {
                i=i->after;
                if(i!=j)
                {
                    wap(head,i,j);
                }
            }
        }
        i=i->after;
        if(i!=r)
        {
            wap(head,i,r);
        }
        line_sort(head,p,i->ago);
        line_sort(head,i->after,r);
    }
}

void wap(st *head,st *a,st *b)
{
    tmp *t;

    t=a->q;
    a->q=b->q;
    b->q=t;
}

void print(st *head)
{
    while(head)
    {
        printf("%d ",head->q->num);
        head=head->after;
    }
    puts("");
}

int check(st *p,st *r)
{
    while(p)
    {
        if(p->after==r)
        {
            return 1;
        }
        p=p->after;
    }

    return 0;
}

void del_line(st *head)
{
    st *t=NULL;

    while(head)
    {
        t=head;
        head=head->after;
        free(t);
    }
    free(t);
}

   

劳烦您亲自写一下吧,也好让偶菜们好好学习学习.