数据结构代码——折半插入排序

折半插入排序的算法思想可以参考王道数据结构的书，建议先看书或者通过B站学习相关课程了解算法思想后再看代码。

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#define ElemType int
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef struct {
	ElemType* elem;
	ElemType len;
}SSTable;
//初始化待排序数组
void ST_Init(SSTable& ST, ElemType len) {
	ST.len = len;
	ST.elem = (ElemType*)malloc(sizeof(ElemType) * ST.len);
	srand(time(NULL));
	for (int i = 0; i < ST.len; i++) {
		ST.elem[i] = rand() % 100;
	}
}
//折半插入排序算法
void InsertSort(SSTable& ST) {
	ElemType i, j, low, high, mid, temp;
	for (i = 1; i < ST.len; i++) {
		//临时变量存储待排数据
		temp = ST.elem[i];
		low = 0;
		high = i - 1;
		//这一步是为了找到待排序元素最终的位置
		//最终的插入位置是high+1的地方
		while (low <= high) {
			mid = (low + high) / 2;
			if (ST.elem[mid] < temp) {
				low = mid + 1;
			}
			else {
				high = mid - 1;
			}
		}
		//将包括high+1位置的元素都向后移动
		for (j = i - 1; j >= high+1 ; j--) {
			ST.elem[j + 1] = ST.elem[j];
		}
		//最后将待排序元素插入high+1的位置即可
		ST.elem[high+1] = temp;
	}
}
//王道书上是将a[0]作为哨兵，这样待排序数组中第一个元素不参与排序
//第一个for循环里书上写的是i<=n，但是这样就会访问越界，我将它改为i<n
//可能王道书这样的写法在main函数中调用的时候会有措施保证不越界吧
//这个点是我没搞懂王道的地方，在直接插入排序中也有相同的问题
void InsertSort(ElemType a[], ElemType n) {
	int i, j, low, high,mid;
	for (i = 2; i < n; i++) {
		//a[0]作为哨兵存储待排数据
		a[0] = a[i];
		low = 1;
		high = i - 1;
		while (low <= high) {
			mid = (low + high) / 2;
			if (a[mid] < a[0]) {
				low = mid + 1;
			}
			else {
                high = mid - 1;
			}
		}
		for (j = i - 1; j >= high+1; j--) {
			a[j + 1] = a[j];
		}
		a[high + 1] = a[0];
	}
}
void print(SSTable ST) {
	for (int i = 0; i < ST.len; i++) {
		printf("%d ", ST.elem[i]);
	}
	printf("\n");
}
int main() {
	SSTable ST;
	ST_Init(ST, 10);
	print(ST);
	//我写的排序算法
	InsertSort(ST);
	//王道书上给的方法
	//InsertSort(ST.elem,ST.len);
	print(ST);
	return 0;
}

每次生成随机数进行排序，当然读者可以自己输入待排序的数据或者将数据固定下来。

如果想最后的结果按照逆序输出，可以修改打印函数或者修改排序算法。打印函数的修改可以参考快速排序的文章，快速排序。对于折半插入排序算法的修改更为简单，直接把排序算法中的if条件判断的小于号改为大于号即可。

运行结果截图：

采用我写的算法：

采用王道书上的算法：  上面数据也就是25不参与排序，而且输出数据中，第一个位置是忽略不看的，因为第一个位置被用作哨兵，当然可以修改输出函数不把第一个位置的数据输出。 

如果内容对你有帮助，关注我，给我点个小小的赞吧！

若内容有误，请指正并多多包容，谢谢。