当前位置:网站首页>Recursive way
Recursive way
2022-07-06 18:12:00 【eight hundred and forty-eight million six hundred and ninety-ei】
recursive
Recursive method to achieve the maximum value of the array
@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] Find the maximum value on the range
public int recursion(int[] arr, int l, int r) {
if (l == r) {
//arr[l...r] There is only one number in the range , Go straight back to
return arr[l];
}
int mid = l + ((r - l) >> 1); // Finding the midpoint , Prevent overflow
int leftMax = recursion(arr, l, mid);
int rightMax = recursion(arr, mid + 1, r);
return Math.max(leftMax, rightMax);
}
Merge sort
- The core idea used
Divide and conquer
Local sort first ,,,,,, Then sort the whole
First, divide a complete array into two halves ( Left half , Right half , Then divide the left side into two halves ,,,,, Until it can't be further divided , Then sort ,,,, Left row , The right row ...) Finally, the overall order
Space for time
Time complexity 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]);
}
}
/** * recursive , Bisection order * @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); // Order on the left
process(arr, mid + 1, r); // Order on the right
merge(arr, l, mid, r);
}
/*** * Sort * @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]; // Store the locally ordered array
int i = 0; // Index for new array
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++];
}
/** * Assign the ordered new array to the old array */
for (i = 0; i < help.length; i++) {
arr[l+i] = help[i];
}
}
Extension of merge sort
边栏推荐
- 重磅硬核 | 一文聊透对象在 JVM 中的内存布局,以及内存对齐和压缩指针的原理及应用
- 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
- Jerry's watch reading setting status [chapter]
- Take you through ancient Rome, the meta universe bus is coming # Invisible Cities
- Nodejs 开发者路线图 2022 零基础学习指南
- Jerry is the custom background specified by the currently used dial enable [chapter]
- In terms of byte measurement with an annual salary of 30W, automated testing can be learned in this way
- Codeforces Round #803 (Div. 2)
- Easy introduction to SQL (1): addition, deletion, modification and simple query
猜你喜欢
编译原理——预测表C语言实现
Olivetin can safely run shell commands on Web pages (Part 1)
How to solve the error "press any to exit" when deploying multiple easycvr on one server?
Compilation Principle -- C language implementation of prediction table
Prophet模型的简介以及案例分析
On time and parameter selection of asemi rectifier bridge db207
传输层 拥塞控制-慢开始和拥塞避免 快重传 快恢复
30 分钟看懂 PCA 主成分分析
There is a gap in traditional home decoration. VR panoramic home decoration allows you to experience the completion effect of your new house
Why should Li Shufu personally take charge of building mobile phones?
随机推荐
关于这次通信故障,我想多说几句…
队列的实现
编译原理——预测表C语言实现
MSF horizontal MSF port forwarding + routing table +socks5+proxychains
Jerry's access to additional information on the dial [article]
STM32 key state machine 2 - state simplification and long press function addition
STM32按键状态机2——状态简化与增加长按功能
The difference between parallelism and concurrency
Flet教程之 13 ListView最常用的滚动控件 基础入门(教程含源码)
After entering Alibaba for the interview and returning with a salary of 35K, I summarized an interview question of Alibaba test engineer
Jerry is the custom background specified by the currently used dial enable [chapter]
Today in history: the mother of Google was born; Two Turing Award pioneers born on the same day
Olivetin can safely run shell commands on Web pages (Part 1)
Grafana 9.0 正式发布!堪称最强!
李书福为何要亲自挂帅造手机?
JMeter interface test response data garbled
Common - magic number 7
[introduction to MySQL] the first sentence · first time in the "database" Mainland
高精度运算
Take you through ancient Rome, the meta universe bus is coming # Invisible Cities