数据结构与算法之排序算法-归并排序

排序算法是数据结构与算法中最基本的算法之一，其作用就是将一些可以比较大小的数据进行有规律的排序，而想要实现这种排序就拥有很多种方法~

那么我将通过几篇文章，将排序算法中各种算法细化的，详尽的为大家呈现出来：

📚 非线性时间比较类：

📕 插入类排序：数据结构与算法之排序算法-插入排序-CSDN博客

📖 直接插入排序

📖 希尔排序

📕 交换类排序：数据结构与算法之排序算法-快速排序(分治)-CSDN博客

📖 冒泡排序

📖 冒泡排序-优化

📖 快速排序(Hoare，挖坑法，前后指针法)

📖 快速排序-优化

📕 选择类排序：数据结构与算法之排序算法-选择排序-CSDN博客

📖 简单选择排序

📖 堆排序

📕 归并类排序：[本篇]

📖 归并排序

📚 线性时间非比较类：

📕 非比较类排序：数据结构与算法之排序算法-(计数,桶,基数排序)-CSDN博客

📖 计数排序

📖 桶排序

📖 基数排序

一、归并排序

稳定性：稳定

时间复杂度：O(n logn)

额外空间复杂度：O(n)

归并排序也是一种在实际应用中比较常用的排序算法，这是因为它的速度和快速排序一样也是O(n logn)，并且相较于快速排序，归并排序还具有稳定性

但唯一的缺点就是归并排序并不是"原地算法"，而是需要开辟一个和原数组一样大小的辅助数组，所以归并排序的额外空间复杂度为O(n)

① 习题引入:合并排序的数组

首先，为什么要使用这题作为习题引入呢？我们先接着上面的话题，研究研究归并排序：

上面我们提到归并排序的时间复杂度为O(n logn)，从这里就不难猜出，归并排序的算法大概也是和快排类似，是一种"不断将数组分为两份"的排序算法，也就是"分治"

归并排序的基本思想：取数组的开始位置为left，结束位置为right，不断对数组取中间下标mid，使数组均匀的被分成两个新数组，并继续对新数组进行如上操作。

直到left == right(数组中只有一个元素)时，我们认为此时这个数组为有序数组，将它向上递归。按照这个思想，我们后续递归回去的数组也都是有序的，而如此便能够提到我们上面说的这道习题了："合并排序的数组"

📚 思路提示：

合并有序的数组想必对大家来说肯定非常简单的~毕竟我们之前在学习"链表"的时候就实现过类似的题目，而"合并有序链表"应该是比"合并有序数组"要更加复杂一点点的。

我们只需要创建一个新的数组 arr ，使他的长度等于两个数组之和，然后遍历两个数组，使用双指针的思想，用cur1遍历 arr1，用cur2遍历arr2，将较小的元素放入arr中，随后移动cur1/cur2。

(最后可能会有一个数组没被加入完，记得处理一下就好)

📖 代码示例：

class Solution {public void merge(int[] A, int m, int[] B, int n) {int[] nums = new int[m + n];int cur1 = 0;int cur2 = 0;int i = 0;while(cur1 < m && cur2 < n){nums[i++] = A[cur1] < B[cur2] ? A[cur1++] : B[cur2++];}while(cur1 < m) nums[i++] = A[cur1++];while(cur2 < n) nums[i++] = B[cur2++];for(i = 0;i < n + m;i++){A[i] = nums[i];}}
}

② 归并排序

而上面我们又提到了，将有序的数组向上递归，排序后再递归，这样多此递归下来，我们就能够得到我们想要的"有序数组"。

这样就正好验证了，归并排序的排序速度与其中数组的有序性并没有关系，也就是说它是稳定的O(n logn)的排序~

⭐ 图示：

📖 代码示例：

    public static int[] arr;public int[] sortArray(int[] nums) {arr = new int[nums.length];mergeSort(nums, 0, nums.length - 1);return nums;}public static void mergeSort(int[] array, int left, int right) {if (left >= right) {return;}int mid = left + (right - left) / 2;mergeSort(array, left, mid);mergeSort(array, mid + 1, right);int cur1 = left;int cur2 = mid + 1;int i = 0;while (cur1 <= mid && cur2 <= right) {arr[i++] = array[cur1] < array[cur2] ? array[cur1++] : array[cur2++];}while (cur1 <= mid) {arr[i++] = array[cur1++];}while (cur2 <= right) {arr[i++] = array[cur2++];}for (i = left; i <= right; i++) {array[i] = arr[i - left];}}

那么上次我们学习的"快速排序优化版"能跑多少ms呢？能跑到 30多ms~：

而归并排序跑了 28ms，再一次证明了它O(n logn)的速度是多么的稳定(内存消耗的多就是了)。

那么这篇关于归并排序的文章到这里就结束啦，作者能力有限，如果有哪里说的不够清楚或者不够准确，还请各位在评论区多多指出，我也会虚心学习的，我们下次再见啦