排序

未数据结构

Sort a linked list in O(n log n) time using constant space complexity.

归并排序

因为题目要求复杂度为O(nlogn),故可以考虑归并排序的思想。
数组存储的归并排序 时间复杂度O（nlogn）空间复杂度 O（n）
链表存储的归并排序 时间复杂度O（nlogn）空间复杂度 $O(log_2N)$,因为使用了递归
归并排序的一般步骤为：
1. 将待排序数组（链表）取中点并一分为二；
2. 递归地对左半部分进行归并排序；
3. 递归地对右半部分进行归并排序；
4. 将两个半部分进行合并（merge）,得到结果。

1）找到链表中点 （快慢指针思路，快指针一次走两步，慢指针一次走一步，快指针在链表末尾时，慢指针恰好在链表中点）；
2）写出merge函数，即如何合并链表。
3）写出mergesort函数，实现上述步骤。

class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val =x;
        next = null;
    }
}
public class TestSort {
    public static ListNode sort(ListNode head){
        if (head == null || head.next == null)
            return head;
        ListNode mid = getMiddle(head); //获取中间结点
        //断开
        ListNode midNext = mid.next;
        mid.next = null;
        //排序，合并
        return mergeTwoLists(sort(head), sort(midNext));//递归
        }
    /**
     * 获取链表的中间结点,偶数时取中间第一个
     * @param head
     * @return
     */
    public static ListNode getMiddle(ListNode head){
        if (head == null || head.next == null)  //空或只有一个
            return head;
        ListNode fast, slow;    //快慢指针
        fast = slow = head;
        //快2步，慢一步
        while (fast.next != null && fast.next.next != null) {
            //偶数时取第一个
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    /**
     * 实现合并两个已经排序的链表
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //特殊情况
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;
        //first、second分别指向第一第二条链表的第一个节点
        ListNode first = l1.next, second = l2.next;
        // newHead合并链表的头引用
        ListNode res, newHead;   //结果
        if (l1.val < l2.val){
            newHead = res = l1;
            second = l2;
        }else {
            newHead = res = l2;
            first = l1;
        }
        while (first != null || second != null){
            if (first == null){             //第一条链表没了
                res.next = second;
                return newHead;
            }
            else if (second == null) {    //第二条链表空了
                res.next = first;
                return newHead;
            } else if (first.val < second.val){ //第一个值小
                res.next = first;
                first = first.next;
                res = res.next;
            } else {
                res.next = second;
                second = second.next;
                res = res.next;
            }
        }
        return newHead;
    }

快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

/**
     * 快速排序
     * 平均复杂度：O(nlogn)
     * 最坏情况：O(n^2)
     * 辅助空间：O(logn)~O(n)
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        quickSort(head, null);
        return head;
    }
    /**
     * 划分为两部分，一部分比另一部分小，再分别对两部分递归排序
     * @param head
     * @param end
     */
    public static void quickSort(ListNode head, ListNode end) {
        if(head != end) {
            ListNode partion = partion(head);
            quickSort(head, partion);
            quickSort(partion.next, end);
        }
    }
    /**
     * 选取一个关键字，然后把它放到一个位置，使得它左边的值比它小，右边的值比它大
     * @param head
     * @return
     */
    public static ListNode partion(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null) {
            if(fast.val < head.val) {   //小于枢纽值则换到前面
                slow = slow.next;
                fast.val = slow.val ^ fast.val ^ (slow.val = fast.val); //交换两个节点的值，括号得放后面
            }
            fast = fast.next;           //逐步往后遍历
        }
        slow.val = head.val ^ slow.val ^ (head.val = slow.val);     //交换两个节点的值，将枢纽值放到中间位置
        return slow;
    }

插入排序

插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。