快排最核心的思想就是划分，确定一个枢轴元素(pivot)，每一趟划分的目的就是把待排序列分为两部分，前一部分比枢轴小(序列A)，后一部分比枢轴大(序列B)。经过一趟划分之后序列变为：{A} pivot {B}。以下是具体步骤： 1、确定每一次划分的枢轴元素为当前待排序列的头节点。 2、设置Slow和Fast两个游标，Slow指向序列A中的最后一个元素，初始化为枢轴本身(待排序列头节点)。让Fast遍历一遍待排序列，当所指元素比枢轴小时，将Slow往前游一格，交换Slow和Fast所指元素的值，这样仍能保证Slow指向的元素是序列A中的最后一个元素。 3、交换Slow所指元素和枢轴元素的值。这个交换在昨晚一轮遍历后进行的
4、对序列A和B重复步骤1～4。进行分别递归。
5、例子第一行先是按照12步骤进行，然后第二行交换 最后一行又一次递归。
1. struct Node
2. {
3. int key;
4. Node* next;
5. Node(int nKey, Node* pNext)
6. : key(nKey)
7. , next(pNext)
8. {}
9. };
10.
11.
12. Node* GetPartion(Node* pBegin, Node* pEnd)
13. {
14. int key = pBegin->key;
15. Node* p = pBegin;
16. Node* q = p->next;
17.
18. while(q != pEnd)
19. {
20. if(q->key < key)
21. {
22. p = p->next;
23. swap(p->key,q->key);
24. }
25.
26. q = q->next;
27. }
28. swap(p->key,pBegin->key);
29. return p;
30. }
31.
32. void QuickSort(Node* pBeign, Node* pEnd)
33. {
34. if(pBeign != pEnd)
35. {
36. Node* partion = GetPartion(pBeign,pEnd);
37. QuickSort(pBeign,partion);
38. QuickSort(partion->next,pEnd);
39. }
40. }
