数据结构

前缀树

前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

字符前缀树

#include <iostream>
#include <unordered_map>
using namespace std;

// 字典树节点结构
struct TrieNode {
    bool isEnd;  // 标记是否是单词结尾
    unordered_map<char, TrieNode*> children;  // 子节点映射表，键是字符，值是对应节点
  
    // 构造函数，初始化节点
    TrieNode() {
        isEnd = false;  // 默认不是单词结尾
    }
};

// 字典树类
class Trie {
public:
    TrieNode* root;  // 根节点指针

    // 构造函数，初始化字典树
    Trie() {
        root = new TrieNode();  // 创建根节点
    }
  
    // 插入单词到字典树
    void insert(string word) {
        TrieNode* cur = root;  // 从根节点开始
      
        // 遍历单词中的每个字符
        for (char c : word) {
            // 如果当前字符不存在于子节点中，创建新节点
            if (cur->children.find(c) == cur->children.end()) {
                cur->children[c] = new TrieNode();
            }
            cur = cur->children[c];  // 移动到子节点
        }
      
        cur->isEnd = true;  // 标记单词结尾
    }
  
    // 搜索完整单词
    bool search(string word) {
        TrieNode* cur = root;  // 从根节点开始
      
        // 遍历单词中的每个字符
        for (char c : word) {
            // 如果当前字符不存在于子节点中，返回false
            if (cur->children.find(c) == cur->children.end()) {
                return false;
            }
            cur = cur->children[c];  // 移动到子节点
        }
      
        return cur->isEnd;  // 检查是否是单词结尾
    }
  
    // 检查是否存在以指定前缀开头的单词
    bool startsWith(string prefix) {
        TrieNode* cur = root;  // 从根节点开始
      
        // 遍历前缀中的每个字符
        for (char c : prefix) {
            // 如果当前字符不存在于子节点中，返回false
            if (cur->children.find(c) == cur->children.end()) {
                return false;
            }
            cur = cur->children[c];  // 移动到子节点
        }
      
        return true;  // 前缀存在
    }
};

int main() {
    Trie trie;  // 创建字典树实例
  
    cout << "===== 测试插入和搜索功能 =====" << endl;
    // 测试1: 插入单词并搜索
    trie.insert("apple");
    cout << "搜索 'apple': " << (trie.search("apple") ? "找到" : "未找到") << endl;   // 预期：找到
    cout << "搜索 'app': " << (trie.search("app") ? "找到" : "未找到") << endl;       // 预期：未找到
  
    // 测试2: 插入另一个单词并测试前缀
    trie.insert("app");
    cout << "搜索 'app': " << (trie.search("app") ? "找到" : "未找到") << endl;       // 预期：找到
    cout << "前缀 'app': " << (trie.startsWith("app") ? "存在" : "不存在") << endl;   // 预期：存在
  
    cout << "\n===== 测试前缀功能 =====" << endl;
    // 测试3: 测试前缀功能
    cout << "前缀 'ap': " << (trie.startsWith("ap") ? "存在" : "不存在") << endl;     // 预期：存在
    cout << "前缀 'ban': " << (trie.startsWith("ban") ? "存在" : "不存在") << endl;   // 预期：不存在
  
    return 0;
}

URL前缀树

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

// URL字典树节点类
class UrlTrieNode {
public:
    unordered_map<string, UrlTrieNode*> children;  // 子节点映射表，键是URL部分，值是对应节点
    bool isEndpoint;                               // 标记是否是URL终点

    // 构造函数，初始化节点
    UrlTrieNode(const string& val = "")
        : isEndpoint(false) {}  // 默认不是终点节点
};

// URL字典树类
class UrlTrie {
private:
    UrlTrieNode* root;  // 根节点指针

