已排序区
待排序区
?
算法说明直接插入排序（Straight Insertion Sort）的基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已排好序的子序列中的适当位置，直到全部记录插入完成为止。
for (i = 1; i < n; i++) {
key = a[i];
j = i - 1;
while (j >= 0 && a[j] > key) {
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
时间复杂度 O(n²) 空间复杂度 O(1) 稳定排序