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