9.27-排序与递归调用
数组顺序/倒序排序
package day9_27;
import java.util.Arrays;
public class SortDemo {
public static void main(String[] args) {
int[] ary= {1,2,5,4,8,0};
System.out.println("排序前"+Arrays.toString(ary));
Arrays.sort(ary);
System.out.println("排序后"+Arrays.toString(ary));
bubbleSort(ary);
selectSorf(ary);
}
//冒泡排序
public static void bubbleSort(int[] a) {
//外层循环表示循环轮数
for(int i=0;i<a.length-1;i++) {
// 内层循环实现相邻元素的的比较换位
for(int j=0;j<a.length-1-i;j++) {
if(a[j]>a[j+1]) {
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
System.out.println(Arrays.toString(a));
}
public static void selectSorf(int[] a) {
//选择排序
//外层循环表示轮数
for(int i=0;i<a.length-1;i++) {
//内层实现两个元素比较换位
for(int j=i+1;j<a.length-1;j++) {
if(a[i]<a[j]) {
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
System.out.println(Arrays.toString(a));
}
}
递归调用
在方法中直接或间接的调用方法自身
好处
可以简洁的处理问题,只要搞清楚第一层,其他都一样
缺点
不能进行过深递归,递归过深会导致栈内存溢出错误(StackOverflowError)
不能进行发散递归
递归算法一定要有结束条件
例子
package day9_27;
public class DiGuiDemo01 {
/**
* 需求:
* 计算sum=1+2+3+4+5+6+...+n
*/
public static void main(String[] args) {
System.out.println(f1(10));
}
//普通方法
public static int f1(int n) {
int sum=0;
for(int i=1;i<=n;i++) {
sum=sum+i;
}
return sum;
}
//递归方法
public static int f2(int n) {//f2(n)=f2(n-1)+n
if (n==1) {
return 1;
}
return f2(n-1)+n;
}
}
例子-斐波那契数列
package day07;
public class DiGuiDemo02 {
/**
* 有如下数列:(斐波那契数列)
* 1 1 2 3 5 8 13 21 34 55....
* 求第n个斐波那契数?
* f(n)=f(n-1)+f(n-2)且f(1)=f(2)=1
*/
public static void main(String[] args) {
System.out.println(f1(30));
}
//递归方法
public static long f1(int n) {//f1(n)
if(n==1||n==2) {
return 1;
}
return f1(n-1)+f1(n-2);
}
//普通方法
public static long f2(int n){
int[] res ={0,1};
if(n<2){
return res[n];
}
int frist = 0;
int second = 1;
int fibn =0;
for(int i=2;i<=n;i++){
fibn=frist+second;
frist=second;
second=fibn;
}
return fibn;
}
}
最后更新于