当前位置：首页 > 编程日记 > 正文

递归/分治：归并排序

编程日记 2024-04-19 23:00:00

前言

分治算法:
将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解后进行合并，就可得到原问题的解。

步骤如下:

分解，将要解决的问题划分成若干规模较小的同类问题;
求解，当子问题划分得足够小时，用较简单的方法解决;
合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

归并排序

在描述归并排序之前，我们先来看看如何合并两个有序数组，大概过程类似与之前描述过的两个有序链表的合并

实现过程如下:

void merge_two_arr(std::vector<int> &arr1, std::vector<int> &arr2, std::vector<int> &result) {int i = 0;int j = 0;/*在下标不断累加的过程中优先插入较小的一个元素，且对应的下标累加*/while(i < arr1.size() && j < arr2.size()) {if (arr1[i] <= arr2[j]) {result.push_back(arr1[i]);i++;} else {result.push_back(arr2[j]);j++;}}if (i == arr1.size()) { //将剩余的未合并的元素合入for (;j < arr2.size(); ++j) {result.push_back(arr2[j]);}} else {for (;i < arr1.size(); ++i) {result.push_back(arr1[i]);}}
}

依据分治算法的步骤，我们回到归并排序的过程上

以上过程即实现了分治算法的第三步：合并；

那么分治算法的第一步：分解，第二步：求解该如何做呢？

显然，我们的一个无序数组同样可以不断得二分，最终拆解为对底层的两两合并，对于每一个分解后的集合，我们同样使用合并有序数组（因为只有两个元素了，要做的就是对两个元素的合并）的过程。

实现如下:

void merge_sort(std::vector<int> &arr) {if (arr.size() < 2) {return ;}int mid = arr.size() / 2;std::vector<int> arr1;std::vector<int> arr2;for (int i = 0; i < mid; ++i) {arr1.push_back(arr[i]);}for (int i = mid; i< arr.size(); ++i){arr2.push_back(arr[i]);}merge_sort(arr1);merge_sort(arr2);arr.clear();/*以上递归返回的arr1和arr2为有序数组，最终合并两个有序数组即可*/merge_two_arr(arr1,arr2,arr); 
}

测试代码如下:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdlib.h>using namespace std;
/*合并两个有序数组*/
void merge_two_arr(std::vector<int> &arr1, std::vector<int> &arr2, std::vector<int> &result) {int i = 0;int j = 0;while(i < arr1.size() && j < arr2.size()) {if (arr1[i] <= arr2[j]) {result.push_back(arr1[i]);i++;} else {result.push_back(arr2[j]);j++;}}if (i == arr1.size()) {for (;j < arr2.size(); ++j) {result.push_back(arr2[j]);}} else {for (;i < arr1.size(); ++i) {result.push_back(arr1[i]);}}
}
/*归并排序*/
void merge_sort(std::vector<int> &arr) {if (arr.size() < 2) {return ;}int mid = arr.size() / 2;std::vector<int> arr1;std::vector<int> arr2;for (int i = 0; i < mid; ++i) {arr1.push_back(arr[i]);}for (int i = mid; i< arr.size(); ++i){arr2.push_back(arr[i]);}merge_sort(arr1);merge_sort(arr2);arr.clear();merge_two_arr(arr1,arr2,arr);
}int main(int argc, char const *argv[])
{std::vector<int> arr;int n; cin >> n;int tmp;for (int i = 0; i < n; ++i) {cin >> tmp;arr.push_back(tmp);}	merge_sort(arr);for (int i = 0;i < arr.size(); ++i) {cout << arr[i] << " ";}cout << endl;return 0;
}

输出如下:

#输入
5
-7 3 -4 -1 2
#输出
-7 -4 -1 2 3

https://www.dkcj.cn/info/4931.html

Java中volatile 的使用场景有哪些？

volatile是一种轻量级的同步机制，它能保证共享变量的可见性，同时禁止重排序保证了操作的有序性，但是它无法保证原子性。所以使用volatilevolatile。

编程日记2024/04/19 22:30:05

Java 22 除了推出了新的增强功能和特性，也获得 Java Management Service (JMS) 的支持，这是一项新的 Oracle 云基础设施远程软件服务(Oracle Cloud Infrastructure, OCI) 原生服务，提供统一的控制台和仪表盘，帮助企业管理本地或云端的 Java 运行时和应用。使包含运行时计算值的字符串更容易表达，简化 Java 程序的开发工作，同时提高将用户提供的值编写成字符串，并将字符串传递给其他系统的程序的安全性。支持开发人员自由地表达构造器的行为。

编程日记2024/04/19 22:30:05

递归/分治：归并排序

前言

归并排序

相关文章：

Java中volatile 的使用场景有哪些？

JDK22 正式发布了！

Jackson 用起来！

Swift中的问号?和感叹号!

拜托！别再滥用 ! = null 判空了！！

ffmpeg java linux水印,Linux环境用FFmpeg给视频加水印详细步骤

red hat DHCP服务器配置

axios解决调用后端接口跨域问题

递归/归并：count of smaller numbers求逆序数

远程计划任务管理

linux shell for 循环变量,shell for循环总结

自定义堆栈（回文检测）

二叉树(C++)：创建，前中后序遍历（递归+非递归），获取叶子节点个数，获取树的高度

6月11号=》121页-125页

linux cp sync,通过SSH使用Rsync传输文件，复制和同步文件及目录

【Java笔记】C++与Java的对比

cf792b循环链表

二叉树：路径之和 Path Sum

从零开始编写自己的C#框架（16）——Web层后端父类

c语言中的普通字符包括什么,【判断题】C语言中的字符常量通常有两种形式:普通字符和转义字符。...

Codeforces Round #104 (Div. 2) E DP(01背包模型) +组和+除法取模求逆元

django 增加验证邮箱功能

二叉树：最近的公共祖先 Lowest Common Ancestor of a Binary Tree

VS不显示最近打开的项目

河科大c语言上机实验答案,2016年河南科技学院信息工程学院C语言上机编程考研复试题库...

无符号数溢出之后

加载BeanFactory

t-top 命令详解

怎么看懂c语言程序,求讲解一下这个程序，我看了1个小时都没有看懂，

【转】Winform输入法控制