排序

假设\(K_i=K_j (1 \leq i \leq n，1 \leq j \leq n，i \neq j)\)，且在排序前的序列中\(R_i\)领先于\(R_j\)（即i<j）。若在排序后的序列中\(R_i\)仍领先于\(R_j\)，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中Rj领先于Ri，则称所用的排序方法是不稳定的

插入排序

每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止

直接插入排序

将一条记录插入到已排好序的有序表中，从而得到一个新的、记录数量增1的有序表

#define MAXSIZE 20
typedef int KeyType
typedef struct {} InfoType
typedef struct {
    KeyType key;  // 关键字项
    InfoType otherinfo; // 其他数据项
}RedType;
typedef struct {
    RedType r[MAXSIZE+1]; // r[0]闲置或用做哨兵单元
    int length;  // 顺序表长度
}SqList; // 顺序表类型

void InsertSort(SqList &L)
{
    for (int 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]; // r[i-1]后移
            // 从后向前寻找插入位置
            for (int 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]; // 将r[0]即r[i],插入到正确位置
        }
    }
}

交换排序

选择排序

归并排序

基数排序

外部排序