链表的快速排序 - C语言论坛

楼主

已结贴√ 问题点数：20 回复次数：7

链表的快速排序

我对一个链表做了一个快速排序的函数，感觉好像正确了，但是不知道是不是还有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);
    }
}