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. 排序链表

单向链表的快速排序