1 #include <iostream>  2 #include<string>  3 #include <vector>  4 #include <algorithm>  5 using namespace std;  6   7 class node  8 {  9 public: 10     int value; 11     node *next; 12     node():value(0),next(NULL) 13     { 14     } 15     node(int val):value(val),next(NULL) 16      { 17      } 18 }; 19  20 void LinkQuickSort(node*&head) 21 { 22     if (NULL == head->next ) 23     { 24         return; 25     } 26     const int key = head->value; 27     //将链表拆分为三部分 28     node *left = new node;//小于key的链表伪头结点 29     node *right = new node;//大于key的链表伪头结点 30     node *middle = head;//等于key的链表头结点 31  32     node *lastLeft,*lastRight,*temp,*lastMiddle; 33     lastRight = right;//记录链表最后一个节点 34     lastLeft = left; 35     lastMiddle = middle;     36      37     temp=head->next;//从第二个元素开始 38     lastMiddle->next = NULL; 39     while(NULL != temp) 40     { 41         if((temp->value)> key) 42         { 43             lastRight->next = temp; 44             lastRight = lastRight->next; 45             temp = temp->next; 46             lastRight->next=NULL; 47         } 48         else if ((temp->value) < key) 49         { 50             lastLeft->next = temp; 51             lastLeft = lastLeft->next; 52             temp = temp->next; 53             lastLeft->next=NULL; 54         } 55         else 56         { 57             lastMiddle->next = temp; 58             lastMiddle = lastMiddle->next; 59             temp = temp->next; 60             lastMiddle->next=NULL; 61         } 62     } 63     temp = left; 64     left = left->next; 65     temp->next = NULL; 66     delete temp;//删除伪头结点 67  68     temp = right; 69     right = right->next; 70     temp->next = NULL; 71     delete temp; 72  73     if(NULL != left) 74         LinkQuickSort(left); 75     if (NULL != right) 76         LinkQuickSort(right); 77  78     //合并三个链表 79      80     if (NULL != left)//做链表不为空 81     { 82         temp = left; 83         head = left; 84         while(temp->next!=NULL)//定位最后一个节点 85         { 86             temp = temp->next; 87         } 88         temp->next = middle; 89     } 90     else 91     { 92         head = middle; 93     } 94  95     lastMiddle->next = right;//right 为NULL也无所谓 96      97 } 98  99 int main()100 {101     node *head=new node;102 103     node *temp = head;104     temp->next = new node(5);105     temp = temp->next;106     temp->next = new node(19);107     temp = temp->next;108 109     temp->next = new node(19);110     temp = temp->next;111 112     temp->next = new node(22);113     temp = temp->next;114 115     temp->next = new node(44);116     temp = temp->next;117 118     temp = head;119     head = head->next;120     temp->next = NULL;121     delete temp;122 123     LinkQuickSort(head);124 125     temp = head;126     while(temp!=NULL)127     {128         cout << temp->value <<" ";129         temp = temp->next;130     }131     cout << endl;132 133     return 0;134 }