    // 将URL路径拆分为部分
    vector<string> splitPath(const string& path) {
        vector<string> parts;  // 存储拆分后的部分
        size_t start = 0;      // 当前部分的起始位置
        size_t end = path.find("/");  // 查找第一个斜杠

        // 处理开头的斜杠（如果有）
        if (end == 0) {
            start = 1;
            end = path.find("/", start);
        }

        // 循环查找所有部分
        while (end != string::npos) {
            string part = path.substr(start, end - start);  // 提取当前部分
            if (!part.empty()) {
                parts.push_back(part);  // 非空部分加入结果
            }
            start = end + 1;            // 更新起始位置
            end = path.find("/", start); // 查找下一个斜杠
        }

        // 处理最后的部分（如果有）
        if (start < path.length()) {
            string part = path.substr(start);
            if (!part.empty()) {
                parts.push_back(part);
            }
        }

        return parts;
    }

    // 根据部分路径搜索节点
    UrlTrieNode* searchParts(const vector<string>& parts) {
        UrlTrieNode* current = root;  // 从根节点开始

        // 遍历所有部分
        for (const string& part : parts) {
            // 如果当前部分不存在于子节点中，返回nullptr
            if (current->children.find(part) == current->children.end()) {
                return nullptr;
            }
            current = current->children[part];  // 移动到子节点
        }

        return current;  // 返回最终节点
    }

public:
    // 构造函数，初始化字典树
    UrlTrie() {
        root = new UrlTrieNode();  // 创建根节点
    }

    // 插入URL路径
    void insert(const string& path) {
        vector<string> parts = splitPath(path);  // 拆分路径
        UrlTrieNode* current = root;             // 从根节点开始

        // 遍历所有部分
        for (const string& part : parts) {
            // 如果当前部分不存在于子节点中，创建新节点
            if (current->children.find(part) == current->children.end()) {
                current->children[part] = new UrlTrieNode();
            }
            current = current->children[part];  // 移动到子节点
        }

        current->isEndpoint = true;  // 标记为终点节点
    }

    // 搜索完整URL路径
    bool search(const string& path) {
        vector<string> parts = splitPath(path);  // 拆分路径
        UrlTrieNode* node = searchParts(parts);  // 搜索节点
        return node != nullptr && node->isEndpoint;  // 检查是否是终点节点
    }

    // 检查是否存在以指定前缀开头的URL
    bool startsWith(const string& prefix) {
        vector<string> parts = splitPath(prefix);  // 拆分前缀
        return searchParts(parts) != nullptr;     // 只需检查节点是否存在
    }
};

int main() {
    UrlTrie urlTrie;  // 创建URL字典树实例

    cout << "===== 测试基本URL插入和搜索 =====" << endl;
    // 测试1: 插入简单URL路径并搜索
    urlTrie.insert("/user/profile");
    urlTrie.insert("/user/settings");
  
    // 预期结果：找到
    cout << "搜索 '/user/profile': " << (urlTrie.search("/user/profile") ? "找到" : "未找到") << endl;
    // 预期结果：找到
    cout << "搜索 '/user/settings': " << (urlTrie.search("/user/settings") ? "找到" : "未找到") << endl;
    // 预期结果：未找到（因为/user不是终点节点）
    cout << "搜索 '/user': " << (urlTrie.search("/user") ? "找到" : "未找到") << endl;
  
    cout << "\n===== 测试前缀功能 =====" << endl;
    // 测试2: 测试前缀功能
    // 预期结果：存在（因为有/user/profile和/user/settings）
    cout << "前缀 '/user': " << (urlTrie.startsWith("/user") ? "存在" : "不存在") << endl;
    // 预期结果：不存在
    cout << "前缀 '/admin': " << (urlTrie.startsWith("/admin") ? "存在" : "不存在") << endl;
  
    return 0;
}

LRU缓存

LRU（Least Recently Used）缓存是一种淘汰最近最少使用数据的缓存策略，当缓存空间不足时，优先移除最久未被访问的数据。

#include <iostream>
#include <unordered_map>
using namespace std;

// 双向链表节点结构
struct Node{
    int key;        // 键
    int value;      // 值
    Node *prev;     // 前驱节点指针
    Node *next;     // 后继节点指针

