插入排序(直接插入，折半插入，希尔排序)

学习时间2022.12.17

插入排序

基本概念

直接插入排序

• 要理解直接插入排序看这篇解学武插入排序算法及C语言实现
• 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
• 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
• 示意图
  

折半插入排序

• 要理解折半插入排序看这篇解学武折半插入排序算法（折半排序算法）
• 折半插入排序,是在直接插入排序的基础上进行的。直接插入排序把数组分为了已排序和待插入两部分，折半插入排序是在已排序的数组中进行折半查找操作，找到最新要插入元素应该在的位置。

希尔排序

• 要理解希尔排序看这篇博客园dreamcatcher-cx的文章-图解排序算法(二)之希尔排序
• 希尔排序是使用增量将数组元素分为若干组，对每组进行插入排序，然后依次缩减增量，直到增量为1，此时一般只需微调即可

代码实现

基本数据结构

typedef int ElemType;

typedef struct {
	ElemType* elem;//整型指针
	int TableLen;//动态数组元素个数
}SSTable;

基本函数实现

void ST_init(SSTable& ST, int len) {
	ST.TableLen = len + 1;//多申请一个空间，第一个空间用于存储插入排序时要交换的元素值，因为下标在变化，不使用哨兵的话代码会更复杂一些
	//ST.elem = (ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
	ST.elem = (ElemType*)calloc(ST.TableLen, sizeof(ElemType));
	//初始化随机数发生器
	srand(time(NULL));
	//输出0-100的ST.TableLen个随机数
	for (int i = 0; i < ST.TableLen; i++)
	{
		ST.elem[i] = rand() % 100;
	}
}

void swap(ElemType& a, ElemType& b) {
	int temp;
	temp = a;
	a = b;
	b = temp;
}

void ST_print(SSTable ST) {
	for (int i = 0; i < ST.TableLen; i++) {
		printf("%3d", ST.elem[i]);
	}
	printf("\n");
}

直接插入排序和对应main函数

//直接插入排序
void InsertSort(ElemType A[], int n) {
	int i, j;
	for (i = 2; i <= n; i++)
	{
		if (A[i] < A[i - 1])
		{
			A[0] = A[i];
			for (j = i - 1; A[0] < A[j]; j--)
			{
				A[j + 1] = A[j];
			}
			A[j+1] = A[0];
		}
	}
}

int main() {
	SSTable ST;
	ST_init(ST, 10);
	ElemType A[] = { 32,45,11,324,32,59,90,85,1,49 };
	//memcpy(ST.elem, A, sizeof(A));
	ST_print(ST);
	InsertSort(ST.elem, 10);
	ST_print(ST);
}

折半插入排序和对应main函数

//折半插入排序
void MidInsertSort(ElemType A[], int n) {
	int low, high, mid, i, j, temp;
	for (i = 2; i <= n; i++)
	{
		low = 1;
		high = i - 1;
		temp = A[i];
		while (low <= high)
		{
			mid = (low + high) / 2;
			if (temp < A[mid])
			{
				high = mid - 1;
			}
			else
			{
				low = mid + 1;
			}
		}
		for (j = i; j > low; j--)
		{
			A[j] = A[j - 1];
		}
		A[low] = temp;
	}
}
int main() {
	SSTable ST;
	ST_init(ST, 10);
	ElemType A[] = { 32,45,11,324,32,59,90,85,1,49 };
	//memcpy(ST.elem, A, sizeof(A));
	ST_print(ST);
	MidInsertSort(ST.elem, 10);
	ST_print(ST);
}

希尔排序和对应main函数

//希尔排序(交换法)
void ShellSort1(ElemType A[], int n) {
	int gap,i;
	for (gap = n / 2; gap >= 1; gap /= 2)
	{
		for (i = gap + 1; i <= n; i++)
		{
			int j = i;
			while (j - gap >= 1 && A[j] < A[j - gap])
			{
				swap(A[j], A[j - gap]);
				j -= gap;
			}
			
		}
	}
}

//希尔排序(移动法)
void ShellSort2(ElemType A[], int n) {
	int gap, i;
	for (gap = n / 2; gap >= 1; gap /= 2)
	{
		for (i = gap + 1; i <= n; i++)
		{
			int j = i;
			int temp = A[j];
			while (j - gap >= 1 && temp < A[j - gap])
			{
				A[j] = A[j - gap];
				j -= gap;
			}
			A[j] = temp;
		}
	}
}

int main() {
	SSTable ST;
	ST_init(ST, 10);
	ElemType A[] = { 32,45,11,324,32,59,90,85,1,49 };
	//memcpy(ST.elem, A, sizeof(A));
	ST_print(ST);
	ShellSort2(ST.elem, 10);
	ST_print(ST);
}