#创作计划# 分治思想 看一眼呗
2025-09-16 20:29:29
发布于:上海
各位老师,各位家长,各位同学,各位学弟学妹们弄错场景了
镜头切到电脑
CHAPTER 1
古代有个成语
核癌氪氰的小明:“”
接下来就要讲 关键了
咋么分 咋么合
CHAPTER 2
二分应该学过吧
我们借助图来理解
我们发现 第一层8个数字在第二层中分成了两组,一组四个数(也就是8/2)
第三层再在第二层的基础上每组(4 / 2)个数,总共4组
以此类推
直到一层中每组只有一个数
那么合的时候:就需要对每层的每组进行排列
我可以明确的告诉你:这是一种排序叫归并排序
CHAPTER 3 代码
#include<bits/stdc++.h>
using namespace std;
const int max_n = 1e5 + 10;
typedef long long ll;
int n;
ll a[max_n],b[max_n];//b数组为临时数组,用于合并
//任务准备:函数编写
void merge(int l,int r)
{//对待排序序列l~r区间进行排序
//判断结束条件
if(l == r){
return; //如果该序列长度为1
}
int mid = (l + r) / 2;
//分成两组
merge(1,mid);
merge(mid + 1,r);
//接下来合并:
int i = l,j = mid + 1;//初始化,i表示一组中最小的数字,j表示另一组最小的数字
for(int k = l;k <= r;k++){//遍历l到r的每个位置
if(j > r || (i <= mid && a[i] <= a[j])){ //右半段为空,或者i必须小于中点且a[i] <= a[j]
b[k] = a[i++];
}else{
b[k] = a[j++];
}
}for(int i = l;i <= r;i++){
a[i] = b[i];//賦值回原数组
}
}
int main(){
cin >> n;
//主线任务:对a数组进行排序
for(int i = 1;i <= n;i++){
cin >> a[i];
}merge(1,n);
for(int i = 1;i <= n;i++){
cout << a[i] << " ";
}
return 0;
}
输入
输出
是不是很厉害
CHAPTER 4
关于时间复杂度,
他死了,我们来算一算
CHAPTER 5
告诉各位归并排序是稳定的,不稳定的排序「有快速排序、选择排序、堆排序和希尔排序」
B选项正确
C选项他需要额外的空间(临时数组b)
D选项他结果要从小到大排
CHAPTER 6 彩蛋
讲完了,你学费了吗,点个赞欧,给个彩蛋吧
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
祝大家学业有成,健健康康,生活淼淼,巳巳如意!!!!!!!!!!!!!!!!!
全部评论 4
5小时前 来自 上海
0d
5小时前 来自 上海
0d
5小时前 来自 上海
0大老勿喷
5小时前 来自 上海
0
有帮助,赞一个