颜文岩 刘朝元 吴彩莲

摘要：在排序中分为内排序和外排序，而我们今天要做的插入排序在排序过程中，整个表都放在内存中处理，排序时不涉及数据内存与外存之间的交换，因此也被称为内排序。插入排序的基本思想是每次将一个待排序的元素按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部元素插入完为止。

插入排序的分类

插入排序的方法非常之多，今天我们主要研究这三种：

第一种：直接插入排序;

第二种：折半插入排序;

第三种：希尔排序;

...

直接插入排序

假使我们将所有待排序的元素放在一个一维数组a[]中，那么在排序过程中会产生两个区域。一部分是已经经过直接插入排序的区域，该部分区域内的元素有序排列，但相对于整体来说只能认为是局部有序;另一部分是还未进行排序的区域，该部分区域内的元素无序排列。这种方法也被叫做增量发，它使有序区每次增加一个元素，只有当最后一个元素也进行排序后整个数组才是全局有序的。

但是由于直接插入排序是每一个元素都要与之前进入有序区的元素进行比较，随着有序区元素的增多，计算量也在不断的增大。算法的最小时间复杂度为O（n），算法的最大时间复杂度为O（n2），算法的平均时间复杂度为O（n2）

但值得一提的是——直接插入排序算法中只使用了三个辅助变量因此可以说是一个就地排序算法。

折半插入排序

与直接插入排序一样，折半插入排序也是将所有数据放入一个一维数组a[]中，并在排序过程中将所有元素分为有序区与无序区。……