插入排序

插入排序

Description

实现插入排序。

Input

输入第一行为用例个数， 每个测试用例输入的每一行代表一个数组，其中的值用空格隔开，第一个值表示数组的长度。

Output

输出排序的数组，用空格隔开，末尾不要空格。

Solution

public class InsertSort {

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int caseNum = in.nextInt();
        for(int i = 0; i < caseNum; i++){
            int len = in.nextInt();
            int[] arr = new int[len];
            for(int j = 0; j < len; j++){
                arr[j] = in.nextInt();
            }
            insertSort(arr);
        }
    }

    public static void insertSort(int[] arr){
        for(int i = 1; i < arr.length; i++){
            int temp = arr[i];
            int j = i - 1;
            while(j >= 0 && temp < arr[j]){
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
        System.out.print(arr[0]);
        for(int i = 1; i < arr.length; i++){
            System.out.print(" " + arr[i]);
        }
        System.out.println();
    }
}