    Node()          // 构造函数初始化
    : prev(NULL), next(NULL), key(0), value(0) {}
};

class LRUCache {
public:
    // 构造函数，初始化容量和哨兵节点
    LRUCache(int capacity) {
        dummy = new Node;       // 创建哨兵节点
        dummy -> next = dummy;  // 初始化时指向自己
        dummy -> prev = dummy;
        this -> capacity = capacity;  // 设置缓存容量
    }
  
    // 获取键对应的值
    int get(int key) {
        Node *node = get_node(key);  // 获取节点
        if ( node == NULL ) return -1;  // 不存在返回-1
        return node -> value;       // 存在返回值
    }
  
    // 插入或更新键值对
    void put(int key, int value) {
        Node *node = get_node(key);  // 先尝试获取节点
        if ( node != NULL ) {        // 如果已存在
            node -> value = value;   // 更新值
            return;
        }

        // 不存在则创建新节点
        node = new Node;
        node -> key = key;
        node -> value = value;
        push_front(node);            // 插入到链表头部
        key_to_node[key] = node;     // 存入哈希表

        // 如果超过容量，移除最久未使用的节点
        if ( key_to_node.size() > capacity ) {
            Node *k = dummy -> prev;  // 链表尾部是最久未使用的
            remove(k);               // 从链表中移除
            key_to_node.erase(k -> key);  // 从哈希表中移除
            delete k;                // 释放内存
        }
    }

private:
    unordered_map<int, Node*> key_to_node;  // 哈希表存储键到节点的映射
    Node *dummy;        // 哨兵节点，简化链表操作
    int capacity;       // 缓存容量

    // 从链表中移除节点
    void remove(Node *node) {
        node -> prev -> next = node -> next;
        node -> next -> prev = node -> prev;
    }

    // 将节点插入到链表头部
    void push_front(Node *node) {
        node -> prev = dummy;
        node -> next = dummy -> next;
        node -> prev -> next = node;
        node -> next -> prev = node;
    }

    // 获取节点并移动到链表头部
    Node* get_node(int key) {
        if ( key_to_node.find(key) == key_to_node.end() ) {
            return NULL;  // 不存在返回NULL
        }
        Node *node = key_to_node[key];  // 获取节点
        remove(node);      // 从当前位置移除
        push_front(node);  // 移动到头部
        return node;
    }
};

int main() {
    // 测试用例1：基本插入和查询
    {
        cout << "测试用例1：基本插入和查询" << endl;
        LRUCache cache(2);
        cache.put(1, 1);            // 缓存: {1=1}
        cache.put(2, 2);            // 缓存: {1=1, 2=2}
        cout << cache.get(1) << endl;  // 输出1 (缓存: {2=2, 1=1})
        cout << cache.get(2) << endl;  // 输出2 (缓存: {1=1, 2=2})
        cout << cache.get(3) << endl;  // 输出-1 (不存在)
        cout << "----------------" << endl;
    }
  
    // 测试用例2：LRU淘汰机制
    {
        cout << "测试用例2：LRU淘汰机制" << endl;
        LRUCache cache(2);
        cache.put(1, 1);            // 缓存: {1=1}
        cache.put(2, 2);            // 缓存: {1=1, 2=2}
        cache.put(3, 3);            // 淘汰1，缓存: {2=2, 3=3}
        cout << cache.get(1) << endl;  // 输出-1 (已被淘汰)
        cout << cache.get(2) << endl;  // 输出2 (缓存: {3=3, 2=2})
        cout << cache.get(3) << endl;  // 输出3 (缓存: {2=2, 3=3})
        cout << "----------------" << endl;
    }
  
    // 测试用例3：更新已有键的值
    {
        cout << "测试用例3：更新已有键的值" << endl;
        LRUCache cache(2);
        cache.put(1, 1);            // 缓存: {1=1}
        cache.put(1, 10);           // 更新值，缓存: {1=10}
        cout << cache.get(1) << endl;  // 输出10
        cout << "----------------" << endl;
    }
  
    // 测试用例4：get操作影响LRU顺序
    {
        cout << "测试用例4：get操作影响LRU顺序" << endl;
        LRUCache cache(2);
        cache.put(1, 1);            // 缓存: {1=1}
        cache.put(2, 2);            // 缓存: {1=1, 2=2}
        cout << cache.get(1) << endl;  // 输出1，使1成为最近使用 (缓存: {2=2, 1=1})
        cache.put(3, 3);            // 淘汰2，缓存: {1=1, 3=3}
        cout << cache.get(1) << endl;  // 输出1
        cout << cache.get(2) << endl;  // 输出-1 (已被淘汰)
        cout << cache.get(3) << endl;  // 输出3
        cout << "----------------" << endl;
    }
  
    return 0;
}

