当前位置:网站首页>递归的方式
递归的方式
2022-07-06 10:08:00 【848698119】
递归的方式实现取数组最大值
@Test
public void TestMax() {
int a[] = {
0, 1, 2, 5, 3, 2, 1, 8, 4, 2, 0};
System.out.println(getMax(a));
}
public int getMax(int[] arr) {
return recursion(arr, 0, arr.length - 1);
}
//arr[l...r]范围上求最大值
public int recursion(int[] arr, int l, int r) {
if (l == r) {
//arr[l...r]范围上只有一个数,直接返回
return arr[l];
}
int mid = l + ((r - l) >> 1); //求中点,防止溢出
int leftMax = recursion(arr, l, mid);
int rightMax = recursion(arr, mid + 1, r);
return Math.max(leftMax, rightMax);
}
归并排序
- 其用到的核心思想
分治
先局部排序,,,,,,然后整体排序
先把一个完整的数组分为两半(左一半,右一半,然后再把左边分成两半,,,,,直到不能再分,然后排序,,,,左边排,右边排。。。)最后整体排序
空间换时间
时间复杂度O(nlogn)
@Test
public void sort(){
int a[]={
2,5,4,6,9,7,1,0};
process(a,5,7);
for (int i = 0; i < 8; i++) {
System.out.print(a[i]);
}
}
/** * 递归,二分排序 * @param arr * @param l * @param r */
public void process(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
process(arr, l, mid); //左边有序
process(arr, mid + 1, r); //右边有序
merge(arr, l, mid, r);
}
/*** * 排序 * @param arr * @param l * @param mid * @param r */
private void merge(int[] arr, int l, int mid, int r) {
int[] help = new int[r - l + 1]; //把局部排好序的数组存放进来
int i = 0; //用于新数组的索引
int j = l;
int k = mid + 1;
while (j <= mid && k <= r) {
help[i++] = arr[j] <= arr[k] ? arr[j++] : arr[k++];
}
while (j<=mid){
help[i++] = arr[j++];
}
while (k<=r){
help[i++] = arr[k++];
}
/** * 把排好序的新数组赋给老数组 */
for (i = 0; i < help.length; i++) {
arr[l+i] = help[i];
}
}
归并排序的扩展
边栏推荐
- 李书福为何要亲自挂帅造手机?
- Unity tips - draw aiming Center
- 微信小程序中给event对象传递数据
- The shell generates JSON arrays and inserts them into the database
- Solution qui ne peut pas être retournée après la mise à jour du navigateur Web flutter
- scratch疫情隔离和核酸检测模拟 电子学会图形化编程scratch等级考试三级真题和答案解析2022年6月
- 传统家装有落差,VR全景家装让你体验新房落成效果
- [Android] kotlin code writing standardization document
- The solution that flutterweb browser cannot be rolled back after refreshing
- Manifest of SAP ui5 framework json
猜你喜欢
Manifest of SAP ui5 framework json
Is it meaningful for 8-bit MCU to run RTOS?
There is a gap in traditional home decoration. VR panoramic home decoration allows you to experience the completion effect of your new house
Compilation principle - top-down analysis and recursive descent analysis construction (notes)
分布式不来点网关都说不过去
After entering Alibaba for the interview and returning with a salary of 35K, I summarized an interview question of Alibaba test engineer
李书福为何要亲自挂帅造手机?
Getting started with pytest ----- test case rules
一体化实时 HTAP 数据库 StoneDB,如何替换 MySQL 并实现近百倍性能提升
[introduction to MySQL] the first sentence · first time in the "database" Mainland
随机推荐
It doesn't make sense without a distributed gateway
EasyCVR平台通过接口编辑通道出现报错“ID不能为空”,是什么原因?
Pytest learning ----- pytest operation mode and pre post packaging of interface automation testing
F200——搭载基于模型设计的国产开源飞控系统无人机
Awk command exercise
Insert dial file of Jerry's watch [chapter]
Release of the sample chapter of "uncover the secrets of asp.net core 6 framework" [200 pages /5 chapters]
Appium automated test scroll and drag_ and_ Drop slides according to element position
微信小程序中给event对象传递数据
Growth of operation and maintenance Xiaobai - week 7
Unity tips - draw aiming Center
Olivetin can safely run shell commands on Web pages (Part 1)
Shell input a string of numbers to determine whether it is a mobile phone number
传统家装有落差,VR全景家装让你体验新房落成效果
Distinguish between basic disk and dynamic disk RAID disk redundant array
QT中Model-View-Delegate委托代理机制用法介绍
Markdown grammar - better blogging
微信小程序获取手机号
Pytest learning ----- detailed explanation of the request for interface automation test
Debug and run the first xv6 program