作业介绍
C4.06 分治算法
课堂内容:分治策略
-
归并排序
-
参考代码
#include<bits/stdc++.h>
using namespace std;
// 定义两个全局数组 a 和 b,以及一个全局变量 n
int a[1005], b[1005], n;
// Merge 函数,用于合并两个已排序的子数组
void Merge(int L, int R, int mid) {
// i 和 j 分别指向两个子数组的起始位置,k 用于指向临时数组 b 的当前位置
int i = L, j = mid + 1, k = 1;
// 合并操作,将元素依次放入临时数组 b 中
while (i <= mid && j <= R) {
if (a[i] > a[j]) // 如果左子数组的元素大于右子数组的元素
b[k++] = a[i++]; // 将左子数组的元素放入 b,并移动左子数组的指针
else
b[k++] = a[j++]; // 否则将右子数组的元素放入 b,并移动右子数组的指针
}
// 如果左子数组还有剩余元素,将其全部放入 b
while (i <= mid)
b[k++] = a[i++];
// 如果右子数组还有剩余元素,将其全部放入 b
while (j <= R)
b[k++] = a[j++];
// 将临时数组 b 的元素复制回原数组 a
k = 1;
for (int i = L; i <= R; i++)
a[i] = b[k++];
}
// Msort 函数,递归地执行归并排序
void Msort(int L, int R) {
// 如果 L 和 R 相等,说明只有一个元素或没有元素,无需排序,直接返回
if (L == R) return;
// 计算中点,将数组分为两部分
int mid = (L + R) / 2;
// 递归地对左半部分和右半部分进行排序
Msort(L, mid);
Msort(mid + 1, R);
// 合并已排序的子数组
Merge(L, R, mid);
}
int main() {
// 输入数组的长度
cin >> n;
// 输入数组的元素
for (int i = 1; i <= n; i++)
cin >> a[i];
// 调用归并排序函数
Msort(1, n);
// 输出排序后的数组
for (int i = 1; i <= n; i++)
cout << a[i] << " ";
return 0;
}
-
快速排序
-
sort()函数
sort
函数用于C++中,对给定区间所有元素进行排序,默认为升序,也可进行降序排序。sort函数包含在头文件为#include<algorithm>
的c++标准库中。
sort()函数调用一般形式
sort(start,end,cmp);
// tart 表示要排序数组的起始地址;对于数组来说就是数组的首地址,一般写上数组名就可以,因为数组名是一个指针常量。
// end 表示数组结束地址的下一位;即首地址加上数组的长度n(代表尾地址的下一地址)。
// cmp 用于规定排序的方法,可不填,默认升序。
-
sort()函数的cmp
sort函数没有第三个参数,实现的是从小到大(升序)排列。
较为简单的排序条件修改。
bool cmp(int x, int y)
{
return x > y; // 降序
}
较为复杂的排序条件自定义。
bool cmp(stu x, stu y) // 结构类型元素
{
return x.score > y.score; // score为结构类型的某个成员
}
题目
认领作业后才可以查看作业内容。
- 状态
- 正在进行…
- 题目
- 4
- 开始时间
- 2024-1-1 0:00
- 截止时间
- 2099-12-31 23:59
- 可延期
- 0 小时