用单链表实现快速排序

用单链表实现快速排序

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

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

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

• 如果 j 指向的值大于等于基准数字（如果比基准大，直接跳过）
  
  • j ++
• 如果 j 指向的值小于基准数字，（如果比基准小，交换 i 和 j 位置的值）
  
  • i ++
  • swap(i， j)
  • j ++

以【4，2，5，3，7，9，0，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 代码如下：

import java.util.*;

public class Main{

    // 交换
    public static void swap(LinkedList<Integer> list, int i, int j) {
        int t = list.get(j);
        list.set(j, list.get(i));
        list.set(i, t);
    }


    public static void qsort(LinkedList<Integer> list, int left, int right) {

        if(left < right) {
            int i = left; // 初始化i，为链表第一个元素（最左边的元素）
            int j = i + 1; // 初始化j = i + 1
            int x = list.get(i); // 基准数字

            while(j <= right) { // 大循环条件，j不能超过链表长度

                // 如果 j 指向的值大于等于基准数字（如果比基准大，直接跳过）
                while(j <= right && list.get(j) >= x) j++;

                // 否则，j 指向的值小于基准，则交换
                if(j <= right) {
                    i++; // 交换时，i 首先要向后移动一位
                    swap(list, i, j); // 交换
                    j++; // 随后，j向后移动一位
                }

            } 
            swap(list, left, i); // 最后，交换 i 位置的值和基准元素。一趟排序结束。
            qsort(list, left, i-1);   // 递归排序左边
            qsort(list, i+1, right);  // 递归排序右边
        }
    }


    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList();
        int[] arr = {4,2,5,3,7,9,0,1}; // test case 1
//      int[] arr = {5,4,3,2,1,6,7,9,8,10}; // test case 2
        for(int i = 0; i < arr.length; i++) {
            list.add(arr[i]);
        }
        qsort(list, 0, arr.length-1);
        System.out.println(list.toString());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

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

参考了这篇文章：http://blog.csdn.net/wumuzi520/article/details/8078322
这篇文章写得很详细，本文算是对它的一种补充吧。

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