單鏈表快排
快排最核心的思想就是劃分，確定一個(gè)樞軸元素(pivot)恋腕，每一趟劃分的目的就是把待排序列分為兩部分，前一部分比樞軸小(序列A)荠藤，后一部分比樞軸大(序列B)。經(jīng)過一趟劃分之后序列變?yōu)椋簕A} pivot {B}吻育。以下是具體步驟：
1淤井、確定每一次劃分的樞軸元素為當(dāng)前待排序列的頭節(jié)點(diǎn)。
2游两、設(shè)置Slow和Fast兩個(gè)游標(biāo)，Slow指向序列A中的最后一個(gè)元素贱案，初始化為樞軸本身(待排序列頭節(jié)點(diǎn))止吐。讓Fast遍歷一遍待排序列碍扔，當(dāng)所指元素比樞軸小時(shí)，將Slow往前游一格厉膀，交換Slow和Fast所指元素的值，這樣仍能保證Slow指向的元素是序列A中的最后一個(gè)元素汰具。
3菱魔、交換Slow所指元素和樞軸元素的值。
4澜倦、對序列A和B重復(fù)步驟1～4藻治。

package leetcode.sort;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

/**
 * 單鏈表快排
 * Created by blank on 2015-11-03 下午8:42.
 */
public class ListQuickSort {

    public static final int R = 50;

    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(new FileInputStream("/Users/blank/IdeaProjects/LeetCode/src/main/java/leetcode/sort/input.in"));
        int[] arr = new int[R];
        for (int i = 0; i < R; i++) {
            arr[i] = new Random().nextInt(100);
        }
        System.out.println(Arrays.toString(arr));
        ListNode head = new ListNode(0);
        ListNode p = head;
        for (int i = 0; i < arr.length; i++) {
            ListNode node = new ListNode(arr[i]);
            p.next = node;
            p = p.next;
        }
        quickSort(head.next, null);
        head = head.next;
        while (head != null) {
            System.out.print(head);
            head = head.next;
        }
    }

    public static void quickSort(ListNode head, ListNode tail) {
        if (head != tail) {
            //以各部分第一個(gè)元素為pivot元素,然后劃分左右
            ListNode pr = sort(head, tail);
            quickSort(head, pr);
            quickSort(pr.next, tail);
        }
    }

    private static ListNode sort(ListNode head, ListNode tail) {
        if (head == tail) {
            return head;
        }
        int val = head.val;
        ListNode slow = head.next;
        //用pre記錄比pivot小的最后一個(gè)元素
        ListNode pre = head;
        ListNode fast;
        while (true) {
            //slow表示比pivot元素大的元素
            while (slow != tail && slow.val < val) {
                pre = slow;
                slow = slow.next;
            }
            if (slow == tail) {
                break;
            }
            //fast表示比pivot元素小的元素
            fast = slow.next;
            while (fast != tail && fast.val > val) {
                fast = fast.next;
            }
            if (fast == tail) {
                break;
            }
            //如果存在fast在slow之后,則交換兩個(gè)元素的值
            swap(slow, fast);
            pre = slow;
            slow = slow.next;
        }
        //交換pivot和pre
        swap(head, pre);
        return pre;
    }

    private static void swap(ListNode one, ListNode two) {
        int tmp = one.val;
        one.val = two.val;
        two.val = tmp;
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return val + ", ";
        }
    }

}