导航特效网站视频号视频下载助手app
排序算法是数据结构与算法中最基本的算法之一，其作用就是将一些可以比较大小的数据进行有规律的排序，而想要实现这种排序就拥有很多种方法~
那么我将通过几篇文章，将排序算法中各种算法细化的，详尽的为大家呈现出来：
📚 非线性时间比较类：
📕 插入类排序：数据结构与算法之排序算法-插入排序-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)的速度是多么的稳定(内存消耗的多就是了)。
那么这篇关于归并排序的文章到这里就结束啦，作者能力有限，如果有哪里说的不够清楚或者不够准确，还请各位在评论区多多指出，我也会虚心学习的，我们下次再见啦