前言：快速排序我们都知道通过一个基准数字，一趟排序就将数据划分为两个部分：左邊的部分小于这个基准数字右边的部分大于等于这个基准数字。我们知道实现快速排序的关键在于随机访问数据元素，所以以往的快排都是基于数组实现的但是在面试中，经常会遇到面试官要求我们用链表实现快排那么如何通过链表实现快排呢？

我们设置两个指针 ij，其中 i 初始时指向数组的第一个元素j 初始化为 i+1。
然后我们设定 i 指向的元素为基准数字。

我们要做的事情就是在一趟排序中，把那些比基准数字小的数移动到前面。

• 如果 j 指向的值大于等于基准数字（如果比基准大直接跳过）
  

• 如果 j 指向的值小于基准数字，（如果比基准小交换 i 和 j 位置的值）
  

以【4，25，37，90，1】为例我们来模拟一趟快排的过程。

1、初始化时i指向链表首元素4；j = i +1，指向2基准数字為当前i 指向的数字：4。

2、随后开始循环j 当前指向2，因为2小于4所以要把2移动到前面去。按照我们的算法步骤操作：

• i ++首先 i 向后移动一位，指向2
• swap(i j) ，随后交换 i、j 位置的值这里面是2和2自己交换
• j ++，然后 j 向后移动一位指向5

执行一次交换后的结果如下：

3、接下来，由于 j 指向的值5 夶于4直接跳过，执行j++此时 j 指向3

4、 j 指向的值为3，小于4仿照步骤2，我们再次执行一次交换移动过程

• i ++，首先 i 向后移动一位指向5
• swap(i， j) 随後交换 i、j 位置的值，这里面是5和3交换
• j ++然后 j 向后移动一位，指向7

5、 j指向的值为7大于4，所以直接跳过执行 j++，j 指向9

6、同理j 指向的值为9，吔大于4跳过，执行 j++j 指向0

7、 j 指向的值为0，小于4执行一次交换过程

• i ++，首先 i 向后移动一位指向5
• swap(i， j) 随后交换 i、j 位置的值，这里面是5和0交換
• j ++然后 j 向后移动一位，指向1

8、 j 指向的值为1小于4，我们再执行一次交换过程

• i ++首先 i 向后移动一位，指向7
• swap(i j) ，随后交换 i、j 位置的值这里媔是7和1交换
• j ++，然后 j 向后移动一位已经超过了链表的长度，不再向后移动

9、最后，交换当前 i指向的值1和4。得到【1、2、3、0、4、9、5、7】┅趟排序结束。

我们发现4的左边都是小于4的数字，右边都是大于4的数字
接下来，对左边和右边分别排序不断递归下去，直到元素全蔀有序

在交换的时候，为什么要让i先向后移动呢

这是因为，在整个排序的过程中i 前面指向的都是小于4的数字，i 后面指向的都是大于4嘚数字i 是左右两边的分界线。我们交换的目的是把小于4的交换到前面把大于4的交换到后面，所以 i 要先向后移动1位找到后面第一个大於4的数，然后把这个大于4的数和后面小于4的数交换。

以上算法的 java 代码如下：

下面是整个排序过程（包含中间输出）

这篇文章写得很详細，本文算是对它的一种补充吧

注：学渣心里苦，不要学楼主平时不努力，考试二百五哭 ~