算法-归并排序

基本思想

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

归并排序

合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

合并
合并

代码实现

import java.util.Arrays;
public class Main {

  public static void main(String[] args) {
    int[] nums = {8, 4, 5, 7, 1, 3, 6, 2};
    mergesort(nums, 0, nums.length - 1);
    System.out.println(Arrays.toString(nums));
  }

  private static void mergesort(int[] array, int left, int right) {
    int mid = (left + right) / 2; // 默认向下取整,
    if (left < right) {
      mergesort(array, left, mid); //左边归并排序，使得左子序列有序
      mergesort(array, mid + 1, right); //右边归并排序，使得右子序列有序
      merge(array, left, mid, right); //将两个有序子数组合并操作
    }
  }

  // 排序核心
  private static void merge(int[] array, int left, int mid, int right) {
    int leftIndex = left; //左序列指针
    int rightIndex = mid + 1; //右序列指针

    //针对一个临时数组
    int temp[] = new int[right - left + 1]; //存放分治排列之后的内容
    int tempindex = 0; //临时数组索引指针

    // 这里理解为两个单元合并排序, 也就是,左边一个数组, 右边一个数组
    // leftIndex <= mid 左边一个数组的范围  ,   rightIndex <= right 右边一个数组的范围
    // 比较并且依次放入一个临时数组temp中
    while (leftIndex <= mid && rightIndex <= right) {
      if (array[leftIndex] <= array[rightIndex]) {
        temp[tempindex++] = array[leftIndex++];
      } else {
        temp[tempindex++] = array[rightIndex++];
      }
    }

    //如果上面全部排序完毕, 这里相当于, 右半部分搞定了, 左边的内容全部往临时数组中填满
    while (leftIndex <= mid) {
      temp[tempindex++] = array[leftIndex++];
    }

    //如果上面全部排序完毕, 这里相当于, 左半部分搞定了, 右边的内容全部往临时数组中填满
    while (rightIndex <= right) {
      temp[tempindex++] = array[rightIndex++];
    }

    //最后将temp中的元素全部覆盖到原数组中
    for (int i = 0; i < tempindex; i++) {
      array[left + i] = temp[I];
    }
  }
}

输出结果

[1, 2, 3, 4, 5, 6, 7, 8]

快速整理思路

快速整理思路

从代码角度理解总结

• 6个不同的指针(left, mid, right , leftIndex, rightIndex, tempIndex) 的作用和临时数组(temp)的作用
• 分治过程的处理

最后

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

排序算法	平均时间复杂度	最好	最坏	空间复杂度	稳定性
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定

---

---

---

变形

合并K个升序链表

示例1:

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

有点类似于归并排序, 多个有序的(链表拆分成数组)数组合并成一个, 假设现在不考虑最优解, 最合适的解法, 我们就用归并排序来实践一下. 这里主要想沿用上面的操作数组的方式.

PS : 应该用两两链表合并的操作方式原地合并是比较好的.

package com.company;

class ListNode {
  int val;
  ListNode next;

  ListNode() {}

  ListNode(int val) {
    this.val = val;
  }

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

public class Main {

  public static void main(String[] args) {
    //创建链表
    ListNode list1 = new ListNode(1, new ListNode(4, new ListNode(5, null)));
    ListNode list2 = new ListNode(1, new ListNode(3, new ListNode(4, null)));
    ListNode list3 = new ListNode(2, new ListNode(6));
    ListNode list4 = new ListNode();
    ListNode list5 = new ListNode(1);
    System.out.println(list4.val);
    ListNode[] list = {list1,list2,list3,list4, list5};
    mergeKLists(list);
  }

