[数据结构与算法]【算法题】单链表快速排序

Java实现单链表的快速排序和归并排序 - morethink - 博客园

在一般实现的快速排序中，我们通过首尾指针来对元素进行切分，下面采用快排的另一种方法来对元素进行切分。

我们只需要两个指针p1和p2，这两个指针均往next方向移动，移动的过程中保持p1之前的key都小于选定的key，p1和p2之间的key都大于选定的key，那么当p2走到末尾时交换p1与key值便完成了一次切分。

图示如下：

public class Test23 {

    public static void main(String[] args) {
        LinkNode node0 = new LinkNode(0, null);
        LinkNode node1 = new LinkNode(1, node0);
        LinkNode node2 = new LinkNode(2, node1);
        LinkNode node3 = new LinkNode(3, node2);

        quickSort(node3);
    }


    public static LinkNode partition(LinkNode start, LinkNode end) {
        LinkNode flag = start, pre = start, next = start;

        while (next != end) {
            if (next.val < flag.val) {
                pre = pre.next;
                swap(pre, next);
            }
            next = next.next;
        }
        swap(pre, flag);
        return pre;
    }

    public static void sort(LinkNode start, LinkNode end) {
        if (start == end) {
            return;
        }
        LinkNode mid = partition(start, end);
        sort(start, mid);
        sort(mid.next, end);
    }

    public static void quickSort(LinkNode link) {
        if (link == null || link.next == null) {
            return;
        }
        LinkNode start = link;
        LinkNode end = null;
        sort(start, end);
    }

    public static void swap(LinkNode a, LinkNode b) {
        int temp = a.val;
        a.val = b.val;
        b.val = temp;
    }
}

class LinkNode {
    int val;
    LinkNode next;

    public LinkNode(int val, LinkNode next) {
        this.val = val;
        this.next = next;
    }
}