插入排序及其代码解释

插入排序是一种简单直观的排序算法，它的基本思想是将一个记录插入到已经排好序的有序序列中，从而得到一个新的、记录数增加1的有序序列。下面是插入排序的代码解释：

#include<stdio.h>
typedef struct {
    int key;
}RecType;
typedef struct {
    RecType R[100+1];
    int Length;
}SqList;

void InsertSort(SqList *L){
    int i,j;
    for(i=2;i<=L->Length;i++){ // 从第二个元素开始，依次将其插入到前面已排序的序列中
        if(L->R[i].key<L->R[i-1].key){ // 如果当前元素小于前一个元素，则需要插入到前面有序序列中
            L->R[0]=L->R[i]; // 将当前元素存储到哨兵位置
            L->R[i]=L->R[i-1]; // 将前一个元素后移一位
            for(j=i-2;L->R[0].key<L->R[j].key;j--){ // 从当前元素的前一个元素开始，依次向前比较，找到插入位置
                L->R[j+1]=L->R[j]; // 将比当前元素大的元素后移一位
            }
            L->R[j+1]=L->R[0]; // 将当前元素插入到正确的位置
        }
    }
}

上述代码中，我们定义了两个结构体`RecType`和`SqList`，分别表示记录和顺序表。`InsertSort`函数实现了插入排序算法，其中`L`是一个指向顺序表的指针。算法的核心部分是一个嵌套的循环，外层循环从第二个元素开始，内层循环从当前元素的前一个元素开始，依次向前比较并将比当前元素大的元素后移一位，直到找到插入位置，然后将当前元素插入到正确的位置。

插入排序的时间复杂度为O(n^2)，其中n是待排序序列的长度。它是一种稳定的排序算法，适用于小规模数据或基本有序的数据。