1.直接插入排序（Straight Insert Sort）

将一个记录插入到已经排序好的有序表中，从而得到一个新的、记录数增加1的有序表。即：先将第一个记录看成有序表，然后从第二个记录逐一进行插入，直至整个序列有序为止。

• 直接插入排序示例：

第一排为初始表，斜体加粗记录为有序表，有序表后加黑记录为待插入记录。

• 直接插入排序代码示例：

    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）

待续...