锐客网

  1. 首页 > it技术 > >

每天刷题档|merge_sort_归并排序 —每日算法档

数据结构leetcode排序算法每天刷题档

【每天刷题档|merge_sort_归并排序 —每日算法档】归并排序 ：
用到了递归思想 将一个
每天刷题档|merge_sort_归并排序 —每日算法档
文章图片

不停的将其 进行拆分 拆分到 （1）剩下一个 停止
每天刷题档|merge_sort_归并排序 —每日算法档
文章图片

（2） 拆完就将其进行排序 中间用一个b 变量进行
充当中间的变量 小的放在前面
每天刷题档|merge_sort_归并排序 —每日算法档
文章图片

总体思想：递归排序 要先执行到 最深层的那一部分（剩下两个数字） 对其左右进行排序 再进行操作 已经分割后的两个是已经排完的
然后再分别将左右两边的进行排序
判断逻辑
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. 树的重心**

    下一篇：c++|2022/3/29 每日思维