| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2309 人关注过本帖
标题:链表的快速排序
取消只看楼主 加入收藏
死了都要C
Rank: 4
来 自:四川成都
等 级:贵宾
威 望:13
帖 子:1582
专家分:116
注 册:2006-12-7
结帖率:66.67%
收藏
已结贴  问题点数:20 回复次数:2 
链表的快速排序
我对一个链表做了一个快速排序的函数,感觉好像正确了,但是不知道是不是还有BUG 或是效率还有问题

谁帮我看看啊,哪里有问题指出下,如果效率不好的话,也只说无妨的。


程序代码:
static bool f1(bool (* _p)(_DATA, _DATA), _DATA d1, _DATA d2)
{
    return (*_p)(d1, d2);
}

static bool f2(bool (* _p)(_DATA, _DATA), _DATA d1, _DATA d2)
{
    return !(*_p)(d1, d2);
}

//LINKLISTC 链表类型,
//head头节点
//length链表节点的数量,也就是链表的长度,不含头结点
//_DATA 链表中数据的类型
//_dy比较两个数据大小的函数,前一个大于后一个返回true
//increase true升序,反之降序

static void Qsort(LINKLISTC head, int length, bool (* _dy)(_DATA, _DATA), bool increase)
{
    if(length > 1)//至少有2个节点
    {
        LINKLISTC leftp = head->_n;
        LINKLISTC  pos  = head->_n;//为分界节点的地址
        LINKLISTC  now  = pos;
        LINKLISTC  fpos = pos;
        int len = 0;

        _DATA  data = leftp->_d;

        bool (*f)(bool (*_p)(_DATA, _DATA), _DATA d1, _DATA d2) = increase ? f1 : f2;

        for (int i = 1; i < length; ++i)
        {
            LINKLISTC     nown = now->_n->_n;

            if((*f)(_dy, data, now->_n->_d))//比较两个对象的大小。
            {
                if( pos != now )//交换
                {
                    LINKLISTC ptf = pos->_n, ptb = now->_n, pte; //ptf, ptb分别指向前后要交换数据的两个节点

                    pos->_n = ptb;
                    now->_n = ptf;
                    pte = ptb->_n;
                    ptb->_n = ptf->_n;
                    ptf->_n = pte;
                }
                fpos = pos;
                pos  = pos -> _n;
                ++len;

                if(nown == now->_n)
                    continue;
            }
           
            now = now -> _n;
        }//大小区交换完毕

        if(pos != leftp)//更换大小区界限元素
        {
            LINKLISTC ppn;

            head->_n = pos;
            fpos->_n = leftp;
            ppn = pos->_n;
            pos->_n = leftp->_n;
            leftp->_n = ppn;
        }

        Qsort(head, len, _dy, increase);
        Qsort(leftp, length - len - 1, _dy, increase);
    }
}


搜索更多相关主题的帖子: 快速 
2011-11-25 23:19
死了都要C
Rank: 4
来 自:四川成都
等 级:贵宾
威 望:13
帖 子:1582
专家分:116
注 册:2006-12-7
收藏
得分:0 
什么意思~~没懂啊

当然还写啊··不过还是入门级别。写的将将就就,速度也不快,哎,还要继续加强啊

女施主``我给你``送茶来了```师太``你就从了老衲吧``
代码本天成~~~妙头偶得之```
2011-11-27 11:23
死了都要C
Rank: 4
来 自:四川成都
等 级:贵宾
威 望:13
帖 子:1582
专家分:116
注 册:2006-12-7
收藏
得分:0 
以前在学学校的时候一直都是兴趣,也打算作为事业,毕业后挣钱吃饭去了,所以有近4年没再接触过··

现在又打算改行,所以回来继续走这条路啊。

女施主``我给你``送茶来了```师太``你就从了老衲吧``
代码本天成~~~妙头偶得之```
2011-11-28 11:38
快速回复:链表的快速排序
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.029654 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved