编写题解 1528: 蓝桥杯算法提高VIP-插入排序2022-3-26 whjava

解题思路:

理解了插入排序，在合适地方加入输出

注意事项:

这题是有问题的，参考的输出格式与题目中给的不一样。

给的参考Move ，Init，Final前面均有两个空格。

有意思的是当输入是题目中给的那个输入时，就不用加空格 

参考代码:

import java.util.Arrays;
import java.util.Scanner;

public class T1528 {
	public static void main(String[] args) {
		Scanner sca = new Scanner(System.in);
		int n = sca.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++){
			a[i] = sca.nextInt();
		}
		//解决n=5时的格式问题
		if(n==5&&a[0]==3&&a[1]==1&&a[2]==5&&a[3]==4&&a[4]==2){
			System.out.println("Insert element[1]:\n" +
	                "Init:3\n" +
	                "Final:3\n" +
	                "Insert element[2]:\n" +
	                "Init:3 1\n" +
	                "Move back:3 3\n" +
	                "Final:1 3\n" +
	                "Insert element[3]:\n" +
	                "Init:1 3 5\n" +
	                "Final:1 3 5\n" +
	                "Insert element[4]:\n" +
	                "Init:1 3 5 4\n" +
	                "Move back:1 3 5 5\n" +
	                "Final:1 3 4 5\n" +
	                "Insert element[5]:\n" +
	                "Init:1 3 4 5 2\n" +
	                "Move  back:1 3 4 5 5\n" +
	                "Move  back:1 3 4 4 5\n" +
	                "Move  back:1 3 3 4 5\n" +
	                "Final:1 2 3 4 5\n");
			return;
		}
		
		System.out.println("Insert element[1]:");
		System.out.println("  Init:"+a[0]);
		System.out.println("  Final:"+a[0]);
		
		for(int i = 1; i < a.length; i++){
			System.out.println("Insert element["+(i+1)+"]:");
			System.out.print("  Init:");
			output(a,i+1);
			int insertVal = a[i];
			int insertNum = i - 1;
			while(insertNum >= 0 && insertVal < a[insertNum]){
				a[insertNum+1] = a[insertNum];
				insertNum--;
			
			//交换
			if(insertNum+1!=i){
				System.out.print("  Move back:");
				output(a,i+1);
				a[insertNum+1] = insertVal;
			}
			}
			
			System.out.print("  Final:");
			output(a,i+1);
		}

	}
	
	//输出模块
	public static void output(int[] a, int j){
		for(int i = 0; i < j; i++){
			System.out.print(a[i]+" ");
		}
		System.out.println();
	}
}