直接插入排序分为两部分：有序区、无序区
排序方法：从无序区中取一个数，再到有序区中进行排列
直接插入排序
例子：5 8 4 7 1
第1趟: [5] 8 4 7 1
第2趟: [5 8] 4 7 1
第3趟: [4 5 8] 7 1
第4趟: [4 5 7 8] 1
第5趟: [1 4 5 7 8]
public class InsertSort {
public static void main(String[] args) {
int[] a = {7, 11, 8, 9, 5, 4, 100, 76};
for (int i = 0; i < a.length; i++) {
// j<i为有序区
for (int j = 0; j < i; j++) {
// 在有序区逐一判断大小，交换位置
if (a[i] < a[j]) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
System.out.println("排序后：");
for (int o : a) {
System.out.print(o+" ");
}
}
}
直接插入排序时间复杂度：O(N*N)
