愚昧者怨天尤人，无能者长吁短叹，儒弱者颓然放弃。
归并排序就是这么容易
welcome rodert
一
归并排序（Merge Sort）
排序算法很重要
一
介绍
【百度百科】：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。
分治法：
分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。
分治法的精髓：
分--将问题分解为规模更小的子问题；
治--将这些规模更小的子问题逐个击破；
合--将已解决的子问题合并，最终得出“母”问题的解；
一
实现
算法描述：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤 3 直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾。
（看完这个描述是否还不清楚）
动态图演示：
选择排序流程图
图片来源百度
Java代码实现
public static int[] mergeSort(int[] nums, int l, int h) { if (l == h) return new int[] { nums[l] }; int mid = l + (h - l) / 2; int[] leftArr = mergeSort(nums, l, mid); //左有序数组 int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组 int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组 int m = 0, i = 0, j = 0; while (i < leftArr.length && j < rightArr.length) { newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++]; } while (i < leftArr.length) newNum[m++] = leftArr[i++]; while (j < rightArr.length) newNum[m++] = rightArr[j++]; return newNum; } public static void main(String[] args) { int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 }; int[] newNums = mergeSort(nums, 0, nums.length - 1); for (int x : newNums) { System.out.println(x); } }
类似方法二：
public class MergeSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); if (arr.length < 2) { return arr; } int middle = (int) Math.floor(arr.length / 2); int[] left = Arrays.copyOfRange(arr, 0, middle); int[] right = Arrays.copyOfRange(arr, middle, arr.length); return merge(sort(left), sort(right)); } protected int[] merge(int[] left, int[] right) { int[] result = new int[left.length + right.length]; int i = 0; while (left.length > 0 && right.length > 0) { if (left[0] <= right[0]) { result[i++] = left[0]; left = Arrays.copyOfRange(left, 1, left.length); } else { result[i++] = right[0]; right = Arrays.copyOfRange(right, 1, right.length); } } while (left.length > 0) { result[i++] = left[0]; left = Arrays.copyOfRange(left, 1, left.length); } while (right.length > 0) { result[i++] = right[0]; right = Arrays.copyOfRange(right, 1, right.length); } return result; } }
一道使用leetcode题
148. 排序链表 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 示例 1: 输入: 4->2->1->3 输出: 1->2->3->4 示例 2: 输入: -1->5->3->4->0 输出: -1->0->3->4->5 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode sortList(ListNode head) { } }
题解：
class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; ListNode fast = head.next, slow = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode tmp = slow.next; slow.next = null; ListNode left = sortList(head); ListNode right = sortList(tmp); ListNode h = new ListNode(0); ListNode res = h; while (left != null && right != null) { if (left.val < right.val) { h.next = left; left = left.next; } else { h.next = right; right = right.next; } h = h.next; } h.next = left != null ? left : right; return res.next; } }
转载是一种动力 分享是一种美德 开源是一种信仰
