目录
概要
整体架构流程
技术名词解释
代码实现
1、直接插入排序
2、折半插入排序
3、希尔排序
小结
概要
插入排序是一种简单直观的排序算法，适用于小规模数据或部分有序的数据集。它的工作原理类似于整理扑克牌，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
整体架构流程
插入排序的基本流程如下：
-
初始化：从第二个元素开始，假设第一个元素已经是有序的。
-
比较与插入：将当前元素与已排序部分的元素从后向前比较，找到合适的位置插入。
-
重复：重复上述步骤，直到所有元素都被排序。
技术名词解释
-
直接插入排序：最基本的插入排序，逐个比较并插入。
-
折半插入排序：在查找插入位置时使用二分查找，减少比较次数。
-
希尔排序：通过分组进行插入排序，逐步缩小分组间隔，最终完成排序。
代码实现
这里有三种实现方式，分别为直接插入排序、折半插入排序和希尔排序，其中main函数定义了一个测试数组，调用插入排序函数并输出结果。代码的每一步操作都有详细的注释。
1、直接插入排序
#include <stdio.h>
#include <stdlib.h>typedef struct SqList {int* arr;int length;
} SqList;// 直接插入排序
void insertSort(SqList list) {// 两个计数器int i = 0;int j = 0;for (i = 2; i <= list.length; i++) {// 检查是否需要排序if (list.arr[i] < list.arr[i - 1]) {list.arr[0] = list.arr[i]; // 复制为哨兵for (j = i - 1; list.arr[j] > list.arr[0]; j--) {list.arr[j + 1] = list.arr[j]; // 后移元素}list.arr[j + 1] = list.arr[0]; // 插入到正确位置}}
}int main() {// 初始化数据SqList list;list.length = 10;list.arr = calloc(list.length + 1, sizeof(int));// 输入int i = 0;for (i = 1; i <= list.length; i++) {scanf("%d", list.arr + i);}insertSort(list); // 排序// 输出for (i = 1; i <= list.length; i++) {printf("%d ", list.arr[i]);}return 0;
}2、折半插入排序
#include <stdio.h>
#include <stdlib.h>typedef struct SqList {int* arr;int length;
} SqList;// 折半插入排序
void insertSort(SqList list) {// 两个计数器int i = 0;int j = 0;for (i = 2; i <= list.length; i++) {// 检验是否需要排序if (list.arr[i - 1] > list.arr[i]) {list.arr[0] = list.arr[i]; // 复制为哨兵int left = 1;int right = list.length;int mid = (right - left) / 2 + left;// 寻找要插入的位置while (left <= right) {mid = (right - left) / 2 + left;if (list.arr[0] > list.arr[mid]) {left = mid + 1;}else{right = mid - 1;}}// 插入操作for (j = i - 1; j > right + 1; j--) {list.arr[j + 1] = list.arr[j]; // 后移元素}list.arr[right + 1] = list.arr[0]; // 插入到正确位置}}
}int main() {// 初始化数据SqList list;list.length = 10;list.arr = calloc(list.length + 1, sizeof(int));// 输入int i = 0;for (i = 1; i <= list.length; i++) {scanf("%d", list.arr + i);}insertSort(list); // 排序// 输出for (i = 1; i <= list.length; i++) {printf("%d ", list.arr[i]);}return 0;
}3、希尔排序
#include <stdio.h>
#include <stdlib.h>typedef struct SqList {int* arr;int length;
} SqList;// 每一趟的操作
void shellInsert(SqList list, int dk) {// 两个计数器int i = 0;int j = 0;for (i = dk + 1; i <= list.length; i++) {// 判断是否需要排序if (list.arr[i] < list.arr[i - dk]) {list.arr[0] = list.arr[i]; // 复制为哨兵// 开始排序for (j = i - dk; (j > 0) && (list.arr[j] > list.arr[0]); j -= dk) {list.arr[j + dk] = list.arr[j];}list.arr[j + dk] = list.arr[0]; // 插入到正确位置}}
}void shellSort(SqList list, int dlta[], int t) {// 按增量序列 dlta 对顺序表 list 作希尔排序int i = 0;for (i = 0; i < t; i++) {shellInsert(list, dlta[i]); // 一趟增量为 dlta[i] 的插入排序}
}int main() {// 初始化数据SqList list;list.length = 10;list.arr = calloc(list.length + 1, sizeof(int));int dlta[] = { 5, 3, 1 }; // 增量序列int t = sizeof(dlta) / sizeof(dlta[0]); // 序列长度// 输入int i = 0;for (i = 1; i <= list.length; i++) {scanf("%d", list.arr + i);}shellSort(list, dlta, t); // 排序// 输出for (i = 1; i <= list.length; i++) {printf("%d ", list.arr[i]);}return 0;
}小结
插入排序是一种简单且易于理解的排序算法，特别适合小规模数据或部分有序的数据集。本文详细介绍了插入排序的三种实现方式：直接插入排序、折半插入排序和希尔排序。
-
直接插入排序：适合小规模数据，实现简单。
-
折半插入排序：通过二分查找优化了查找效率，适合中等规模数据。
-
希尔排序：通过分组排序进一步优化了性能，适合大规模数据。
每种实现方式都有其独特的优势和适用场景，开发者可以根据具体需求选择合适的排序算法。