单链表的快速排序

一般情况下快速排序采用的数据结构是数组，数组可以随机存取，如果采用单链表，由于只有一个头节点，所以和数组的快速排序有一些不一样的地方，主要还是切分的方法不同。在单链表的快速排序中，可以使用两个指针，p和q，p和q开始时都在子数组的开头，其中p=start，q=p.next。同样地，选择start节点的数值作为切分元素，需要满足以下条件：

1. start和指针p之间的元素值要小于切分元素
2. p和q之间的元素值要大于切分元素
3. q和end之间的元素还未确定
4. 当q循环到end的时候结束此子链表的循环，把指针p和指针start的元素值进行交换

代码如下：

package chapter2;

import java.util.Random;

/**
 * Created by jia on 17-5-17.
 */
public class QuickList {
    class Node {
        int val;
        Node next;
    }

    Node head;
    int length;

    public QuickList() {
         head = new Node();
         head.next = null;
         length = 0;
    }

    public void add(int val) {
        Node newNode = new Node();
        newNode.val = val;
        newNode.next = head.next;
        head.next = newNode;
        length++;
    }

    private void swap(Node i, Node j) {
        //只交换两个节点的值，并不是直接交换两个节点
        if (i == j) return;
        int temp = i.val;
        i.val = j.val;
        j.val = temp;
    }

    private Node partition(Node start, Node end) {
        int v = start.val;
        Node p = start;
        Node q = p.next;
        while (q != end) {
            //当发现q节点的值小于v的时候，将指针p向右循环一位，并交换p和q节点的值
            if (q.val < v) {
                p = p.next;
                swap(p, q);
            }
            //q向右循环一位，直至遇到end节点
            q = q.next;
        }
        //结束循环后说明已经将start和end之间的节点按照大小划分，其中节点p及p之前的元素除了start节点外都是小于v的，
        // 此时需要做的只是把作为枢轴的start节点和p节点交换
        swap(p, start);
        return p;
    }

    public void sort() {
        sort(head.next, null);
    }

    public void sort(Node start, Node end) {
        if (start == end) return;

        Node j = partition(start, end);
        sort(start, j);
        sort(j.next, end);
    }

    public int[] toArray() {
        int[] a = new int[length];
        Node current = head;
        for (int i = 0; i < length; i++) {
            a[i] = current.next.val;
            current = current.next;
        }
        return a;
    }

    public static void main(String[] args) {
        Random random = new Random();
        QuickList list = new QuickList();
        for (int i = 0; i < 100; i++) {
            int t = random.nextInt(10);
            System.out.println(t);
            list.add(t);
        }
        ArrayPrint.print(list.toArray());
        list.sort();
        ArrayPrint.print(list.toArray());
    }
}
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93