插入排序

直接插入排序

时间复杂度 : O(n²) , θ(n²) , Ω(n)
插入排序由n-1趟排序组成 , 对于p=1 到 n-1趟 , 插入排序保障从位置0到p上的元素为已排序状态
在第p次移动时 , 我们将位置p上的元素向左移动 , 直到它在前面的元素中找到正确的位置

public static void sort(){
        int i = 0;
        for (int p = 0; p < a.length; p++) {
            int tmp = a[p];
            for (i = p; i > 0 && a[i-1] > tmp; i--) {
                a[i] = a[i-1];
            }
            a[i] = tmp;
        }
}