算法之排序-插入排序

排序算法之插入排序

对大小为n的array进行插入排序，从i = 1到n-1的循环,选择元素arr [i]并将其插入到排序数组arr [0 … i-1]中。

• 时间复杂度: $O(n^2)$
• 辅助空间: $O(1)$

arr[] = 12，11，13，5,6
1. i = 1。由于11小于12，移动12和12之前插入11 
11，12，13，5,6

2. i = 2 13将保持不变因为11，12 均小于13
11，12，13，5,6

3. i = 3. 5将移至开头，11至13之间的所有其他元素将移动到下一个位置。
5，11，12，13，6

4. i = 4. 6将移动到5之后位置，而11到13之间的元素将移动到下一个位置。
5,6,11,12,13

代码实现见InsertionSort

对插入排序的优化-二分插入排序

我们可以使用二分搜索来减少插入排序中的比较次数。时间复杂度: $O(n*logn)$, 辅助空间: $O(1)$。

• 最好情况：每次插入的位置k都是已序数组的最后的位置，则无需再执行移位赋值操作。
• 最坏情况：每次插入的位置k都是已序数组的最前的位置，则整个已排序数组需要移位赋值，最坏时间复杂度仍是 $O(n^2)$

代码实现见BinaryInsertSort

对插入排序的优化-希尔排序

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序为什么会快？

希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。