分析插入排序

给你一个n代表有n个数字，然后你需要使用插入排序将这些数字从小到大排好。
输入描述:
第一行输入一个n，代表有n个数字
第二行输入n个数


输出描述:
输出排序好后的n个数
示例1
输入
4
4 3 2 1
输出
1 2 3 4

1、先把0~1下标的数排序,3比3小交换4和3，结果：3 4 2 1
2、然后把0~2下标的数排序，2比4小交换2和4,2比3小，交换2和3，发现3和4之前排过序了，所以只需要拿最后一个数一直与前面的数比较，如果小就交换，结果：2 3 4 1
3、然后把0~3下标的数排序，由上得，结果：1 2 3 4
综述：外循环是排序的范围，i从1 到 n-1，内循环是往前比较的数 j，j下标的数如果大于j+1下标的数且j不能小于0(越界)，则交换两者值。

import java.util.*;
import java.io.*;
 
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int[] arr = new int[size];
        for(int i=0;i=0&&arr[j]>arr[j+1];j--){
                swap(arr, j, j+1);
            }    
        }
        for(int i=0;i 
时间复杂度 
插入排序的时间复杂度与数据情况有关：
 如果数据是最糟糕的情况，从大到小排序的，则依次要比较1、2、3、n-1次，合计an*n+bn+c，所以时间复杂度是O(n^2)
 如果数据就是从小到大排序的，则每次比较都是1次，合计n，所以时间复杂度是O(n)
 
空间复杂度 
因为只需要定义几个int变量就能完成存储，所以空间复杂度都是O(1)