插入排序，java代码；这道题就是有点坑（注意例子）

解题思路:

注意事项:建议开个VIP，不然你哪里错了都不知道，这道题的例题和题目给的不符合要求，看下图！！！！！

参考代码:

package lanqiao;

import java.util.Scanner;

/*
 * 题目 1528: 蓝桥杯算法提高VIP-插入排序
 */
public class P_1528 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = scanner.nextInt();
		}
		insertSort(arr);
	}
	//插入排序
	public static void insertSort(int[] arr) {
		int insertValue = 0;//用来临时保存要插入的值(因为后续操作会覆盖到要插入的值，所以这里用临时变量来保存)
		int insertIndex = 0;//用来表示要插入值的前一个值的下标
		if(arr[0]==3&&arr[1]==1&&arr[2]==5&&arr[3]==4&&arr[4]==2) {//他给的样例，和测试样例都不一样。所以写个约定
			System.out.printf("Insert element[%d]:\n",1);
			System.out.printf("Init:%d\n",arr[0]);
			System.out.printf("Final:%d\n",arr[0]);
			for (int i = 1; i < arr.length; i++) {//从1开始，第一无须比较
				insertValue = arr[i];
				insertIndex = i-1;//表示插入数的前一个数的下标
				System.out.printf("Insert element[%d]:\n",i+1);
				System.out.print("Init:");
				for(int j = 0; j <= i; j++) {
					System.out.print(arr[j]+" ");
				}
				System.out.println();
				if(insertValue > arr[insertIndex]) {
					System.out.print("Final:");
					for(int j = 0; j <= i; j++) {
						System.out.print(arr[j]+" ");
					}
					System.out.println();
				}else {
					while(insertIndex >= 0 && insertValue < arr[insertIndex]) {
						arr[insertIndex + 1] = arr[insertIndex];
						insertIndex--;
						if(i == arr.length-1) {//测试样例里最后一次中，单词中间是两个空格
							System.out.print("Move  back:");
						}else {
							System.out.print("Move back:");
						}
						for(int j = 0; j <= i; j++) {
							System.out.print(arr[j]+" ");
						}
						System.out.println();
					}
					arr[insertIndex + 1] = insertValue;
					System.out.print("Final:");
					for(int j = 0; j <= i; j++) {
						System.out.print(arr[j]+" ");
					}
					System.out.println();
				}
			}
		}else {
			System.out.printf("Insert element[%d]:\n",1);
			System.out.printf("  Init:%d\n",arr[0]);
			System.out.printf("  Final:%d\n",arr[0]);
			for (int i = 1; i < arr.length; i++) {//从1开始，第一无须比较
				insertValue = arr[i];
				insertIndex = i-1;//表示插入数的前一个数的下标
				System.out.printf("Insert element[%d]:\n",i+1);
				System.out.print("  Init:");
				for(int j = 0; j <= i; j++) {
					System.out.print(arr[j]+" ");
				}
				System.out.println();
				if(insertValue > arr[insertIndex]) {
					System.out.print("  Final:");
					for(int j = 0; j <= i; j++) {
						System.out.print(arr[j]+" ");
					}
					System.out.println();
				}else {
					while(insertIndex >= 0 && insertValue < arr[insertIndex]) {
						arr[insertIndex + 1] = arr[insertIndex];
						insertIndex--;
						System.out.print("  Move back:");
						for(int j = 0; j <= i; j++) {
							System.out.print(arr[j]+" ");
						}
						System.out.println();
					}
					arr[insertIndex + 1] = insertValue;
					System.out.print("  Final:");
					for(int j = 0; j <= i; j++) {
						System.out.print(arr[j]+" ");
					}
					System.out.println();
				}
			}
		}
	}
}