插入排序

Description

實現(xiàn)插入排序。

Input

輸入第一行為用例個數(shù)， 每個測試用例輸入的每一行代表一個數(shù)組，其中的值用空格隔開，第一個值表示數(shù)組的長度。

Output

輸出排序的數(shù)組，用空格隔開，末尾不要空格。

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