2025/12/21
要实现直接插入排序，核心思路是将数组分为有序区和无序区，依次将无序区的元素插入到有序区的合适位置，最终使整个数组有序。以下是详细的实现思路和代码解析。
方法思路
划分区间：初始时，有序区仅包含第一个元素（elem[1]），无序区为elem[2]到elem[L.Length]。
逐个插入：遍历无序区的每个元素（记为temp），向前扫描有序区，找到temp的插入位置：
若有序区的元素大于temp，则将该元素后移一位。
找到插入位置后，将temp放入该位置。
哨兵优化：利用elem[0]作为哨兵，存储当前待插入的元素，避免数组越界判断，同时简化代码逻辑。
完整代码
c
运行
include<stdio.h>
include<stdlib.h>
typedef int KeyType;
typedef struct {
KeyType elem; /elem[0]一般作哨兵或缓冲区/
int Length;
}SqList;
void CreatSqList(SqList L);/待排序列建立，由裁判实现，细节不表/
void InsertSort(SqList L);
int main()
{
SqList L;
int i;
CreatSqList(&L);
InsertSort(L);
for(i=1;i<=L.Length;i++)
{
printf("%d ",L.elem[i]);
}
return 0;
}
/* 直接插入排序函数 /
void InsertSort(SqList L) {
int i, j;
// 从第二个元素开始（无序区第一个元素），遍历到最后一个元素
for (i = 2; i <= L.Length; i++) {
// 若当前元素小于前一个元素（有序区最后一个元素），需要插入
if (L.elem[i] < L.elem[i - 1]) {
// 将当前元素存入哨兵位置elem[0]，避免数据覆盖
L.elem[0] = L.elem[i];
// 向前扫描有序区，寻找插入位置
for (j = i - 1; L.elem[0] < L.elem[j]; j--) {
// 元素后移，为插入位置腾出空间
L.elem[j + 1] = L.elem[j];
}
// 将哨兵中的元素插入到正确位置
L.elem[j + 1] = L.elem[0];
}
}
}
/ 裁判实现的CreatSqList函数（供测试用） */
void CreatSqList(SqList *L) {
int n, i;
scanf("%d", &n);
L->Length = n;
// 动态分配数组，elem[0]作为哨兵，实际元素从elem[1]开始
L->elem = (KeyType *)malloc((n + 1) * sizeof(KeyType));
for (i = 1; i <= n; i++) {
scanf("%d", &L->elem[i]);
}
}
代码解析
- InsertSort函数核心逻辑
变量定义：
i：遍历无序区的循环变量，从2开始（有序区初始为elem[1]）。
j：向前扫描有序区的循环变量，用于寻找插入位置。
L.elem[0]：哨兵，存储当前待插入的元素，避免越界且简化比较逻辑。
外层循环（遍历无序区）：
c
运行
for (i = 2; i <= L.Length; i++) {
从第二个元素开始，逐个处理无序区的元素。
判断是否需要插入：
c
运行
if (L.elem[i] < L.elem[i - 1]) {
若当前元素小于有序区的最后一个元素，说明需要插入；否则该元素已在正确位置，无需处理。
哨兵存储待插入元素：
c
运行
L.elem[0] = L.elem[i];
将待插入元素存入elem[0]，后续移动元素时不会覆盖该值。
内层循环（寻找插入位置并移动元素）：
c
运行
for (j = i - 1; L.elem[0] < L.elem[j]; j--) {
L.elem[j + 1] = L.elem[j];
}
j从有序区最后一个元素开始向前扫描。
若elem[0]（待插入元素）小于elem[j]，则将elem[j]后移一位（elem[j+1] = elem[j]）。
当循环结束时，j+1即为待插入位置。
插入元素：
c
运行
L.elem[j + 1] = L.elem[0];
将哨兵中的待插入元素放入最终的插入位置。 - 裁判程序逻辑
CreatSqList函数：读取输入的关键字个数和具体值，动态分配数组空间，初始化顺序表SqList（elem[0]为哨兵，实际数据从elem[1]开始）。
main函数：驱动流程，调用CreatSqList建表、InsertSort排序、最后输出结果。
输入输出示例
输入：
plaintext
10
5 2 4 1 8 9 10 12 3 6
输出：
plaintext
1 2 3 4 5 6 8 9 10 12
时间与空间复杂度
时间复杂度：
最好情况（数组已有序）：
O(n)
，只需遍历一次，无需移动元素。
最坏情况（数组逆序）：
O(n
，每个元素都需移动到最前面。
平均情况：
O(n
2)
。
空间复杂度：
O(1)
，仅使用常数级额外空间（哨兵位置为数组本身的预留空间，未额外分配）。