插入排序⁻⁻⁻⁻直接插入排序希尔排序

引言

所谓的排序，就是使一串记录按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

常见的排序算法有：

今天我们主要学习插入排序的直接插入排序和希尔排序。

直接插入排序

什么是直接插入排序？

直接插入排序其实是一种很简单的排序算法哦。它就像我们平时整理扑克牌一样，一张一张地来，把每一张牌都插到已经排好序的部分里面，直到全部都排好。

我们再通过一个动图理解一下：

思路

从第二个元素始，逐一遍历数组。
当前元素与前序已排序元素逐一比较，找到插入位置。
插入当前元素至正确位置，前序元素后移。
重复上述步骤，直至数组全排序。

代码

void insertSort(int* a, int n)
{
	for (int i = 1; i < n; i++) {
		int curIndex = i - 1, tmp = a[i];
		while (curIndex >= 0) {
			if (tmp < a[curIndex]) {
				a[curIndex + 1] = a[curIndex];
				--curIndex;
			}
			else {
				break;
			}
		}
		a[curIndex + 1] = tmp;
	}
}

时间复杂度

从代码我们可以看出，直接插入排序的时间复杂度是 O(n²)，在数据比较少或者已经部分有序的情况下，它的性能还是不错的。

希尔排序

什么是希尔排序？

希尔排序，又称为缩小增量排序，是直接插入排序的一种更高效的改进版本。

前面我们知道，直接插入排序比最差的条件下时间复杂度可以达到O(n²)，但是在部分有序的情况下，它的性能还是不错的。

希尔排序的基本思想是预排序，即先将数组内的数据变得部分有序，最后再通过直接插入排序将部分有序的数组进组排序。

那它具体是如何实现预排序的呢？接下来我们会进行讲解。

讲解与分析

接下来，我们具体来通过一个例子来理解一下希尔排序：先将整个待排序数组分割成若干个子序列（也称为分组），使得每个子序列中的元素在原数组中的位置间隔gap，然后对每个子序列分别进行直接插入排序，这样可以使原数组变得部分有序。我们一起来看一下：

原数组：int a[]=｛9,1,2,5,7,4,8,6,3,5｝;

接下来我们按照间隔（gap）为3时将原数组进行升序排序，什么意思呢？即下标为0，3，6，9的树为一组进行排序，对应上面的数组也就是将9，5，8，5进行排序：

tmp之前的数据已经按升序排序，开始进入下一轮排序：

tmp之前的数据已经按升序排序，开始进行下一轮排序：

如果我们让gap为2，原数组排序下来会是这样的：

我们发现，gap越大，排序就越快，但是越不接近有序；gap越小，排序就越慢，但是越接近有序。

当gap等于1就是直接插入排序，gap大于1就是预排序。

那我们可以先让gap初始化为较大的数，我们可以逐渐缩小gap，再对新的子序列进行直接插入排序，直到最后增量减至1，此时整个数组几乎已经有序，最后再进行一次直接插入排序即可完成排序。

这里补充说明一下gap的初始值，一般初始化为数组长的一半或三分之一。如果是数组长度的二分之一，每次gap就是按照gap/=2去缩小；如果是数组长的三分之一，每次gap就是按照gap=gap/3+1去缩小（为什么不是gap/=3呢？我们要考虑到两个整数相除时，最后结果会向下取整，如果数组长度n=6，第一次排序时gap=n/3=2，第二次排序时gap/=3就是2/3=0，那这样下去永远都无法让gap==1，也就无法进行直接插入排序。所以应该是gap=gap/3+1）。

代码

void shellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1) {
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i += gap) {
			int curIndex = i, tmp = a[i + gap];
			while (curIndex >= 0) {
				if (tmp < a[curIndex]) {
					a[curIndex + gap] = a[curIndex];
					curIndex -= gap;
				}
				else {
					break;
				}
			}
			a[curIndex + gap] = tmp;
		}
	}
	
}

时间复杂度

分析

最外层循环：控制间隔（gap）的变化，通常从数组长度n开始，每次除以一个常数（如3）并加1，直到gap为1。此循环的时间复杂度为O(logn)。
内层循环（这种分析方式存在一定不严谨性）：包括两层循环，一层用于遍历数组，另一层用于在分组内进行插入排序。for循环以gap为步长遍历数组，因此其迭代次数为n / gap次。在每次for循环的迭代中，while循环负责将当前元素（位于i + gap位置）插入到其前面gap间隔的有序子序列中。最坏情况下，这个插入操作需要比较和移动gap个元素（但实际上由于分组的存在，通常不会达到这么多）。然而，对于时间复杂度的分析，我们可以认为每次while循环至多执行O(gap)次操作，但在整个for循环中，由于分组的存在，每个元素至多被比较和移动一次。因此，对于每个固定的gap值，内层循环（包括for和while）的总时间复杂度为O(n)。