目录
前言
归并排序算法是必须掌握的一种基础算法，在一些比较出名的竞赛acm、蓝桥杯，并且在一些公司面试题中都可能会出现，而且作为简单题我们必须要拿下，所以我们要引起重视，下面让我们来深入了解归并排序算法。
一、什么是归并排序
归并排序（Merge Sort）是一种经典的分治算法，它采用分治法将一个数组分成若干个子数组，分别对每个子数组进行排序，然后再将已排序的子数组合并成一个完整的排序数组。归并排序的时间复杂度为 O(nlogn)，且它是一个稳定的排序算法。
二、归并排序步骤
1.分解：将数组从中间分成两半，分别对左半部分和右半部分进行归并排序。
2.递归：递归地对每一半进行分解，直到每个子数组只有一个元素（自然是有序的）。
3.合并：将两个有序的子数组合并成一个有序的数组。
三、算法思想
对于一个非有序的序列，可以拆成两个非有序的序列，然后分别调用归并排序，然后对两个有序的序列再执行合并的过程。所以这里的“归”其实是递归，“并”就是合并。
整个算法的执行过程用mergeSort(a[], l, r) 描述，代表 当前待排序数组a，左区间下标l，右区间下标r，分以下几步：
第一步、计算中点mid=(l+r)/2；
第二步、递归调用mergeSort(a[], l, mid)和mergeSort(a[], mid+1, r)；
第三步、第二步中两个有序数组进行有序合并，再存储到 a[l:r]；
调用时，调用mergeSort(a[], 0, n-1)就能得到整个数组的排序结果了。
四、归并排序复杂度分析
时间复杂度：
分解步骤的时间复杂度为 O(logn)，因为数组被反复分成两半。
合并步骤的时间复杂度为 O(n)，因为需要遍历两个子数组来合并它们。因此，总的时间复杂度为 O(nlogn)。
空间复杂度：
合并步骤需要一个额外的数组来存储合并后的结果，所以空间复杂度为 O(n)。
归并排序是一个相对简单且高效的排序算法，适用于大多数需要稳定排序的场景。
五、优化方案
归并排序在众多排序算法中效率较高，时间复杂度为0(nlog2n)。但是，由于归并排序在归并过程中需要额外的一个辅助数组，所以申请辅助数组内存空间带来的时间消耗会比较大，比较好的做法是，实现用一个和给定元素个数一样大的数组，作为函数传参传进去，所有的辅助数组干的事情，都可以在这个传参进去的数组上进行操作，这样就免去了内存的频繁申请和释放。
六、算法图解
七、c++代码模板
#include <iostream>
#include <vector>
// 合并两个有序的子数组
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// 创建临时数组
std::vector<int> L(n1), R(n2);
// 拷贝数据到临时数组L[]和R[]
for (int i = 0; i < n1; ++i)
L[i] = arr[left + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[mid + 1 + j];
// 合并临时数组回到arr[left..right]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
++i;
} else {
arr[k] = R[j];
++j;
}
++k;
}
// 拷贝L[]的剩余元素（如果有）
while (i < n1) {
arr[k] = L[i];
++i;
++k;
}
// 拷贝R[]的剩余元素（如果有）
while (j < n2) {
arr[k] = R[j];
++j;
++k;
}
}
// 归并排序的主函数
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// 递归排序两个子数组
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// 合并已排序的子数组
merge(arr, left, mid, right);
}
}
// 打印数组
void printArray(const std::vector<int>& arr) {
for (int num : arr)
std::cout << num << " ";
std::cout << std::endl;
}
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
int arr_size = arr.size();
std::cout << "Given array is \n";
printArray(arr);
mergeSort(arr, 0, arr_size - 1);
std::cout << "\nSorted array is \n";
printArray(arr);
return 0;
}
八、经典例题
1.排序数组
（帅哥们这个蓝色字体可以点进去看原题）
代码题解
class Solution {
void merge(vector<int>&a,int l,int m,int r){
int n1=m-l+1;//左部分元素个数
int n2=r-m;//右部分元素个数
int t[n1+n2];
for(int i=0;i<n1;i++){
t[i]=a[i+l];
}
for(int j=0;j<n2;j++){
t[n1+j]=a[m+1+j];
}
int i=0,j=n1,k=l;
while(i<n1&&j<n1+n2){
if(t[i]<=t[j]){
a[k++]=t[i++];
}
else a[k++]=t[j++];
}
while(i<n1){
a[k++]=t[i++];
}
while(j<n1+n2){
a[k++]=t[j++];
}
}
void mergeSort(vector<int>&a,int l,int r){
if(l>=r)return ;
int m=(l+r)/2;//中点下标为m
mergeSort(a,l,m);//将左半部分排好序
mergeSort(a,m+1,r);//将右半部分排好序
merge(a,l,m,r);//合并两个部分
}
public:
vector<int> sortArray(vector<int>& a) {
mergeSort(a,0,a.size()-1);
return a;
}
};
2.排序链表
（帅哥们这个蓝色字体可以点进去看原题）
代码题解
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
ListNode* mergeSort(ListNode*a,ListNode*b){
a=sortList(a);
b=sortList(b);
ListNode*head=new ListNode();
ListNode*tail=head;
while(a||b){
if(!a){
tail->next=b;
break;
}
else if(!b){
tail->next=a;
break;
}
else if(a->val<b->val){
tail->next=a;
a=a->next;
}
else{
tail->next=b;
b=b->next;
}
tail=tail->next;
tail->next=NULL;
}
return head->next;
}
public:
ListNode* sortList(ListNode* head) {
if(!head)return NULL;
else if(head->next==NULL)return head;
ListNode*fast=head;
ListNode*slow=head;
ListNode*pre=NULL;
while(fast){
pre=slow;
slow=slow->next;
fast=fast->next;
if(fast)fast=fast->next;
}
pre->next=NULL;
return mergeSort(head,slow);
}
};
九、结语
学习算法是一个很艰难，漫长的过程，我们要克服一切困难，学习算法本就是由易到难，我相信通过我们坚持不懈的努力一定能理解并熟练掌握其中细节，加油。
关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家
