归并排序

归并排序的主要思想是“分而治之”，可以达到O(nlogn)的时间复杂度。下图引自敬爱的邓俊辉老师和尹霞老师数据结构课程上的课件：

Paste_Image.png

从右边的例子可以看出，归并排序的步骤分为两步，首先对无序向量进行递归的分解，直到每个分组仅剩下一个元素，一个元素肯定是有序的；然后对分解的结果逐步进行有序归并。整个算法思路很清晰。我尝试实现了数组的归并排序以及链表的归并排序，贴出代码：

数组的归并排序

    /*
        数组的归并排序

        @low：   归并排序分解数组过程中的低位；
        @high：  归并排序分解数组过程中的高位；
        @nums：  待排序数组
        @result：存储排序结果的数组
     */
    public void mergeSortForArrays(int low, int high, int[] nums, int[] result){
        // 首先，递归分解数组，直到数组的元组只有一个
        if(low < high){
            int middle = (high + low) >> 1; // middle = (low + high) / 2
            mergeSortForArrays(low , middle , nums , result); //左边归并排序，使得左子序列有序，注意这里nums[middle]可取
            mergeSortForArrays(middle + 1, high , nums , result); //右边归并排序，使得右子序列有序

            // 然后，从少到多进行归并
            mergeForArrys(low , middle , high , nums , result);
        }
    }


    /*
        有序数组的归并算法
        @low：   分解数组过程中的低位；
        @middle：分解数组过程中左边与右边两个数组的分界点；
        @high：  分解数组过程中的高位；
        @nums：  原待排序数组
        @result：存储归并排序结果的数组，最后需要更新到nums数组中。

        其实这里可以不需要result参数，每次在merge的时候新开一个数组即可。但是这样会浪费空间
 */
    public void mergeForArrys(int low , int middle , int high, int[] nums, int[] result){
        System.out.println("merge" + low + " " + middle + " " + high);
        int leftPosi = low; // 左序列的指针
        int rightPosi = middle + 1; // 右序列的指针
        int resultPosi = 0; // 结果数组维护的指针

        // 归并：对于两个数组，分别从第一位开始比较其大小，将小的数存入result中，并将result与小的数所在数组的位置指针++
        while(leftPosi <= middle && rightPosi <= high){
            if(nums[leftPosi] < nums[rightPosi]){
                result[resultPosi++] = nums[leftPosi++];
            }
            else{
                result[resultPosi++] = nums[rightPosi++];
            }
        }

        // 一个数组不能移动后，将另外一个数组的剩余值填充进result
        // 注意这里下面的两个while只有一个会成立
        while(leftPosi <= middle) {
            result[resultPosi++] = nums[leftPosi++];
        }
        while(rightPosi <= high){
            result[resultPosi++] = nums[rightPosi++];
        }

        // 将排序后的值写回原数组
        for(int i = 0;i < resultPosi;i++){
            nums[low + i] = result[i];
        }
    }

链表的归并排序

    /*
        链表的归并排序

        @head：  待排序链表头指针；
        注意这里没有链表长度，用之前解leadCode：删除链表倒数第n个节点的思路，用两个快、慢指针找链表的一半
        快指针需要先走len/2步，再和慢指针同步才能一起到结尾。如果让快、慢指针一起从头出发，则快指针需要一次移动两格
 */
    public ListNode mergeSortForList(ListNode head){
        // 为空或为单个，不用排序直接返回
        if(head == null || head.next == null)
            return head;
        else{

            ListNode fast = head.next;
            ListNode slow = head;

            // fast一次走两步，slow一次走一步
            // fast必须从header.next开始，否则无法处理两个节点的情况
            // 最后从slow.next处断开成两个链表
            while(fast.next != null && fast.next.next != null){
                fast = fast.next.next;
                slow = slow.next;
            }

            // leftHead记录左边链表
            ListNode leftHead = head;
            // rightHead记录右边链表
            ListNode rightHead = slow.next;

            // 断开生成左边链表
            slow.next = null;

            // 继续进行递归拆分
            leftHead = mergeSortForList(head);
            rightHead = mergeSortForList(rightHead);

            // 对新链表进行归并
            return mergeForList(leftHead , rightHead);

        }


    }

    /*
        有序链表的归并算法
        @leftHead： 拆分后左链表头指针；
        @rightHead：拆分后右链表头指针；

        初始两个链表指针leftHead和rightHead都在头部。比较其对应的val值，将值小的接入新的链表，同时移动链表指针
        一个有序链表遍历完成后，需要将另一个链表剩下的元素接入新的链表
    */
    public ListNode mergeForList(ListNode leftHead  , ListNode rightHead){

        // 存储归并后新的有序链表，最后返回newHead.next
        ListNode newHead = new ListNode(-1);
        ListNode tempHead = newHead;

        // 比较val大小，移动链表并更新保存结果的有序链表
        while(leftHead != null && rightHead != null){
            if(leftHead.val < rightHead.val){
                tempHead.next = new ListNode(leftHead.val);
                leftHead = leftHead.next;
                tempHead = tempHead.next;
            }
            else{
                tempHead.next = new ListNode(rightHead.val);
                rightHead = rightHead.next;
                tempHead = tempHead.next;
            }
        }

        // 将未遍历完的链表接入
        if(leftHead == null)
            tempHead.next = rightHead;
        else
            tempHead.next = leftHead;

        // 返回归并后的有序链表
        return newHead.next;

    }