哈希表

哈希表是一种通过哈希函数快速定位数据存储位置的高效数据结构。

#include <iostream>
#include <vector>
#include <list>

using namespace std;

class MyHashSet {
public:
    // 构造函数，初始化哈希表大小为1000
    MyHashSet()
    : data(size) {
      
    }

    // 哈希函数，使用取模运算确定键的位置
    int hash(int key) {
        return key % size;
    }
  
    // 添加元素到集合中
    void add(int key) {
        if (contains(key)) return; // 如果已存在则不添加
        int index = hash(key);
        data[index].push_back(key);
    }
  
    // 从集合中移除元素
    void remove(int key) {
        if (!contains(key)) {
            return; // 如果不存在则直接返回
        }
        int index = hash(key);
        data[index].remove(key);
    }
  
    // 检查集合中是否包含指定元素
    bool contains(int key) {
        int index = hash(key);
        for (auto it = data[index].begin(); it != data[index].end(); it++) {
            if ((*it) == key) {
                return true;
            }
        }
        return false;
    }
private:
    int size = 1000; // 哈希表大小
    vector<list<int>> data; // 使用链表解决冲突
};

int main() {
    // 测试用例1：基本添加和包含测试
    MyHashSet set1;
    set1.add(1);
    set1.add(2);
    set1.add(3);
    cout << "测试1 - 基本功能:" << endl;
    cout << "集合包含1? " << (set1.contains(1) ? "是" : "否") << endl; // 预期: 是
    cout << "集合包含5? " << (set1.contains(5) ? "是" : "否") << endl; // 预期: 否
    cout << endl;

    // 测试用例2：重复添加测试
    MyHashSet set2;
    set2.add(10);
    set2.add(10); // 重复添加
    cout << "测试2 - 重复添加:" << endl;
    cout << "集合包含10? " << (set2.contains(10) ? "是" : "否") << endl; // 预期: 是
    cout << endl;

    // 测试用例3：删除测试
    MyHashSet set3;
    set3.add(100);
    set3.add(200);
    set3.remove(100);
    cout << "测试3 - 删除功能:" << endl;
    cout << "集合包含100? " << (set3.contains(100) ? "是" : "否") << endl; // 预期: 否
    cout << "集合包含200? " << (set3.contains(200) ? "是" : "否") << endl; // 预期: 是
    cout << endl;

    // 测试用例4：哈希冲突测试
    MyHashSet set4;
    set4.add(1);
    set4.add(1001); // 1001 % 1000 = 1，与1冲突
    cout << "测试4 - 哈希冲突:" << endl;
    cout << "集合包含1? " << (set4.contains(1) ? "是" : "否") << endl; // 预期: 是
    cout << "集合包含1001? " << (set4.contains(1001) ? "是" : "否") << endl; // 预期: 是
    cout << endl;

    return 0;
}

堆

堆是一种特殊的完全二叉树，满足每个节点的值都大于等于（或小于等于）其子节点的值，常用于优先队列和动态排序。

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

class MaxHeap {
private:
    vector<int> heap; // 使用数组存储堆元素

