每日回顾：简单用C写 直接插入排序、希尔排序

直接插入排序

直接插入排序（Straight Insertion Sort）是一种简单直观的排序算法。它的基本思想是将未排序的数据插入到已排序的序列中。

大致思想：

使用 2 个数组下标指针 end、i 模拟数组元素逐个进行插入的过程；

i 每递增一次，代表数组新插入一个元素。在这次循环中，end 将逐渐递减比较已有元素与新插入元素的大小，

如果新插入元素小 ：直接向后挪动覆盖（在此之前，被覆盖的元素已提前使用 tmp 存储），最后 end 会停在合适位置的前一个下标处，将 tmp 放回去

如果新插入元素大：升序情况下，无须再进行比较

//直接插入排序
void InsertSort(int* a, int n) {
	//从第二个元素插入开始
	for (int i = 1; i < n; i++) {
		int tmp = a[i];
		int end = i - 1;
		while (end >= 0) {
			//升序
			if (a[end] > tmp) {
				//挪动覆盖之前，保存 a[i]
				a[end + 1] = a[end];
				end--;
			}
			else {	//如果 a[end] 小于等于 tmp，说明之前的都小于等于 tmp
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

时间复杂度

直接插入排序的时间复杂度，取决于数组长度和元素的交换次数；

前者消耗的时间避免不了，那么如果数组本来有序，无须比较的情况下，时间复杂度为 O(n)；

如果数组是逆序，时间复杂度为 O(n^2)

空间复杂度

原地修改，空间复杂度 O(1)

稳定性

直接插入排序没有元素换来换去的情况，稳定

希尔排序

希尔排序（Shell Sort）是插入排序的一种更高效的改进版本。希尔排序由Donald Shell于1959年提出，它通过将原始数据分成多个子序列，分别对每个子序列进行直接插入排序，从而提高效率。

大致思想：

预排序-->接近有序

增量 gap ：将待排序数据按照间隔 gap 个元素，分成多个子序列，对子序列进行直接插入排序

当 gap 增量逐渐递减到 1 ，就是直接插入排序；在已经接近有序的情况下，直接插入排序的效率还是比较好的

版本一：

//希尔排序1
void ShellSort_1(int* a, int n) {
	int gap = n;
	//控制 gap 递减
	while (gap > 1) {	//不能用 gap >= 1 ，否则会死循环
		gap = gap / 3 + 1;	//保证 gap 最后一次一定是 1
		for (int j = 0; j < gap; j++) {	//每次循环排好一组 gap 的数据
			//直接插入排序
			for (int i = j; i < n - gap; i += gap) {
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0) {
					if (a[end] > tmp) {
						a[end + gap] = a[end];
						end -= gap;
					}
					else {
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}
	}
}

版本二：

//希尔排序2
void ShellSort_2(int* a, int n) {
	int gap = n;
	while (gap > 1) {
		gap = gap / 3 + 1;
		//多组数据并排
		for (int i = 0; i < n - gap; i++) {
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0) {
				if (a[end] > tmp) {
					a[end + gap] = a[end];
					end -= gap;
				}
				else {
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

区别

版本一、二的区别在于，版本一是将每组子序列独立地排序；版本二则是比较巧妙，多组子序列并行排序，只需要按顺序遍历一遍数组就可以

时间复杂度

希尔排序的时间复杂度取决于 gap 增量的大小，要详细分析很困难，了解即可

最好情况：当增量序列选择得当时，时间复杂度可以达到 O(n*log⁡n)

平均情况：时间复杂度通常在 O(n^1.3)到 O(n^1.7)之间

最坏情况：时间复杂度为 O(n^2)

空间复杂度

原地修改，空间复杂度 O(1)

稳定性

不稳定，因为可能会有相同元素处于不同的子序列中，发生交换时可能导致不稳定