插入排序

解题思路：

将一个数插入有序的数组中

public class Main {
   
    public static void main(String[] args) {
        int[] arr = new int[100];
        for(int i=0;i<100;i++) {
            arr[i] = (int) (Math.random() * 1000);
        }
        sort(arr);
        for(int i=0;i<100;i++){
            System.out.println(arr[i]);
        }
    }
    
    public static void sort(int[] arr) {
        int k = 0;
        for(int i=1;i<arr.length;i++) {
            //将第i个元素插入到[0..k]中
            int vi = arr[i];
            int q = i;
            for(int j=k;j>=0;j--) {
                if(vi < arr[j]) {
                    arr[q] = arr[j];
                    arr[j] = vi;
                    q--;
                }
                else{
                    break;
                }
            }
            k++;
        }
    }
    
    
}