前面写了个链表的归并排序,这里再写个链表的快排。
链表的快排处理其实跟数组的没什么区别,只是在partition要三位取中的话稍微烦一点;
#include<iostream> #include<vector> #include<ctime> using namespace std; struct ListNode { int val; ListNode* next; }; typedef ListNode LN; LN* getLast(LN* head) { LN* last=head; while(head) { last=head; head=head->next; } return last; } LN* partition(LN* head,LN*& lHead,LN*& lTail,LN*& rHead,LN*& rTail) { if ( !head || head->next==NULL) return head; LN small,*sTail=&small; LN big,*bTail=&big; LN* piv=head; head=head->next; piv->next=NULL; while(head) { if ( head->val<= piv->val) { sTail->next=head; sTail=head; } else { bTail->next=head; bTail=head; } head=head->next; } bTail->next=sTail->next=NULL; lHead=small.next; if (lHead ) lTail=sTail; rHead=big.next; if (rHead ) rTail=bTail; return piv; } void quickSort(LN*& head,LN*& tail) { if (head==NULL||head==tail) return; LN* lHead=NULL,*lTail=NULL; LN* rHead=NULL,*rTail=NULL; LN* piv=partition(head,lHead,lTail,rHead,rTail); quickSort(lHead,lTail); quickSort(rHead,rTail); LN guard; tail=&guard; if ( lHead ) { tail->next=lHead; tail=lTail; } tail->next=piv; tail=piv; if ( rHead ) { tail->next=rHead; tail=rTail; } head=guard.next; } LN* sortList(LN* list) { if ( !list || list->next==NULL) return list; LN* last=getLast(list); quickSort(list,last); return list; } int main() { int n; while(cin>>n) { srand( (unsigned)time( NULL ) ); vector<ListNode> lists(n); for(int i=0;i<n;i++) { lists[i].val=(rand()%100); } for(int i=0;i<n-1;i++) lists[i].next=&lists[i+1]; lists[n-1].next=NULL; ListNode* head=sortList(&lists[0]); cout << 1 <<endl; } }