    // 上浮操作：将新插入的元素调整到合适位置
    void Up(int i) {
        while (i > 0 && heap[(i - 1) / 2] < heap[i]) {
            swap(heap[(i - 1) / 2], heap[i]); // 如果父节点小于当前节点，交换
            i = (i - 1) / 2; // 继续向上检查
        }
    }

    // 下沉操作：将不符合堆性质的元素下沉到合适位置
    void Down(int i) {
        int maxIndex = i; // 假设当前节点是最大的
        int left = 2 * i + 1; // 左子节点索引
        int right = 2 * i + 2; // 右子节点索引

        // 找出当前节点、左子节点、右子节点中的最大值
        if (left < heap.size() && heap[left] > heap[maxIndex])
            maxIndex = left;
        if (right < heap.size() && heap[right] > heap[maxIndex])
            maxIndex = right;

        // 如果最大值不是当前节点，交换并继续下沉
        if (i != maxIndex) {
            swap(heap[i], heap[maxIndex]);
            Down(maxIndex);
        }
    }

public:
    // 插入元素
    void push(int value) {
        heap.push_back(value); // 添加到数组末尾
        Up(heap.size() - 1); // 执行上浮操作
    }

    // 弹出最大值（堆顶元素）
    void pop() {
        if (heap.empty()) return; // 空堆直接返回
        heap[0] = heap.back(); // 将最后一个元素移到堆顶
        heap.pop_back(); // 删除最后一个元素
        if (!heap.empty()) Down(0); // 执行下沉操作
    }

    // 获取最大值（堆顶元素）
    int top() const {
        if (heap.empty()) return -1; // 简单处理空堆情况
        return heap[0];
    }

    // 获取堆大小
    int size() const {
        return heap.size();
    }

    // 检查堆是否为空
    bool empty() const {
        return heap.empty();
    }
};

int main() {
    // 测试用例1：基本功能测试
    MaxHeap heap1;
    heap1.push(3);
    heap1.push(1);
    heap1.push(4);
    heap1.push(1);
    heap1.push(5);
    heap1.push(9);
  
    cout << "测试1 - 基本功能:" << endl;
    cout << "堆顶元素: " << heap1.top() << endl; // 预期: 9
    heap1.pop();
    cout << "弹出后堆顶元素: " << heap1.top() << endl; // 预期: 5
    cout << "堆大小: " << heap1.size() << endl; // 预期: 5
    cout << endl;

    // 测试用例2：空堆测试
    MaxHeap heap2;
    cout << "测试2 - 空堆测试:" << endl;
    cout << "空堆堆顶: " << heap2.top() << endl; // 预期: -1
    heap2.pop(); // 应该不会崩溃
    cout << "对空堆执行pop操作后堆大小: " << heap2.size() << endl; // 预期: 0
    cout << endl;

    // 测试用例3：大量元素测试
    MaxHeap heap3;
    for (int i = 0; i < 100; ++i) {
        heap3.push(i);
    }
    cout << "测试3 - 大量元素测试:" << endl;
    cout << "堆顶元素: " << heap3.top() << endl; // 预期: 99
    for (int i = 0; i < 50; ++i) {
        heap3.pop();
    }
    cout << "弹出50次后堆顶元素: " << heap3.top() << endl; // 预期: 49
    cout << "剩余堆大小: " << heap3.size() << endl; // 预期: 50
    cout << endl;

    // 测试用例4：重复元素测试
    MaxHeap heap4;
    for (int i = 0; i < 10; ++i) {
        heap4.push(5);
    }
    cout << "测试4 - 重复元素测试:" << endl;
    cout << "堆顶元素: " << heap4.top() << endl; // 预期: 5
    for (int i = 0; i < 5; ++i) {
        heap4.pop();
    }
    cout << "弹出5次后堆顶元素: " << heap4.top() << endl; // 预期: 5
    cout << "剩余堆大小: " << heap4.size() << endl; // 预期: 5
    cout << endl;

    return 0;
}

布隆过滤器

布隆过滤器（Bloom Filter）是一种空间高效的概率型数据结构，用于快速判断一个元素是否可能存在于集合中（可能存在误判，但不会漏判）。

