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

排序算法是数据结构与算法中最根本的算法之一，其作用就是将一些可以比力巨细的数据举行有规律的排序，而想要实现这种排序就拥有许多种方法~
那么我将通过几篇文章，将排序算法中各种算法细化的，细致的为各人出现出来：
📚 非线性时间比力类：
   📕 插入类排序：数据结构与算法之排序算法-插入排序-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。
(末了大概会有一个数组没被参加完，记得处置处罚一下就好)
📖 代码示例：

1. class Solution {
2.     public void merge(int[] A, int m, int[] B, int n) {
3.         int[] nums = new int[m + n];
4.         int cur1 = 0;
5.         int cur2 = 0;
6.         int i = 0;
7.         while(cur1 < m && cur2 < n){
8.             nums[i++] = A[cur1] < B[cur2] ? A[cur1++] : B[cur2++];
9.         }
10.         while(cur1 < m) nums[i++] = A[cur1++];
11.         while(cur2 < n) nums[i++] = B[cur2++];
12.         for(i = 0;i < n + m;i++){
13.             A[i] = nums[i];
14.         }
15.     }
16. }

复制代码

② 归并排序

而上面我们又提到了，将有序的数组向上递归，排序后再递归，如许多此递归下来，我们就可以大概得到我们想要的"有序数组"。
如许就恰恰验证了，归并排序的排序速率与此中数组的有序性并没有关系，也就是说它是稳固的O(n logn)的排序~
⭐ 图示：

📖 代码示例：

1.     public static int[] arr;
2.     public int[] sortArray(int[] nums) {
3.         arr = new int[nums.length];
4.         mergeSort(nums, 0, nums.length - 1);
5.         return nums;
6.     }
7.     public static void mergeSort(int[] array, int left, int right) {
8.         if (left >= right) {
9.             return;
10.         }
11.         int mid = left + (right - left) / 2;
12.         mergeSort(array, left, mid);
13.         mergeSort(array, mid + 1, right);
14.         int cur1 = left;
15.         int cur2 = mid + 1;
16.         int i = 0;
17.         while (cur1 <= mid && cur2 <= right) {
18.             arr[i++] = array[cur1] < array[cur2] ? array[cur1++] : array[cur2++];
19.         }
20.         while (cur1 <= mid) {
21.             arr[i++] = array[cur1++];
22.         }
23.         while (cur2 <= right) {
24.             arr[i++] = array[cur2++];
25.         }
26.         for (i = left; i <= right; i++) {
27.             array[i] = arr[i - left];
28.         }
29.     }

复制代码

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

而归并排序跑了 28ms，再一次证明白它O(n logn)的速率是多么的稳固(内存斲丧的多就是了)。
那么这篇关于归并排序的文章到这里就竣事啦，作者本领有限，如果有那边说的不敷清楚大概不敷准确，还请各位在批评区多多指出，我也会客气学习的，我们下次再见啦

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。