【每天刷题档|merge_sort_归并排序 —每日算法档】归并排序 :
用到了递归思想 将一个
文章图片
不停的将其 进行拆分 拆分到 (1)剩下一个 停止
文章图片
(2) 拆完就将其进行排序 中间用一个b 变量进行
充当中间的变量 小的放在前面
文章图片
总体思想:递归排序 要先执行到 最深层的那一部分(剩下两个数字) 对其左右进行排序 再进行操作 已经分割后的两个是已经排完的
然后再分别将左右两边的进行排序
判断逻辑
1、前提 左边(left)小于中间(mid) 比较左边(lf)和右边第一个( mid+1)
(1)如果左边的小于右边 就 直接放入b【i】 左边+1
(2)如果左边的大于右边 放入右边 放入 b[i] 右边+1
2、如果左边(lf)的大于mid 说明 左边已经遍历完了
就将右边(rt)的依次放入
#include
using namespace std;
int a[1000], n;
int b[1000];
void hebing(int l, int mid ,int r)
{
int p = l,q = mid+1;
for (int i = l;
i <= r;
i++)
{
if((q>r)||(p<= mid && a[p]<= a[q]))
{
b[i] = a[p++];
}else
{
b[i] = a[q++];
}
}
for (inti = l;
i <= r;
i++)
{
a[i] = b[i];
}
}
void merge_sort(int l, int r)
{
if(l==r){
return;
}
int mid = (l+r)/2;
merge_sort(1,mid);
merge_sort(mid+1,r);
hebing(l,mid,r);
}
int main()
{
scanf("%d",&n);
for (int i = 1;
i <= n;
i++)
{
scanf("%d", &a[i]);
}
merge_sort(1,n);
for (int i = 1;
i <= n;
i++)
{
printf("%d", &a[i]);
}return 0;
}
推荐阅读
- acwing|【acwing】846. 树的重心**
- 蓝桥杯Java真题|19年蓝桥杯Java B组省赛第三题(数列求值)
- 13届蓝桥杯夺奖冲刺营|蓝桥杯省赛夺奖冲刺营链表篇
- 数据结构|最新|蓝桥杯备赛冲刺攻略,人手必备!
- 《树锯结构》|【数据结构原理】数组和结构 | ARRAYS AND STRUCTURES | 阅读笔记
- JavaSE|【JavaSE】面向对象编程必备技能,你学会了吗(继承、多态、抽象类、接口详解)
- 机器学习|机器学习—KNN算法
- Leetcode|Leetcode70-爬楼梯(C语言)
- 数据结构|数据结构之并查集(含代码实现)