文章目录 C语言实现折半插入排序一、动态数组实现即输即排1.定义动态数组2.初始化动态数组3.增加动态数组长度4.排序算法5.实时输入数值并排序 二、不带哨兵的数组折半插入排序三、带哨兵的数组折半插入排序项目完整代码运行效果图
一、动态数组实现即输即排 1.定义动态数组 #define InitSize 25//定义动态顺序表typedef struct { int *data; int MaxSize; int length;} DSqList; 2.初始化动态数组 //初始化动态顺序表void InitList(DSqList &L) { //用malloc函数申请一片连续的存储空间 L.data = (int *) malloc(InitSize * sizeof(int)); //数组中包含有效数据个数 L.length = 0; //数组最大长度 L.MaxSize = InitSize;} 3.增加动态数组长度 //增加动态数组长度void IncreaseSize(DSqList &L, int len) { int *p = L.data; //重新申请符合长度的连续空间 L.data = (int *) malloc((L.MaxSize + len) * sizeof(int)); //将原空间里的数据复制到新的区域 for (int i = 0; i < L.length; ++i) { L.data[i] = p[i]; } //顺序表的最大长度增加 len L.MaxSize += len; //释放原来的顺序表所占的空间 free(p);} 4.排序算法 //根据输入实时折半插入排序算法bool InsertAndSort(DSqList &L, int e) { if (L.length >= L.MaxSize) //判断数组是否已满 { printf("数组已满，插入失败，请增加长度后再插入！"); return false; } else if (L.length == 0) { //是否为空数组 L.data[0] = e; L.length++; return true; } else { int i, low, high, mid; low = 0; //设置折半查找范围 high = L.length - 1; while (low <= high) { //折半查找（默认递增有序） mid = (low + high) / 2; //取中间点 if (L.data[mid] > e) high = mid - 1; //查找右半子表 else low = mid + 1; //查找左半子表 } for (i = L.length - 1; i >= high + 1; --i) L.data[i + 1] = L.data[i]; //依次后移元素，空出插入位 L.data[high + 1] = e; //插入 L.length++; return true; }} 5.实时输入数值并排序 //根据输入值进行折半插入排序void CreateList(DSqList &L) { int e; scanf("%d", &e); getchar(); while (e != -1) { InsertAndSort(L, e); printf("请继续输入下一个待插入值（如果结束请输入-1）："); scanf("%d", &e); getchar(); }} 二、不带哨兵的数组折半插入排序 //对已存在的数组进行折半插入排序（不带哨兵）void InsertSort_N(int arr[], int len) { int i, j, temp, low, high, mid; for (i = 1; i < len; ++i) { //依次将数组中arr[2]~arr[n]插入前面已经排序序列 temp = arr[i]; //将arr[i]暂存在temp中 low = 0; //设置折半查找范围 high = i - 1; while (low <= high) { //折半查找（默认递增有序） mid = (low + high) / 2; //取中间点 if (arr[mid] > temp) high = mid - 1; //查找右半子表 else low = mid + 1; //查左半子表 } for (j = i - 1; j >= high + 1; --j) arr[j + 1] = arr[j]; //依次后移元素，空出插入位 arr[high + 1] = temp; //插入 } 三、带哨兵的数组折半插入排序 //对已存在的数组进行折半插入排序（带哨兵）void InsertSort_Y(int arr[], int len) { int i, j, low, high, mid; for (i = 2; i < len; ++i) { //依次将数组中arr[2]~arr[n]插入前面已经排序序列 arr[0] = arr[i]; //将arr[i]复制到哨兵点arr[0] low = 1; //设置折半查找范围 high = i - 1; while (low <= high) { //折半查找（默认递增有序） mid = (low + high) / 2; //取中间点 if (arr[mid] > arr[0]) high = mid - 1; //查找右半子表 else low = mid + 1; //查左半子表 } for (j = i - 1; j >= high + 1; --j) arr[j + 1] = arr[j]; //依次后移元素，空出插入位 arr[high + 1] = arr[0]; //插入 }} 项目完整代码 //插入排序————折半插入排序（稳定，空间复杂度为O(1)，时间复杂度为O(n^2)）#include <stdio.h>#include <stdlib.h>#define InitSize 25//定义动态数组typedef struct { int *data; int MaxSize; int length;} DSqList;//初始化动态数组void InitDSqList(DSqList &L) { //用malloc函数申请一片连续的存储空间 L.data = (int *) malloc(InitSize * sizeof(int)); //数组中包含有效数据个数 L.length = 0; //数组最大长度 L.MaxSize = InitSize;}//增加数组长度void IncreasrSize(DSqList &L, int len) { int *p = L.data; //重新申请符合长度的连续空间 L.data = (int *) malloc((L.MaxSize + len) * sizeof(int)); //将原空间里的数据复制到新的区域 for (int i = 0; i < L.length; ++i) { L.data[i] = p[i]; } //顺序表的最大长度增加 len L.MaxSize += len; //释放原来的顺序表所占的空间 free(p);}//根据输入实时折半插入排序算法bool InsertAndSort(DSqList &L, int e) { if (L.length >= L.MaxSize) //判断数组是否已满 { printf("数组已满，插入失败，请增加长度后再插入！"); return false; } else if (L.length == 0) { //是否为空数组 L.data[0] = e; L.length++; return true; } else { int i, low, high, mid; low = 0; //设置折半查找范围 high = L.length - 1; while (low <= high) { //折半查找（默认递增有序） mid = (low + high) / 2; //取中间点 if (L.data[mid] > e) high = mid - 1; //查找右半子表 else low = mid + 1; //查找左半子表 } for (i = L.length - 1; i >= high + 1; --i) L.data[i + 1] = L.data[i]; //依次后移元素，空出插入位 L.data[high + 1] = e; //插入 L.length++; return true; }}//根据输入值进行折半插入排序void CreateList(DSqList &L) { int e; scanf("%d", &e); getchar(); while (e != -1) { InsertAndSort(L, e); printf("请继续输入下一个待插入值（如果结束请输入-1）："); scanf("%d", &e); getchar(); }}//对已存在的数组进行折半插入排序（不带哨兵）void InsertSort_N(int arr[], int len) { int i, j, temp, low, high, mid; for (i = 1; i < len; ++i) { //依次将数组中arr[2]~arr[n]插入前面已经排序序列 temp = arr[i]; //将arr[i]暂存在temp中 low = 0; //设置折半查找范围 high = i - 1; while (low <= high) { //折半查找（默认递增有序） mid = (low + high) / 2; //取中间点 if (arr[mid] > temp) high = mid - 1; //查找右半子表 else low = mid + 1; //查左半子表 } for (j = i - 1; j >= high + 1; --j) arr[j + 1] = arr[j]; //依次后移元素，空出插入位 arr[high + 1] = temp; //插入 }}//对已存在的数组进行折半插入排序（带哨兵）void InsertSort_Y(int arr[], int len) { int i, j, low, high, mid; for (i = 2; i < len; ++i) { //依次将数组中arr[2]~arr[n]插入前面已经排序序列 arr[0] = arr[i]; //将arr[i]复制到哨兵点arr[0] low = 1; //设置折半查找范围 high = i - 1; while (low <= high) { //折半查找（默认递增有序） mid = (low + high) / 2; //取中间点 if (arr[mid] > arr[0]) high = mid - 1; //查找右半子表 else low = mid + 1; //查左半子表 } for (j = i - 1; j >= high + 1; --j) arr[j + 1] = arr[j]; //依次后移元素，空出插入位 arr[high + 1] = arr[0]; //插入 }}int main() { DSqList L; InitDSqList(L); //根据实时输入值进行直接快速排序 printf("请继续输入第一个待插入值（如果结束请输入-1）："); CreateList(L); //将已排序的结果逐个输出 printf(" 根据输入的值进行折半插入排序结果为："); for (int i = 0; i < L.length; ++i) { printf("%d ", L.data[i]); } printf("n"); //不带哨兵的数组进行快排 int arr_n[] = {49, 38, 65, 97, 76, 13, 27, 49}; int len = sizeof(arr_n) / sizeof(int); InsertSort_N(arr_n, len); //将已排序的结果逐个输出 printf("不带哨兵的数组进行折半插入排序结果为："); for (int i = 0; i < len; ++i) { printf("%d ", arr_n[i]); } printf("n"); //带哨兵的数组进行快排 int arr_y[] = {0, 49, 38, 65, 97, 76, 13, 27, 49}; len = sizeof(arr_y) / sizeof(int); InsertSort_Y(arr_y, len); //将已排序的结果逐个输出 printf(" 带哨兵的数组进行折半插入排序结果为："); for (int i = 1; i < len; ++i) { printf("%d ", arr_y[i]); } return 0; 运行效果图 //不带哨兵的数组 int arr_n[] = {49, 38, 65, 97, 76, 13, 27, 49};//带哨兵的数组 int arr_y[] = {0, 49, 38, 65, 97, 76, 13, 27, 49};