先放上老版代码，这个并不好，由于用到了各种指针和动态数组申请和释放，容易出现问题，不如第二种方法直接用临时数组来解决这个问题
老版：
//归并 left是左边数组 left_len长度
int* Merge(int* left,int left_len, int* right,int right_len){
//申请一个数组res来存储结果
int* res = (int *)malloc(sizeof(int)*(left_len+right_len));
int l=0,r=0,k=0;
//l r 分别是左右的指针 k是当前处理之后放在res的下标
//只要有一边还有元素
while (lright[r]){//左边大于右边 说明是逆序数 此时左边还剩的元素个数就是f(r)
cot += left_len - l;
//cot累加
res[k++]=right[r++];
}else{
res[k++]=left[l++];
}
}
//还剩一些元素
for (;
l 新版（临时数组）：
//新版
//A是待排序数组 T是临时数组 处理的是[x,y)
void MergeSort(int* A,int x,int y, int* T){
if(y-x<=1)return;
//只有一个元素 或者 空的时候 直接返回 不做任何更改
int m = x+(y-x)/2;
//中间下标
//分治第一步划分已经完成，现在开始第二步 递归调用
MergeSort(A, x, m, T);
//处理[x,m)
MergeSort(A, m, y, T);
//处理[m,y)
//开始第三步 归并 合并结果
int l=x,r=m,i=x;
//l是左半边的指针 r是右半边的 i是当前指T的指针while (l=y || (l 【算法学习笔记|【算法学习笔记】20.算法设计初步 归并排序 求逆序数】
推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）
- 网络|简单聊聊压缩网络