1、插入排序的基本思想
从初始有序的子集合开始，不断地把新的数据元素插入到已排列有序子集合的合适位置，使得子集合中数据元素的个数不断增多，当子集合等于集合时，插入排序算法结束。常用的插入排序有直接插入排序和希尔排序两种。
2、直接插入排序
直接插入排序就是顺序地把待排序的数据元素按照其关键值的大小插入到已排序的数据元素子集的适当位置。子集合的数据元素个数从只有一个数据元素开始逐渐增大，当子集合大小最终和集合大小相同时，排序完毕。
假设待排序的n个数据元素存放在数组a中，初始时子集合a[0]已排好序，第一次循环准备把数据元素a[1]插入到已排好序的子集合中，这只需要比较a[0]和a[1]，如果a[0]小于或等于a[1]，则说明序列有序，否则将a[1]插入到a[0]之前，这样子集合的大小增的为2；第二次循环准备把数据元素a[2]插入到已排好序的子集合中，这需要比较a[2]和a[1]的值以确定是否需要把a[2]插入到a[1]之前，然后比较a[2]和a[0]，确认是否需要把a[2]插入到a[0]之前；这样的循环过程一直到a[n-1]插入完为止。这时的数据元素集合a[0]，a[1]，···，a[n-1]就全部排好序了。
如下图所示是直接插入排序的过程图。
2.1、直接插入排序的代码实现
void InsertSort() {
int a[] = {9, 3, 1, 4, 2, 7, 8, 6, 5};
int n = sizeof(a) / sizeof(a[0]);
for (int i = 0; i < n - 1; ++i) {
int temp = a[i + 1];
int j = I;
while (j > -1 && temp < a[j]) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
for (int k = 0; k < n; ++k) {
printf("%d ", a[k]);
}
}
2.2、直接插入排序的时间复杂度
直接插入排序算法的时间复杂度分析分为最好、最坏和随机三种情况。
- 最好情况是原始数据元素集合已全部排好序。这时算法中内层while循环的循环次数每次均为0，外层for循环中每次数据元素的比较次数均为1，数据元素的赋值语句执行次数均为2。因此整个排序过程中的比较次为n-1，赋值语句执行次数为2(n-1)。所以直接插入排序算法最好情况下的时间复杂度为
。
- 最坏情况是原始数据元素集合反序排列。这时算法内存while循环的循环次数每次均为i，整个外层for循环中的比较次数和赋值语句的执行次数（即移动次数）计算公式如下：
因此直接插入排序算法最坏情况的时间复杂度为。
- 如果原始数据元素集合大小的排序是随机的，则数据元素的期望比较次数和期望移动次数约为
。因此直接插入排序算法的期望时间复杂度为
。
3、希尔排序
希尔排序是把待排序的数据元素分成若干个小组，对同一个小组内的数据元素用直接插入法排序；小组的个数逐渐减少；当完成所有数据元素都在一个组内的排序后，排序过程结束。总结来说希尔排序是在分组概念上的直接插入排序，在不断减少组的个数时把原各个小组的数据元素插入到新组中的合适位置上。
如上图所示是希尔排序的过程。在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式。
- 初始增量gap=length/2=5,这意味着整个数组分为5组，分别为[9,4]，[1,8]，[2,6]，[5,3]，[7,5]。对这5组分别进行直接插入排序，结果如上图所示第一趟排序的结果所示。
- 然后缩小当量gap=5/2=2，数组被分为2组，分别为[4,2,5,8,5]和[1,3,9,6,7]
- 对这两组数据进行直接插入排序结果如上图第二趟排序后的结果所示。
- 缩小当量gap=2/2=1，数组分为1组，为[2,1,4,3,5,6,5,7,8,9]。
- 对这组数据进行直接插入排序得到的结果就是最后的排序结果。
3.1、希尔排序的代码实现
void shellSort() {
int arr[] = {9, 3, 1, 4, 2, 7, 8, 6, 5,10};
int length = sizeof(arr) / sizeof(arr[0]);//计算数组的长度
int gap = length / 2;//初始增量
while (gap > 0) {
for (int i = 0; i < gap; ++i) {//共有gap个小组
//组内直接插入排序，每次增加gap
for (int j = i; j < length - gap; j = j + gap) {
int tmp = arr[j + gap];
int k = j;
while (k > -1 && arr[k] > tmp) {
arr[k + gap] = arr[k];
k -= gap;
}
arr[k + gap] = tmp;
}
}
if (gap == 1) { break; }
gap = gap / 2;
}
for (int k = 0; k < length; ++k) {
printf("%d ", arr[k]);
}
}
3.2、希尔排序的时间复杂度
比较希尔排序和直接插入排序两个算法的代码，希尔排序算法比直接插入排序算法要复杂些，但是分析希尔排序算法中四重循环次数可以发现，外面两重的循环次数都很小，并且当增量递减，小组变大时，小组内的数据元素已基本有序。越接近有序时，直接插入排序算法的时间效率就越好。因此希尔排序算法的时间复杂度较直接插入排序算法的时间复杂度改善很多。
希尔排序算法的时间复杂度分析比较复杂，实际所需要的时间取决于各次排序时增量的取值。希尔排序算法的时间复杂度约为。希尔排序算法的空间复杂度为
，由于希尔排序是按照增量分组进行排序的，所以希尔排序算法是一种不稳定的排序算法。