#include <iostream>
#include <vector>
#include <bitset>

using namespace std;

class IntBloomFilter {
private:
    vector<bool> bits;  // 位数组
    int size;          // 位数组大小
    int numHashes;     // 哈希函数数量

    // 简单的哈希函数1
    int hash1(int key) const {
        return key % size;
    }

    // 简单的哈希函数2
    int hash2(int key) const {
        return (key * 31) % size;
    }

    // 简单的哈希函数3
    int hash3(int key) const {
        return (key * 17 + 7) % size;
    }

public:
    // 构造函数，初始化位数组大小和哈希函数数量
    IntBloomFilter(int size, int numHashes = 3) 
        : size(size), numHashes(numHashes), bits(size, false) {
        if (numHashes < 1 || numHashes > 3) {
            cout << "警告: 哈希函数数量限制为1-3个，将使用默认值3" << endl;
            this->numHashes = 3;
        }
    }

    // 添加元素
    void add(int key) {
        bits[hash1(key)] = true;
        if (numHashes >= 2) bits[hash2(key)] = true;
        if (numHashes >= 3) bits[hash3(key)] = true;
    }

    // 检查元素是否存在（可能有误判）
    bool contains(int key) const {
        if (!bits[hash1(key)]) return false;
        if (numHashes >= 2 && !bits[hash2(key)]) return false;
        if (numHashes >= 3 && !bits[hash3(key)]) return false;
        return true;
    }

    // 打印位数组状态（用于调试）
    void printBits() const {
        cout << "位数组状态: ";
        for (bool bit : bits) {
            cout << (bit ? '1' : '0');
        }
        cout << endl;
    }
};

int main() {
    // 测试用例1：基本功能测试
    cout << "=== 测试1: 基本功能 ===" << endl;
    IntBloomFilter bf1(100); // 100位，3个哈希函数
  
    bf1.add(42);
    bf1.add(123);
    bf1.add(999);
  
    cout << "包含42? " << (bf1.contains(42) ? "是" : "否") << endl;    // 预期: 是
    cout << "包含123? " << (bf1.contains(123) ? "是" : "否") << endl;  // 预期: 是
    cout << "包含999? " << (bf1.contains(999) ? "是" : "否") << endl;  // 预期: 是
    cout << "包含456? " << (bf1.contains(456) ? "是" : "否") << endl;  // 预期: 否
    cout << endl;

    // 测试用例2：误判测试
    cout << "=== 测试2: 误判测试 ===" << endl;
    IntBloomFilter bf2(20); // 小位数组增加碰撞概率
  
    bf2.add(1);
    bf2.add(2);
    bf2.add(3);
  
    cout << "包含1? " << (bf2.contains(1) ? "是" : "否") << endl;      // 预期: 是
    cout << "包含10? " << (bf2.contains(10) ? "是" : "否") << endl;    // 可能误判
    cout << "包含15? " << (bf2.contains(15) ? "是" : "否") << endl;    // 可能误判
    cout << endl;

    // 测试用例3：不同哈希函数数量测试
    cout << "=== 测试3: 哈希函数数量影响 ===" << endl;
    IntBloomFilter bf3_1(100, 1); // 1个哈希函数
    IntBloomFilter bf3_3(100, 3); // 3个哈希函数
  
    bf3_1.add(42);
    bf3_3.add(42);
  
    cout << "1个哈希函数 - 包含42? " << (bf3_1.contains(42) ? "是" : "否") << endl;  // 预期: 是
    cout << "1个哈希函数 - 包含43? " << (bf3_1.contains(43) ? "是" : "否") << endl;  // 可能误判
    cout << "3个哈希函数 - 包含42? " << (bf3_3.contains(42) ? "是" : "否") << endl;  // 预期: 是
    cout << "3个哈希函数 - 包含43? " << (bf3_3.contains(43) ? "是" : "否") << endl;  // 误判概率更低
    cout << endl;

    // 测试用例4：边界值测试
    cout << "=== 测试4: 边界值 ===" << endl;
    IntBloomFilter bf4(10);
  
    bf4.add(0);
    bf4.add(9);
    bf4.add(1000);
  
    cout << "包含0? " << (bf4.contains(0) ? "是" : "否") << endl;          // 预期: 是
    cout << "包含9? " << (bf4.contains(9) ? "是" : "否") << endl;          // 预期: 是
    cout << "包含1000? " << (bf4.contains(1000) ? "是" : "否") << endl;    // 预期: 是
    cout << "包含5? " << (bf4.contains(5) ? "是" : "否") << endl;          // 可能误判
    cout << endl;

    return 0;
}

