1.直接插入排序（Straight Insert Sort）
将一个记录插入到已经排序好的有序表中，从而得到一个新的、记录数增加1的有序表。即：先将第一个记录看成有序表，然后从第二个记录逐一进行插入，直至整个序列有序为止。
- 直接插入排序示例：
第一排为初始表，斜体加粗记录为有序表，有序表后加黑记录为待插入记录。
| 外层循环 | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| i = 1 | 23 | 15 | 30 | 1 | 27 | 16 | 54 | 56 | 28 | 10 |
| i = 2 | 15 | 23 | 30 | 1 | 27 | 16 | 54 | 56 | 28 | 10 |
| i = 3 | 15 | 23 | 30 | 1 | 27 | 16 | 54 | 56 | 28 | 10 |
| i = 4 | 1 | 15 | 23 | 30 | 27 | 16 | 54 | 56 | 28 | 10 |
| i = 5 | 1 | 15 | 23 | 27 | 30 | 16 | 54 | 56 | 28 | 10 |
| i = 6 | 1 | 15 | 16 | 23 | 27 | 30 | 54 | 56 | 28 | 10 |
| i = 7 | 1 | 15 | 16 | 23 | 27 | 30 | 54 | 56 | 28 | 10 |
| i = 8 | 1 | 15 | 16 | 23 | 27 | 30 | 54 | 56 | 28 | 10 |
| i = 9 | 1 | 15 | 16 | 23 | 27 | 28 | 30 | 54 | 56 | 10 |
| i = 10 | 1 | 10 | 15 | 16 | 23 | 27 | 28 | 30 | 54 | 56 |
- 直接插入排序代码示例：
private static void StraightInsertSort(int a[], int n){
for (int i = 1; i < n; i++)
{
int tmp = a[i];
int j = i - 1;
while(j >= 0)
{
if (a[j] > tmp)
{
a[j+1] = a[j];
a[j] = tmp;
j--;
}
else break;
}
}
}
- 效率
时间复杂度为O(n^2)
其他插入排序有二分插入排序、2-路插入排序。*
2.希尔排序（Shell's Sort）
待续...
