算法

单链表快排
快排最核心的思想就是划分，确定一个枢轴元素(pivot)，每一趟划分的目的就是把待排序列分为两部分，前一部分比枢轴小(序列A)，后一部分比枢轴大(序列B)。经过一趟划分之后序列变为：{A} pivot {B}。以下是具体步骤：
1、确定每一次划分的枢轴元素为当前待排序列的头节点。
2、设置Slow和Fast两个游标，Slow指向序列A中的最后一个元素，初始化为枢轴本身(待排序列头节点)。让Fast遍历一遍待排序列，当所指元素比枢轴小时，将Slow往前游一格，交换Slow和Fast所指元素的值，这样仍能保证Slow指向的元素是序列A中的最后一个元素。
3、交换Slow所指元素和枢轴元素的值。
4、对序列A和B重复步骤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) {
            //以各部分第一个元素为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小的最后一个元素
        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之后,则交换两个元素的值
            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 + ", ";
        }
    }

}