归并排序就是这么容易

秒速五厘米 2023-10-07 12:42 45阅读 0赞

![format_png][]

愚昧者怨天尤人，无能者长吁短叹，儒弱者颓然放弃。

## 归并排序就是这么容易 ##

welcome rodert

一

#### 归并排序（Merge Sort） ####

排序算法很重要

一

#### 介绍 ####

![format_png 1][]

【百度百科】：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用**分治法**（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路[归并][Link 1]。归并排序是一种稳定的排序方法。

![format_png 2][]

**分治法：**

分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。

分治法的精髓：

分--将问题分解为规模更小的子问题；

治--将这些规模更小的子问题逐个击破；

合--将已解决的子问题合并，最终得出“母”问题的解；

一

#### 实现 ####

**算法描述：**

1.  申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2.  设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3.  比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4.  重复步骤 3 直到某一指针达到序列尾；
5.  将另一序列剩下的所有元素直接复制到合并序列尾。

（看完这个描述是否还不清楚）

**动态图演示：**

![20200416154051122.gif][]

选择排序流程图

图片来源百度

![format_png 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;
        }
    
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzc0NjA0_size_16_color_FFFFFF_t_70][]

一道使用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;
        }
    }

![format_png 4][]

转载是一种动力 分享是一种美德 开源是一种信仰

![format_png 5][]

—END—

rodert

更多文章后面会持续分享，有特别需要可以提前留言。

*welcome*

![20200416154433701.jpg][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZTIuMTM1ZWRpdG9yLmNvbS9jYWNoZS9yZW1vdGUvYUhSMGNITTZMeTl0YldKcGVpNXhiRzluYnk1amJpOXRiV0pwZWw5d2JtY3ZXVlY1V2pkQlQwd3piMnd5VUdKSE5VOW1WRGxyV0dOMVNrSnhaVE5NVUVsV2JXNU5Tak5sTVdKclRuTlpObmxaVURSbE5tSkRhV0pXUkdGeGVteDJhV014WWtSMVZVRkdia0ZqV1cxUVFVVlNiRWR3WW5JeWR5OHc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZTIuMTM1ZWRpdG9yLmNvbS9jYWNoZS9yZW1vdGUvYUhSMGNITTZMeTl0YldKcGVpNXhiRzluYnk1amJpOXRiV0pwZWw5d2JtY3ZOMUZTVkhaclN6SnhRemRSUjJOT1FtaHdla2xCTUhWMU1YQkNRMGxTUzNKRFlucG5VV0V5U1cxb1MwMXhhV0ZGZEhGdE4xZGlVa3ROZEVSdFdHSlVTVUZ4U1hWSFNFRlNUMjl6YlZOaFYxZGhVRTVXWkVWM0x6QS9kM2hmWm0xMFBYQnVadz09?x-oss-process=image/format,png
[Link 1]: https://baike.baidu.com/item/%E5%BD%92%E5%B9%B6/253741
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9iZG4uMTM1ZWRpdG9yLmNvbS9maWxlcy9pbWFnZXMvZWRpdG9yX3N0eWxlcy9jNzBjYWJiNmIwNWYxZmEyZTk2MDE3ZDhlOTgzMzU0Mi5qcGc?x-oss-process=image/format,png
[20200416154051122.gif]: https://img-blog.csdnimg.cn/20200416154051122.gif
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ia2ltZy5jZG4uYmNlYm9zLmNvbS9waWMvYzgxNzdmM2U2NzA5YzkzZDY3M2I5ZWQ0OWQzZGY4ZGNkMDAwNTRjMw?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzc0NjA0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200416154254581.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzc0NjA0,size_16,color_FFFFFF,t_70
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZTIuMTM1ZWRpdG9yLmNvbS9jYWNoZS9yZW1vdGUvYUhSMGNITTZMeTl0YldKcGVpNXhiRzluYnk1amJpOXRiV0pwZWw5d2JtY3ZXVlY1V2pkQlQwd3piMncwT0V0cFkweHRUV2xpVUV0cFlURjJVbkZ0WTBFeVZVdERVM2czUTB0VE9IWXliR1JPZGxCMmJIcG5iV1pwWW01WU1sbFVhV0ZwWVVSVk9WSTVhV00wZWtoUGJHeEpZelJNZGxOU2FXTTFVV1EzWnk4d1AzZDRYMlp0ZEQxd2JtYz0?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZTIuMTM1ZWRpdG9yLmNvbS9jYWNoZS9yZW1vdGUvYUhSMGNITTZMeTl0YldKcGVpNXhiRzluYnk1amJpOXRiV0pwZWw5d2JtY3ZOMUZTVkhaclN6SnhRemRYVDNaeFNucHlXWGhCVGxOelUzTllWMUpGV21OWU9IaHphelppYkdsaU5tNVRXR2hEYUhWR00zSmhaa0Z0UTNOS2Fsb3hjMjA0VkcxaFJsQk9ObkpZVWs5T2RUUXdhV0Z4U1haTWR5OHc?x-oss-process=image/format,png
[20200416154433701.jpg]: https://img-blog.csdnimg.cn/20200416154433701.jpg