直接插入排序
时间复杂度 : 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;
}
}