  public static ListNode mergeKLists(ListNode[] lists) {

    //将多个升序链表凭接为一个长的链表
    int listSize = 0;
    ListNode newHeadNode = null;//新的头结点
    ListNode lastNode = null;//最后一个节点,通过最后一个节点拼接其他链表的节点.
    for (int i = 0; i < lists.length; i++) {
      ListNode list = lists[I];
      if (list != null) {
        if (i == 0) {
          newHeadNode = list;
        }
        if (lastNode != null) {
          lastNode.next = list;
        }
        while (list != null) {
          listSize++;
          lastNode = list;
          list = list.next;
        }
      }
    }

    //把所有的node节点放入在temp数组中, 待进行归并排序
    int tempIndex = 0;
    ListNode[] temp = new ListNode[listSize];
    while (newHeadNode != null) {
      temp[tempIndex++] = newHeadNode;
      newHeadNode = newHeadNode.next;
    }

    //排序前清空所有next
    for (int i = 0; i < temp.length; i++) {
      if (temp[i] != null) {
        temp[i].next = null;
      }
    }

    //归并排序
    mergesort(temp, 0, listSize - 1);

    //排序后拼接所有node节点
    ListNode newHead = pickupList(temp);

    //最后一波打印查看结果
    while (newHead != null) {
      System.out.println("newHead : " + newHead.val + " " + "current : " + newHead + "  " + "Next : " + newHead.next);
      newHead = newHead.next;
    }
    return pickupList(temp);
  } ;


  //重新拼接
  private static ListNode pickupList(ListNode[] arr) {
    ListNode newHead = null;
    ListNode newHeadIndex = null;
    for (int i = 0; i < arr.length; i++) {
      if (newHeadIndex == null) {
        newHead = arr[i];
        newHeadIndex = newHead;
      } else {
        newHeadIndex.next = arr[i];
        newHeadIndex = newHeadIndex.next;
      }
    }
    return newHead;
  }


  private static void mergesort(ListNode[] array, int left, int right) {
    int mid = (left + right) / 2;
    if (left < right) {
      mergesort(array, left, mid);
      mergesort(array, mid + 1, right);
      merge(array, left, mid, right);
    }
  }

  // 排序核心
  private static void merge(ListNode[] array, int left, int mid, int right) {
    int leftIndex = left;
    int rightIndex = mid + 1;

    ListNode temp[] = new ListNode[right - left + 1];
    int tempindex = 0;

    while (leftIndex <= mid && rightIndex <= right) {
      if (array[leftIndex].val <= array[rightIndex].val) {
        temp[tempindex++] = array[leftIndex++];
      } else {
        temp[tempindex++] = array[rightIndex++];
      }
    }

    while (leftIndex <= mid) {
      temp[tempindex++] = array[leftIndex++];
    }

    while (rightIndex <= right) {
      temp[tempindex++] = array[rightIndex++];
    }

    for (int i = 0; i < tempindex; i++) {
      array[left + i] = temp[I];
    }
  }
}

打印结果

newHead : 0 current : com.company.ListNode@629f0666  Next : com.company.ListNode@2d6a9952
newHead : 1 current : com.company.ListNode@2d6a9952  Next : com.company.ListNode@22a71081
newHead : 1 current : com.company.ListNode@22a71081  Next : com.company.ListNode@1bc6a36e
newHead : 1 current : com.company.ListNode@1bc6a36e  Next : com.company.ListNode@3930015a
newHead : 2 current : com.company.ListNode@3930015a  Next : com.company.ListNode@2f7a2457
newHead : 3 current : com.company.ListNode@2f7a2457  Next : com.company.ListNode@566776ad
newHead : 4 current : com.company.ListNode@566776ad  Next : com.company.ListNode@6108b2d7
newHead : 4 current : com.company.ListNode@6108b2d7  Next : com.company.ListNode@1554909b
newHead : 5 current : com.company.ListNode@1554909b  Next : com.company.ListNode@6bf256fa
newHead : 6 current : com.company.ListNode@6bf256fa  Next : null

从结果来看, 最后的链表结构应该是

[0->1->1->1->2->3->4->4->5->6]

从实际结果来看, 执行的结果是正常的.

LeetCode执行效果

正常执行结果

---

---

在LeetCode上没有解释 lists = [], 这里面的[]没有解释具体的, 按照示例1来判断, 应该是一个空节点, 或者是空链表.

试过创建一个新的节点val=0, next=null, 也就是直接调用ListNode() {}方法.或者直接设置 ListNode list = null;这种方式来添加到链表数组中. 好像都有些小问题.

错误结果

待优化吧.