• 介绍
  插入排序法是将数组中的元素，逐一与已排序的数据作比较，再将该数组元素插入适当的位置。
• 演示
  代码如下：

private static void insertSort() {
    int data[] = {6, 4, 8, 1, 3, 7, 2, 9, 5};
    int i, j, tmp;
    for (i = 1; i < data.length; i++) {
        tmp = data[i];
        j = i - 1;
        while (j >= 0 && tmp < data[j]) {
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = tmp;
    }
}

演示结果：

• 分析

1. 最坏及平均情况需比较n(n-1)/2次；时间复杂度为O(n²)，最好情况时间复杂度为O(n)；
2. 是稳定排序法；
3. 只需一个额外的空间，所以空间复杂度为最佳；
4. 此排序法适用于大部分数据已经过排序或已排序数据库新增数据后进行排序的情况；
5. 插入排序法会造成数据的大量搬移，所以建议在链表上使用。

其他排序：选择排序、冒泡排序、希尔排序、快速排序、基数排序