蓝桥杯算法提高VIP-选择排序-题解（递归解法）（Java代码）

递归思想：处理问题时，想办法把父问题转化成一个个相同的子问题，这些子问题形式相同，参数有变化。且这些子问题是“有限”个。

     本题的父、子问题为：

     父问题：对整个序列进行选择排序；

     子问题：对序列中的每一个元素进行交换。

     （写得不好，仅供参考）

解题思路: 每次都是用序列中的最小值与对应的元素进行交换。

注意事项: 每交换一次，就确定了一位，所以下一次求最小值时要从这位“后面”开始。即代码中的count+1

参考代码:

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		int[] arr=new int[n];
		for (int i = 0; i < arr.length; i++) 
			arr[i]=input.nextInt();
		f(n,0,arr);
		
	}
/* 递归要素：
 * 	1.找重复：每次都是用最小的元素和前面的元素交换
 * 	2.找变化：每交换一次，count就往后移动1位
 * 	3.找出口：当所要排序的元素位置count==n时，排序完成。
 */

	private static void f(int n, int count,int[] arr) {
		//设置出口
		if(n==count)  
			return;
		//找最小值和最小值对应的下标
		int min=arr[count];
		int lable=count;
		for (int i = count+1; i < arr.length; i++) 
			if(min>arr[i])
			{
				min=arr[i];
				lable=i;
			}
		//交换
		int k=arr[count];
		arr[count]=arr[lable];
		arr[lable]=k;
		//打印当前排序情况
		System.out.printf("swap(a[%d], a[%d]):",count,lable);
		for (int i = 0; i < arr.length; i++) 
			System.out.print(arr[i]+" ");
		System.out.println();
		//所要排序的元素位置count+1，即往后移动一位，继续排序
		f(n, count+1, arr);	
	}

}