算法

排序

冒泡排序

1. 冒泡排序是一种简单的交换排序算法，通过反复比较相邻元素并交换顺序，使较大的元素逐渐“浮”到数组末尾（或较小的元素“沉”到开头），像气泡一样上升，因此得名。
2. 时间复杂度：O(n²)
3. 空间复杂度：O(1)
4. 稳定性：稳定

#include <iostream>
#include <vector>

using namespace std;

// 冒泡排序函数
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    // 外层循环控制排序轮数
    for (int i = 0; i < n - 1; i++) {
        // 内层循环控制每轮比较次数
        for (int j = 0; j < n - i - 1; j++) {
            // 如果前一个元素比后一个元素大，则交换它们
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int main() {
    // 单个测试用例
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
  
    cout << "排序前: ";
    for (int num : arr) cout << num << " ";
  
    bubbleSort(arr);
  
    cout << "\n排序后: ";
    for (int num : arr) cout << num << " ";
  
    return 0;
}

选择排序

1. 选择排序是一种简单直观的排序算法，核心思想是每次从未排序部分选出最小（或最大）元素，放到已排序部分的末尾，逐步构建有序序列。
2. 时间复杂度：O(n²)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

#include <iostream>
#include <vector>

using namespace std;

// 选择排序函数
void selectionSort(vector<int>& arr) {
    int n = arr.size();
    // 外层循环控制当前要填充的位置
    for (int i = 0; i < n - 1; i++) {
        // 假设当前位置是最小值的位置
        int minIndex = i;
      
        // 内层循环寻找未排序部分的最小值
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
      
        // 将找到的最小值与当前位置交换
        swap(arr[i], arr[minIndex]);
    }
}

int main() {
    // 测试用例
    vector<int> arr = {64, 25, 12, 22, 11};
  
    cout << "排序前: ";
    for (int num : arr) cout << num << " ";
  
    selectionSort(arr);
  
    cout << "\n排序后: ";
    for (int num : arr) cout << num << " ";
  
    return 0;
}

插入排序

1. 插入排序是一种简单直观的排序算法，其核心思想是将未排序部分的元素逐个插入到已排序部分的正确位置，类似于整理扑克牌时的排序方式。
2. 时间复杂度：O(n²)
3. 空间复杂度：O(1)
4. 稳定性：稳定

#include <iostream>
#include <vector>

using namespace std;

// 插入排序函数
void insertionSort(vector<int>& arr) {
    int n = arr.size();
    // 从第二个元素开始（下标1），因为单个元素默认是有序的
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // 当前要插入的元素
        int j = i - 1;     // 已排序部分的最后一个元素索引
      
        // 将比key大的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
      
        // 插入key到正确位置
        arr[j + 1] = key;
    }
}

int main() {
    // 测试用例
    vector<int> arr = {12, 11, 13, 5, 6};
  
    cout << "排序前: ";
    for (int num : arr) cout << num << " ";
  
    insertionSort(arr);
  
    cout << "\n排序后: ";
    for (int num : arr) cout << num << " ";
  
    return 0;
}

归并排序

1. 此得名。归并排序是一种基于分治法（Divide and Conquer）的高效排序算法，核心思想是将数组递归拆分为最小单元（单个元素），再逐步合并为有序序列。
2. 时间复杂度：O(n log n)
3. 空间复杂度：O(n)
4. 稳定性：稳定

#include <iostream>
#include <vector>

using namespace std;

// 合并两个有序数组
void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;  // 左子数组大小
    int n2 = right - mid;     // 右子数组大小
  
    // 创建临时数组
    vector<int> L(n1), R(n2);
  
    // 拷贝数据到临时数组
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
  
    // 合并临时数组到原数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
  
    // 拷贝剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序主函数
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;  // 防止溢出
      
        // 递归排序左右子数组
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
      
        // 合并已排序的子数组
        merge(arr, left, mid, right);
    }
}

