数据结构：常见排序算法原理与实现

各类排序方式完整信息汇总（含性能对比）

一、插入排序

1. 直接插入排序

• 定义：将待排序对象逐个插入到已排序序列的合适位置，直至全部插入完成。
• 适用范围：数据量较小（n≤100）或基本有序的场景，实现简单。
• 稳定性：稳定（关键字相等的元素排序后相对位置不变）。
• 时间复杂度：平均 O(n²)，最好 O(n)（已有序），最坏 O(n²)（逆序）。
• 空间复杂度：O(1)（仅需常数级辅助空间，监视哨可复用数组元素）。
• 实现代码：

#include <vector>

// 定义 ElemType 结构体，适配排序关键字需求
struct ElemType {
    int key; // 可补充其他数据字段
};

// 顺序表结构（C++ 风格，替代原 SqList）
struct SqList {
    std::vector<ElemType> r; // 用 vector 存储，避免手动管理内存
    int length;

    // 构造函数初始化
    SqList(const std::vector<ElemType>& data) : r(data), length(data.size()) {}
};

// 比较函数（替代原 LT 宏，更符合 C++ 规范）
bool LT(int a, int b) {
    return a < b;
}

void InsertSort(SqList& L) {
    // 注意：vector 下标从 0 开始，调整循环范围（原 C 代码从 1 开始计数）
    for (int i = 1; i < L.length; ++i) {
        if (LT(L.r[i].key, L.r[i - 1].key)) {
            ElemType temp = L.r[i]; 
             j;
             (j = i - ; j >=  && (temp.key, L.r[j].key); --j) {
                L.r[j + ] = L.r[j];
            }
            L.r[j + ] = temp;
        }
    }
}