1、一般教材介绍的数字的快速排序，如下：
（1）Swap函数
void Swap(int &a, int &b)
{
int tmp = a;
a = b;
b = tmp;
}
（2）Partition函数
int Partition(int arr[], int low, int high)
{
int left = low;
int right = high;
int pivot = arr[low];
Swap(arr[low], arr[right]);
while (1) {
while ((low < high) && (arr[low] <= pivot)) {
low++;
}
while ((low < high) && (arr[high] >= pivot)) {
high--;
}
if (low >= high) {
break;
}
Swap(arr[low], arr[high]);
}
Swap(arr[low], arr[right]);
return low;
}
（3）QuickSort函数
void QuickSort(int arr[], int low, int high)
{
if (low >= high) {
return;
}
int index = Partition(arr, low, high);
QuickSort(arr, low, index - 1);
QuickSort(arr, index + 1, high);
}
说明： 这里的Partition函数特别好理解，就是选好基准值后，将它放在数组最后的位置，然后两个索引分别从前到后、从后到前扫描数组，直到左边的索引所在值大于等于基准值、右边的索引所在值小于等于基准值时，将它们交换位置，最终一个数组就被分为小于、大于基准值的两部分。
这个思路本身没有问题，但是它不够通用，因为很多时候面试官会考我们对单向链表进行快速排序，这个时候我们就没办法让一个指针从后向前扫描了。也就是Partition函数不好写。
2、《剑指Offer》上的Partition函数更具通用性，如下：
int Partition(int arr[], int low, int high)
{
int left = low;
Swap(arr[low], arr[high]);
for (int i = left; i < high; i++)
{
if (arr[i] < arr[high]) {
Swap(arr[left], arr[i]);
left++;
}
}
Swap(arr[left], arr[high]);
return left;
}
说明： 这个方法就不需要从后向前扫描了，只有从前向后扫描，很容易推广到单向链表上。
3、根据《剑指Offer》上的Partition函数，推导单向链表的快速排序算法
（1）Node定义
struct Node {
int data;
Node *next;
};
（2）Partition函数
Node* Partition(Node *pLow, Node *pHigh)
{
Node *pLeft = pLow;
Swap(pLeft->data, pHigh->data);
while (pLow) {
if (pLow->data < pHigh->data) {
Swap(pLow->data, pLeft->data);
pLeft = pLeft->next;
}
pLow = pLow->next;
}
Swap(pLeft->data, pHigh->data);
return pLeft;
}
（3）QuickSort函数
QuickSort(Node *pLow, Node *pHigh)
{
if (!pLow || !phigh || pLow >= pHigh) {
return;
}
Node *pMid = Partition(pLow, pHigh);
QuickSort(pLow, pMid); // 注释1
QuickSort(pMid->next, pHigh);
}
说明：
（1）如果完全和vector的快排对比的话，注释1的地方应该是QuickSort(pLow, pMid的前一个元素)，但是求pMid的前一个元素又得耗时，所以没必要。
（2）最终的QuickSort函数用起来并不方便，因为要获取链表最后一个元素传入到QuickSort函数，如下：
Node *GetLastNode(Node *pHead)
{
while (pHead) {
if (!pHead->next) {
return pHead;
}
pHead = pHead->next;
}
}
Node *pHigh = GetLastNode(pHead);
QuickSort(pHead, pHigh);
4、改进版
要解决3里面的问题，很简单，其实完全没必要把“基准值”交换到链表末尾处，就放在链表的起始处即可。
（1）Partition函数
Node *Partition(Node *pLow, Node *pHigh)
{
Node *pPivot = pLow; // 基准值，就放在链表起始位置，不用交换到链表最后
Node *pLeft = pLow->next;
while (pLeft != pHigh) {
if (pLeft->data < pPivot->data) {
pLow = pLow->next;
Swap(pLow->data, pLeft->data);
}
pLeft = pLeft->next;
}
Swap(pLow->data, pPivot->data);
return pLow;
}
（2）QuickSort函数
QuickSort(Node *pLow, Node *pHigh = nullptr)
{
if (!pLow || pLow == pHigh) {
return;
}
Node *pMid = Partition(pLow, pHigh);
QuickSort(pLow, pMid);
QuickSort(pMid->next, pHigh);
}
说明： 由于QuickSort带默认形参pHigh = nullptr，这样调用的时候只需传入pHead就够了，如下：
QuickSort(pHead);
5、更进一步的研究
上述第3、4节中的快排，在有些情况下还是有点问题的，因为它们的Swap只是交换了节点里面的值，并没有交换整个节点。
在上面快排的逻辑下，要交换整个节点是不现实的，交换整个节点的快排思路是：
1、将单链表的头节点拿出来，作为一个基准节点；
2、遍历此单链表剩下的所有节点，将这些节点归类放到2个单链表中，一个存放所有比基准节点小的节点，另一个存放所有大于等于基准节点的节点；
3、递归处理第二步中的2个链表；
4、将递归处理好的这2个链表（此时已有序）和基准节点，再拼接成一个完整的单链表
6、使用归并排序
虽然快排和归并排序的时间复杂度都是O（nlogn），但是针对单向链表的排序，归并排序速度更快。具体参考https://blog.csdn.net/nirendao/article/details/81047213
更多信息可以查看Leetcode 148. 排序链表
