HzuQZH

用户名：h1810819001

访问量：32318

签　名：

等　　级
排　　名	45
经　　验	12276
参赛次数	7
文章发表	69
年　　龄	0
在职情况	学生
学　　校	贺州学院
专　　业

　　自我简介：

TA的其他文章

数据结构-KMP字符串模式匹配算法实现-题解(C++代码)
浏览：504

数据结构-用数组实现堆排（易处理，容易理解）
浏览：634

区间dp（动归思想）
浏览：938

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

归并排序详细解法

　　作者: HzuQZH　　　　发表时间：2019-11-01 13:27:44 浏览：1176　|　评论：0　

原题链接：数据结构-归并排序

# 归并排序算法
	虽然c++的STL中有sort算法，但是这个算法可以有效求出逆序对的问题
	时间复杂度上与sort函数和快速排序算法相差无几
	
**归并排序拓展*：处理逆序对**

## 归并排序
**这个算法采用的是分而治之的思想，顾名思义就是把一个数组分开来处理，然后再合并唯一。**
	
	时间复杂度：归并排序比快速排序稳定，因此它的时间复杂度为 O（nlogn），不管在什么情况下都是这种情况。

## 归并排序的大致过程：
		这里需要注意，当返回时处理的区间已经是在区间内有序的。
		
		先把递归的把数组分成左右两个小区间（以mid为中），一直分，直到当区间里的元素只有一个时返回，设置两个指针i，j。
		
		（l）指向左区间最左边的第一个元素，j（mid+1）指向右区间最左边的第一个元素，开一个临时数组（temp）；
		然后比较这两个指针所指向的元素，小的数就放入临时数组（temp），并且指针向后移动，依次操作。
		当i超过mid或者j超过r的时候证明左区间或右区间以及没有元素，退出操作，因为上面的操作是当左区间或右区间中一个区间没有元素时退出。
	所以我们需要判断哪个区间还有数，并且放入临时数组（temp）
		最后再把temp数组赋值给a数组就完成了当前这个区间的排序，再返回上一层递归。

**这个图是将区间递归分**![](https://img-blog.csdnimg.cn/20191101131844888.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczODc2NA==,size_16,color_FFFFFF,t_70)

上代码：

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> Pall;
namespace IO{
    inline LL read(){
        LL o=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
        return o*f;
    }
}using namespace IO;
const int N=1e5+7,INF=0x3f3f3f3f;
int a[N];
void merge_sort(int l,int r){
    if(l>=r)return ;//如果区间中只有一个元素时，就返回
    int mid=l+r>>1;//确定中间点（区间分界点）
    merge_sort(l,mid),merge_sort(mid+1,r);//左边递归处理，右边递归处理
    int i=l,j=mid+1,temp[r-l+1],cnt=0;//i指针指向左区间的最左边的元素，j指针指向右区间最右边的元素，temp是临时数组
    while(i<=mid&&j<=r){//如果左区间还有元素并且右区间还有元素，就需要进行比较
        if(a[i]<=a[j])temp[cnt++]=a[i++];//如果i指向的元素比j指向的元素小或相等，就把i指向的元素放入临时数组，并且移动i到下一个元素
        else temp[cnt++]=a[j++];//如果j指向的元素比j指向的元素大，就把j指向的元素放入临时数组，并且移动j到下一个元素
    }
    while(i<=mid)temp[cnt++]=a[i++];//如果左区间还有元素，就把剩下的元素放入临时数组。如果没有就不会执行
    while(j<=r)temp[cnt++]=a[j++];//如果右区间还有元素，就把剩下的元素放入临时数组。如果没有就不会执行
    for(i=l,j=0;i<=r;i++,j++)a[i]=temp[j];//最后i指向的是这个大区间的最左边（左区间+右区间），j指向的是temp的首元素。
    //把temp中的排好的的元素赋值到a数组中（l,r）这个区间，因为这个递归层就是处理（l,r）区间的排序。
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    merge_sort(0,n-1);//归并排序
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

```

0.0分

8 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

HzuQZH

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

宏定义（C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

矩阵转置（C语言代码）

归并排序详细解法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言训练-求素数问题（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

求组合数（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

【绝对值排序】（C语言代码）

【计算直线的交点数】（C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

HzuQZH

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

宏定义（C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

矩阵转置 （C语言代码）

归并排序详细解法

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言训练-求素数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

求组合数 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

【绝对值排序】 （C语言代码）

【计算直线的交点数】 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

矩阵转置（C语言代码）

　　评论区

C语言训练-求素数问题（C语言代码）

求组合数（C语言代码）

【绝对值排序】（C语言代码）

【计算直线的交点数】（C语言代码）