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;
    }
}