// 包装函数，简化调用
void mergeSort(vector<int>& arr) {
    mergeSort(arr, 0, arr.size() - 1);
}

int main() {
    // 测试用例
    vector<int> arr = {12, 11, 13, 5, 6, 7};
  
    cout << "排序前: ";
    for (int num : arr) cout << num << " ";
  
    mergeSort(arr);
  
    cout << "\n排序后: ";
    for (int num : arr) cout << num << " ";
  
    return 0;
}

快速排序

1. 快速排序是一种基于分治法的高效排序算法，核心思想是通过“分区（Partition）”操作将数组分为两部分，并递归排序子数组，最终完成整体排序。
2. 时间复杂度：O(n log n)
3. 空间复杂度：O(log n) ~ O(n)
4. 稳定性：不稳定

#include <iostream>
#include <vector>

using namespace std;

// 分区函数，选择基准值并将数组分为两部分
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准值
    int i = low - 1;        // i是小于基准值的元素的边界
  
    for (int j = low; j < high; j++) {
        // 如果当前元素小于或等于基准值
        if (arr[j] <= pivot) {
            i++;  // 扩大小于基准值的区域
            swap(arr[i], arr[j]);
        }
    }
    // 将基准值放到正确位置
    swap(arr[i + 1], arr[high]);
    return i + 1;  // 返回基准值的最终位置
}

// 快速排序主函数
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        // pi是分区索引，arr[pi]现在在正确位置
        int pi = partition(arr, low, high);
      
        // 递归排序分区前后的子数组
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 包装函数，简化调用
void quickSort(vector<int>& arr) {
    quickSort(arr, 0, arr.size() - 1);
}

int main() {
    // 测试用例
    vector<int> arr = {10, 7, 8, 9, 1, 5};
  
    cout << "排序前: ";
    for (int num : arr) cout << num << " ";
  
    quickSort(arr);
  
    cout << "\n排序后: ";
    for (int num : arr) cout << num << " ";
  
    return 0;
}

堆排序

1. 堆排序是一种基于二叉堆（Binary Heap）数据结构的高效排序算法，核心思想是将待排序数组构建成堆结构，并利用堆的性质逐步提取最大（或最小）元素，从而完成排序。
2. 时间复杂度：O(n log n)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

#include <iostream>
#include <vector>

using namespace std;

// 调整堆，使其满足堆性质
void heapify(vector<int>& arr, int n, int i) {
    int largest = i;        // 初始化最大元素为当前节点
    int left = 2 * i + 1;   // 左子节点索引
    int right = 2 * i + 2;  // 右子节点索引

    // 如果左子节点比当前节点大
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子节点比当前最大节点大
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大元素不是当前节点，交换并继续调整
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

// 堆排序主函数
void heapSort(vector<int>& arr) {
    int n = arr.size();

    // 构建最大堆（从最后一个非叶子节点开始）
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 逐个提取堆顶元素（最大值）
    for (int i = n - 1; i > 0; i--) {
        // 将当前最大值移到数组末尾
        swap(arr[0], arr[i]);
        // 调整剩余元素使其满足堆性质
        heapify(arr, i, 0);
    }
}

int main() {
    // 测试用例
    vector<int> arr = {12, 11, 13, 5, 6, 7};
  
    cout << "排序前: ";
    for (int num : arr) cout << num << " ";
  
    heapSort(arr);
  
    cout << "\n排序后: ";
    for (int num : arr) cout << num << " ";
  
    return 0;
}