//快排，冒泡链表排序#include<iostream>#include<assert.h>usingnamespacestd;template<classT>structLinkNode{T_data;LinkNode*_next;LinkNode(constT&x):_data(x),_next(NULL){}};template<classT>classListNode{//为了安全性private:ListNode(constListNode&l){}ListNode<T>&operator=(ListNodel){}public://程序限制LinkNode<T>*_head;public:ListNode():_head(NULL){}~ListNode(){while(_head){PopBack();}}voidPushBack(constT&x){LinkNode<T>*tmp=newLinkNode<T>(x);if(_head==NULL)_head=tmp;else{LinkNode<T>*cur=_head;while(cur->_next)cur=cur->_next;cur->_next=tmp;}}voidPopBack(){if(_head==NULL)return;if(_head->_next==NULL){delete_head;_head=NULL;}else{LinkNode<T>*cur=_head;while(cur->_next&&cur->_next->_next){cur=cur->_next;}LinkNode<T>*del=cur->_next;cur->_next=NULL;deletedel;}}LinkNode<T>*Search(constT&x){if(_head==NULL)returnNULL;LinkNode<T>*cur=_head;while(cur->_data!=x)cur=cur->_next;returncur;}voidPrint(){LinkNode<T>*cur=_head;while(cur){cout<<cur->_data<<"";cur=cur->_next;}cout<<endl;}};template<classT>LinkNode<T>*QuickPartion(LinkNode<T>*begin,LinkNode<T>*end)//前闭后开{if(begin==end)returnbegin;LinkNode<T>*prev,*cur;prev=begin;cur=begin->_next;inttmp=begin->_data;while(cur!=end){if(cur->_data<tmp){prev=prev->_next;if(cur!=prev)swap(cur->_data,prev->_data);}cur=cur->_next;}swap(prev->_data,begin->_data);returnprev;}template<classT>voidQuickSort(LinkNode<T>*head,LinkNode<T>*tail){if(head==NULL||head-==tail)return;LinkNode<T>*mid=QuickPartion(head,tail);QuickSort(head,mid);QuickSort(mid->_next,tail);}template<classT>voidBubbleSort(LinkNode<T>*head){if(head==NULL||head->_next==NULL)return;LinkNode<T>*start=head;LinkNode<T>*end=NULL;LinkNode<T>*curBegin=NULL;intflag=0;while(start->_next){curBegin=start;flag=0;while(curBegin->_next!=end){if(curBegin->_data>curBegin->_next->_data){swap(curBegin->_data,curBegin->_next->_data);flag=1;}curBegin=curBegin->_next;}if(flag==0)break;//优化,若有序，直接跳出end=curBegin;}}template<classT>LinkNode<T>*SearchMidNode(LinkNode<T>*head){if(head==NULL||head->_next==NULL)returnhead;LinkNode<T>*slow=head;LinkNode<T>*fast=head;while(fast&&fast->_next)//偶数个数中间任意一个//while(fast&&fast->_next&&fast->_next->_next)//偶数个数找到中间的第一个{fast=fast->_next->_next;slow=slow->_next;}returnslow;}voidTest1(){ListNode<int>l1;l1.PushBack(10);l1.PushBack(9);l1.PushBack(8);l1.PushBack(7);l1.PushBack(6);l1.PushBack(6);l1.PushBack(5);l1.PushBack(9);l1.PushBack(0);l1.PushBack(1);l1.PushBack(2);/*LinkNode<int>*tail=NULL;QuickSort(l1._head,tail);*///BubbleSort(l1._head);cout<<SearchMidNode(l1._head)->_data<<endl;l1.Print();}