插入排序

疫情期间，大家都闲坏了吧？应该没少打扑克牌吧。设想一下，你从牌堆中摸牌的时候，大概率是乱序的。那么你是怎么样把乱序的牌整理成有序的呢？

首先你会假定第一张牌是有序的，然后把后面的牌不断地插到前面的有序牌里的合适位置，最后，牌就从无序的变成有序的了。

那么，插入排序也是一样的道理，看下面动画，蓝色的代表乱序，绿色代表有序，橙色的代表正在比较。

代码实现如下：

//C
void sort(int arr[])
{
    for (int i = 1; i < sizeof(arr)/sizeof(arr[0]); i++)
    {
        int value = arr[i];
        for (j = i - 1; j >= 0; j--)
        {
            if (arr[j] > value)
            {
                arr[j+1] = arr[j]; //移动数据
            }
            else
            {
                break;
            }
        }
        arr[j+1] = value; //插入数据
    }
}

//Java
public static void sort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
        int value = arr[i];
        int j = 0;//插入的位置
        for (j = i-1; j >= 0; j--) {
            if (arr[j] > value) {
                arr[j+1] = arr[j];//移动数据
            } else {
                break;
            }
        }
        arr[j+1] = value; //插入数据
    }
}

#Python
def sort(arr):
    for i in range(1, len(arr)):
        value = arr[i]
        for j in range(0, i-1, -1):
            if arr[j] > value:
                arr[j+1] = arr[j];
            else:
                break
        arr[j+1] = value

插入排序是稳定排序。

这种算法感觉比冒泡什么的快一些（实际上时间复杂度为$O_{(n^2)}$，但受数据影响较大），但是如果数据量很大的话，那么这样挨个比较的话，效率就非常低了。

因此，人们就想出一个办法：使用二分法来查找。

也就是说，当后面的数据想要插入前面的有序数列的时候，不是挨个挨个比较，而是直接和有序数列的中间值进行比较，假设大于中间值，就和中间值到末尾的一段的数列的中间值进行比较，一直持续下去直到找到正确的位置。这样在理想情况下可以节省很多时间。

但是在数据分布比较散的情况下，有时候还是需要移动很多位。那么这种情况下，人们就开始着手改进插入排序，其中希尔改进的插入排序最为出名，也就是希尔排序。

希尔排序

希尔排序改进了插入排序的缺点，可以实现元素的跳跃移动。

希尔排序又叫做缩小增量排序，图中的Gap就是增量的意思。所谓增量，可以理解为一个跨度。插入排序中广为诟病的依次移动，当加上了跨度之后就可以实现跳跃移动。而每一轮排完之后跨度都会减小，直到跨度为1，就完成了排序。实际上，跨度为1的时候就是普通的插入排序。只不过经过了前面的洗礼之后，数据已经基本变得有序了，最后一轮的插入只是很简单地完善一下而已。

代码实现如下：

void shellSort( long int array[], int length)
{
    int i;
    int j;
    int k;
    int gap;    //gap是分组的步长
    long int temp;   //希尔排序是在直接插入排序的基础上实现的,所以仍然需要哨兵
    for(gap=length/2; gap>0; gap=gap/2)
    {
        //以GAP为间隔分组
        for(i=0; i<gap; i++)
        {
            /*
             每一组做插入排序
             */
            for(j=i+gap; j<length; j=j+gap)
            {
                //如果当前元素比这一组中的前一个元素要小
                if(array[j] < array[j - gap])
                {
                    //记录当前这个更小的元素 temp
                    temp = array[j];    //哨兵
                    k = j - gap;
                    //把这一组中之前所有比temp小的元素都往后挪一个位置
                    while(k>=0 && array[k]>temp)
                    {
                        array[k + gap] = array[k];
                        k = k - gap;
                    }
                    //把挪出来的空位，放入temp
                    array[k + gap] = temp;
                }
            }
        }
    }
}

//Java
public static void shell_sort(int[] arr) {
    int length = arr.length;
    //区间
    int gap = 1;
    while (gap < length) {
        gap = gap * 3 + 1;
    }
    while (gap > 0) {
        for (int i = gap; i < length; i++) {
            int tmp = arr[i];
            int j = i - gap;
            //跨区间排序
            while (j >= 0 && arr[j] > tmp) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = tmp;
        }
        gap = gap / 3;
    }
}

#Python
def shell_sort(arr):
	gap = len(arr)//3 + 1
	while gap > 0:
		for i in range(gap):
			for j in range(i + gap, len(arr), gap):
				if arr[j] < arr[j - gap]:
					temp = arr[j]
					k = j - gap
					while k >= 0 and arr[k] > temp:
						arr[k + gap] = arr[k]
						k -= gap
					arr[k + gap] = temp
		if gap == 1:
			break
		gap = gap//3 + 1

至于这个增量gap到底该取多少，目前没有定论。最初shell提出取$gap=\frac{n}{2}$向下取整，gap /= 2向下取整，直到$gap=1$。但由于直到最后一步，在奇数位置的元素才会与偶数位置的元素进行比较，这样使用这个序列的效率会很低。后来Knuth提出取$gap = n\mid 3 +1$还有人提出都取奇数为好，也有人提出gap互质为好。应用不同的序列会使希尔排序算法的性能有很大的差异。

最后，希尔排序是一个不稳定排序，时间复杂度为$O_{(n^{1.3})}$。