当前位置：首页 > article >正文

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

article 2024/10/24 19:32:11

直接插入排序

直接插入排序（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;
		}
	}
}