sort-template

给我这些排序的特点、原理、cpp可实现代码，方便我学习以及亲自手敲代码

选择排序（多次“打擂台”）
冒泡排序
插入排序
计数排序
基数排序
快速排序
归并排序（分治）
堆排序
桶排序
希尔排序（并非常见）
锦标赛排序（并非常见）
Tim排序（并非常见）

以下是各类排序算法的特点、原理及C++实现代码，按常用程度和逻辑复杂度排序，方便学习和手敲练习：

1. 选择排序（Selection Sort）

特点

原理简单，不稳定排序（如[2,2,1]会交换第一个2和1，破坏稳定性）。
时间复杂度：O(n²)，空间复杂度：O(1)。
适合小规模数据，交换次数少（最多n-1次）。

原理

每次从待排序区间选择最小（或最大）元素，放到区间起始位置，重复直到排序完成。

C++实现

cpp

#include <vector>
using namespace std;

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        int minIdx = i;  // 记录最小值索引
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        swap(arr[i], arr[minIdx]);  // 交换到当前位置
    }
}

2. 冒泡排序（Bubble Sort）

特点

原理直观，稳定排序（相等元素不交换）。
时间复杂度：O(n²)，空间复杂度：O(1)。
适合几乎有序的数据（可优化提前终止）。

原理

重复遍历数组，每次比较相邻元素，顺序错误则交换，直到没有元素交换（排序完成）。

C++实现

cpp

#include <vector>
using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    bool swapped;  // 优化：判断是否已有序
    for (int i = 0; i < n - 1; ++i) {
        swapped = false;
        for (int j = 0; j < n - i - 1; ++j) {  // 尾部已排序，无需再比较
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;  // 无交换，提前终止
    }
}

3. 插入排序（Insertion Sort）

特点

稳定排序，适合小规模或部分有序数据。
时间复杂度：O(n²)，空间复杂度：O(1)。
实际应用中比冒泡排序高效（移动操作比交换少）。

原理

将数组分为「已排序」和「未排序」两部分，每次从后者取一个元素，插入前者的合适位置。

C++实现

cpp

#include <vector>
using namespace std;

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    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--;
        }
        arr[j + 1] = key;  // 插入key
    }
}

4. 希尔排序（Shell Sort）

特点

插入排序的优化版，不稳定排序。
时间复杂度：O(n^1.3)（取决于步长），空间复杂度：O(1)。
通过「分组插入排序」减少数据移动距离。

原理

按递减步长将数组分组，对每组进行插入排序，最终步长为1（退化为普通插入排序）。

C++实现（步长采用n/2递减）

cpp

#include <vector>
using namespace std;

void shellSort(vector<int>& arr) {
    int n = arr.size();
    // 步长从n/2开始，每次减半
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // 对每个分组进行插入排序
        for (int i = gap; i < n; ++i) {
            int key = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > key; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = key;
        }
    }
}

5. 快速排序（Quick Sort）

特点

分治思想，不稳定排序，实际应用中最快的排序之一。
时间复杂度：平均O(n log n)，最坏O(n²)（可通过随机选枢轴优化），空间复杂度：O(log n)（递归栈）。

原理

选一个「枢轴」元素，将数组分为两部分：左部≤枢轴，右部≥枢轴。
递归对左右两部分排序。

C++实现（随机枢轴优化）

cpp

#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

// 划分函数：返回枢轴最终位置
int partition(vector<int>& arr, int low, int high) {
    // 随机选枢轴，避免最坏情况
    srand(time(0));
    int pivotIdx = low + rand() % (high - low + 1);
    swap(arr[pivotIdx], arr[high]);
    int pivot = arr[high];
    
    int i = low - 1;  // 记录小于枢轴的区域边界
    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) {
        int pi = partition(arr, low, high);  // 划分
        quickSort(arr, low, pi - 1);         // 左半部分
        quickSort(arr, pi + 1, high);        // 右半部分
    }
}

// 对外接口
void quickSort(vector<int>& arr) {
    if (arr.empty()) return;
    quickSort(arr, 0, arr.size() - 1);
}

6. 归并排序（Merge Sort）

特点

分治思想，稳定排序，时间复杂度稳定。
时间复杂度：O(n log n)，空间复杂度：O(n)（需临时数组）。
适合大规模数据，可并行化。

原理

将数组递归分为两半，直到子数组长度为1（天然有序）。
合并两个有序子数组为一个有序数组。

C++实现

cpp

#include <vector>
using namespace std;

// 合并两个有序子数组[low,mid]和[mid+1,high]
void merge(vector<int>& arr, int low, int mid, int high) {
    int n1 = mid - low + 1;
    int n2 = high - mid;
    vector<int> L(n1), R(n2);  // 临时数组
    
    // 复制数据到临时数组
    for (int i = 0; i < n1; ++i) L[i] = arr[low + i];
    for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];
    
    // 合并临时数组到原数组
    int i = 0, j = 0, k = low;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i++];
        } else {
            arr[k] = R[j++];
        }
        k++;
    }
    // 处理剩余元素
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;  // 避免溢出
        mergeSort(arr, low, mid);          // 左半部分排序
        mergeSort(arr, mid + 1, high);     // 右半部分排序
        merge(arr, low, mid, high);        // 合并
    }
}

// 对外接口
void mergeSort(vector<int>& arr) {
    if (arr.empty()) return;
    mergeSort(arr, 0, arr.size() - 1);
}

7. 堆排序（Heap Sort）

特点

利用堆数据结构，不稳定排序。
时间复杂度：O(n log n)，空间复杂度：O(1)（原地排序）。
适合大数据量，堆顶可快速获取极值。

原理

将数组构建为大顶堆（父节点≥子节点）。
反复将堆顶（最大值）与末尾元素交换，缩小堆范围并重新调整堆结构。

C++实现

cpp

#include <vector>
using namespace std;

// 调整以root为根的子树为大顶堆
void heapify(vector<int>& arr, int n, int root) {
    int largest = root;       // 初始化最大值为根
    int left = 2 * root + 1;  // 左子节点
    int right = 2 * root + 2; // 右子节点
    
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    
    // 若最大值不是根，则交换并递归调整
    if (largest != root) {
        swap(arr[root], 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);    // 调整剩余元素为大顶堆
    }
}

8. 计数排序（Counting Sort）

特点

非比较排序，稳定排序，适用于整数且范围不大的场景。
时间复杂度：O(n + k)（k为数据范围），空间复杂度：O(n + k)。

原理

统计每个元素出现的次数（计数数组）。
根据计数数组计算元素的位置，填充到结果数组。

C++实现（假设数据范围为[minVal, maxVal]）

cpp

#include <vector>
#include <algorithm>
using namespace std;

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;
    int minVal = *min_element(arr.begin(), arr.end());
    int maxVal = *max_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;
    
    vector<int> count(range, 0);  // 计数数组
    vector<int> output(arr.size());  // 结果数组
    
    // 统计每个元素出现次数
    for (int num : arr) {
        count[num - minVal]++;
    }
    
    // 计算前缀和（确定元素位置）
    for (int i = 1; i < range; ++i) {
        count[i] += count[i - 1];
    }
    
    // 填充结果数组（从后往前保证稳定性）
    for (int i = arr.size() - 1; i >= 0; --i) {
        output[count[arr[i] - minVal] - 1] = arr[i];
        count[arr[i] - minVal]--;
    }
    
    // 复制回原数组
    arr = output;
}

9. 基数排序（Radix Sort）

特点

非比较排序，基于计数排序实现，稳定排序。
时间复杂度：O(d*(n + k))（d为位数，k为基数，通常取10），空间复杂度：O(n + k)。
适合大整数或字符串排序（按位处理）。

原理

按低位到高位（或高位到低位）依次排序。
每一位排序使用计数排序（保证稳定性）。

C++实现（按低位排序，基数为10）

cpp

#include <vector>
#include <algorithm>
using namespace std;

// 获取数字的第d位（从0开始，d=0为个位）
int getDigit(int num, int d) {
    for (int i = 0; i < d; ++i) {
        num /= 10;
    }
    return num % 10;
}

// 对第d位进行计数排序（基数为10）
void countSortByDigit(vector<int>& arr, int d) {
    int n = arr.size();
    vector<int> output(n);
    vector<int> count(10, 0);  // 0-9共10个数字
    
    // 统计第d位的次数
    for (int i = 0; i < n; ++i) {
        int digit = getDigit(arr[i], d);
        count[digit]++;
    }
    
    // 计算前缀和
    for (int i = 1; i < 10; ++i) {
        count[i] += count[i - 1];
    }
    
    // 填充结果（从后往前保证稳定性）
    for (int i = n - 1; i >= 0; --i) {
        int digit = getDigit(arr[i], d);
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    
    arr = output;
}

void radixSort(vector<int>& arr) {
    if (arr.empty()) return;
    // 找到最大数，确定最大位数
    int maxVal = *max_element(arr.begin(), arr.end());
    int maxDigits = 0;
    while (maxVal > 0) {
        maxVal /= 10;
        maxDigits++;
    }
    
    // 按每位排序
    for (int d = 0; d < maxDigits; ++d) {
        countSortByDigit(arr, d);
    }
}

10. 桶排序（Bucket Sort）

特点

非比较排序，稳定性取决于桶内排序算法。
时间复杂度：平均O(n + k)，最坏O(n²)（桶内用插入排序时），空间复杂度：O(n + k)（k为桶数）。
适合均匀分布的数据（如浮点数、范围已知的整数）。

原理

将数据分到多个桶中（每个桶对应一个范围）。
对每个桶内数据单独排序（如插入排序）。
合并所有桶的结果。

C++实现（假设数据范围为[0,1)的浮点数）

cpp

#include <vector>
#include <algorithm>
using namespace std;

void bucketSort(vector<float>& arr) {
    int n = arr.size();
    if (n == 0) return;
    
    // 创建n个桶
    vector<vector<float>> buckets(n);
    
    // 将元素分配到桶中
    for (float num : arr) {
        int bucketIdx = n * num;  // 映射到[0, n-1]
        buckets[bucketIdx].push_back(num);
    }
    
    // 对每个桶排序
    for (auto& bucket : buckets) {
        sort(bucket.begin(), bucket.end());  // 此处用库函数，也可替换为插入排序
    }
    
    // 合并桶
    int idx = 0;
    for (auto& bucket : buckets) {
        for (float num : bucket) {
            arr[idx++] = num;
        }
    }
}

11. 锦标赛排序（Tournament Sort）

特点

基于堆的排序，稳定排序，适合外部排序（数据不能全部加载到内存）。
时间复杂度：O(n log n)，空间复杂度：O(n)（需构建锦标赛树）。

原理

构建完全二叉树（锦标赛树），叶子节点为待排序元素，非叶子节点为子节点的最小值（或最大值）。
提取根节点（最小值），标记为已提取，更新路径上的节点为剩余子节点的最小值，重复直到所有元素提取完毕。

C++实现（最小值锦标赛）

cpp

#include <vector>
#include <climits>
using namespace std;

// 构建锦标赛树
void buildTournamentTree(const vector<int>& arr, vector<int>& tree, vector<bool>& isExtracted, int n) {
    int size = 1;
    while (size < n) size <<= 1;  // 找到大于等于n的最小2的幂
    
    // 初始化叶子节点
    for (int i = 0; i < n; ++i) {
        tree[size - 1 + i] = arr[i];
    }
    for (int i = n; i < size; ++i) {
        tree[size - 1 + i] = INT_MAX;  // 虚拟节点（无穷大）
    }
    
    // 构建非叶子节点
    for (int i = size - 2; i >= 0; --i) {
        tree[i] = min(tree[2 * i + 1], tree[2 * i + 2]);
    }
}

// 提取最小值并更新树
int extractMin(vector<int>& tree, vector<bool>& isExtracted, int size, int n) {
    int minVal = tree[0];
    int i = 0;
    
    // 找到最小值对应的叶子节点
    while (i < size - 1) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (tree[left] == tree[i]) {
            i = left;
        } else {
            i = right;
        }
    }
    
    isExtracted[i - (size - 1)] = true;  // 标记为已提取
    tree[i] = INT_MAX;  // 置为无穷大
    
    // 向上更新树
    i = (i - 1) / 2;  // 父节点
    while (i >= 0) {
        int newVal = min(tree[2 * i + 1], tree[2 * i + 2]);
        if (tree[i] == newVal) break;  // 无需继续更新
        tree[i] = newVal;
        if (i == 0) break;
        i = (i - 1) / 2;
    }
    
    return minVal;
}

void tournamentSort(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1) return;
    
    int size = 1;
    while (size < n) size <<= 1;  // 树的大小（2的幂）
    vector<int> tree(2 * size - 1);  // 锦标赛树
    vector<bool> isExtracted(n, false);  // 标记是否已提取
    
    buildTournamentTree(arr, tree, isExtracted, n);
    
    // 提取所有元素
    for (int i = 0; i < n; ++i) {
        arr[i] = extractMin(tree, isExtracted, size, n);
    }
}

12. Tim排序

特点

Python和Java的内置排序算法，结合归并排序和插入排序，稳定排序。
时间复杂度：O(n log n)，空间复杂度：O(n)。
对现实数据（常有部分有序）优化极佳。

原理

将数组分为多个「运行段」（Run，已排序的子序列），短运行段用插入排序扩展。
按规则合并运行段（类似归并排序，控制合并顺序避免失衡）。

C++实现（简化版，实际实现复杂）

cpp

#include <vector>
#include <algorithm>
using namespace std;

const int MIN_RUN = 32;  // 最小运行段长度（可调）

// 插入排序，对[left, right]区间排序
void insertionSort(vector<int>& arr, int left, int right) {
    for (int i = left + 1; i <= right; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// 合并两个有序区间[left, mid]和[mid+1, right]
void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> L(arr.begin() + left, arr.begin() + mid + 1);
    vector<int> R(arr.begin() + mid + 1, arr.begin() + right + 1);
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void timSort(vector<int>& arr) {
    int n = arr.size();
    if (n <= MIN_RUN) {
        insertionSort(arr, 0, n - 1);
        return;
    }
    
    // 划分并排序运行段
    for (int i = 0; i < n; i += MIN_RUN) {
        int end = min(i + MIN_RUN - 1, n - 1);
        insertionSort(arr, i, end);
    }
    
    // 合并运行段，从长度MIN_RUN开始，每次翻倍
    for (int size = MIN_RUN; size < n; size *= 2) {
        for (int left = 0; left < n; left += 2 * size) {
            int mid = min(left + size - 1, n - 1);
            int right = min(left + 2 * size - 1, n - 1);
            if (mid < right) {  // 若有右段则合并
                merge(arr, left, mid, right);
            }
        }
    }
}

学习建议

先掌握基础：选择、冒泡、插入排序是理解排序思想的基础，重点理解「比较-交换/移动」逻辑。
深入分治排序：快速排序（ pivot 选择）、归并排序（合并逻辑）是面试高频考点。
非比较排序：计数、基数、桶排序适用于特定场景，需理解其适用条件（如数据范围、分布）。
动手实践：每敲完一种排序，用测试用例（如空数组、重复元素、逆序数组）验证正确性，观察算法行为。

通过对比不同算法的时间/空间复杂度和适用场景，能更深刻理解排序的本质~

如果我想偷懒调用库函数，如何写，或者调用?

在 C++ 中，直接调用标准库的排序函数是最便捷的方式，无需自己实现排序算法。标准库提供了 std::sort（最常用）和 std::stable_sort（稳定排序），位于 <algorithm> 头文件中，适用于大多数场景。

1. 调用 `std::sort`（快速排序的优化版本，非稳定排序）

特点：

平均时间复杂度 O(n log n)，效率极高。
非稳定排序（相等元素的相对顺序可能改变）。
支持任意可随机访问的容器（如 vector、array、原生数组等）。

使用方法：

cpp

#include <iostream>
#include <vector>
#include <algorithm> // 包含 std::sort

int main() {
    // 示例1：排序 vector<int>
    std::vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
    std::sort(arr.begin(), arr.end()); // 默认升序排序
    
    // 输出结果
    for (int num : arr) {
        std::cout << num << " "; // 输出：1 1 2 3 4 5 6 9
    }
    std::cout << std::endl;

    // 示例2：排序原生数组
    int nums[] = {5, 2, 7, 3, 1};
    int n = sizeof(nums) / sizeof(nums[0]);
    std::sort(nums, nums + n); // 原生数组用指针范围
    
    for (int i = 0; i < n; ++i) {
        std::cout << nums[i] << " "; // 输出：1 2 3 5 7
    }
    std::cout << std::endl;

    // 示例3：降序排序（自定义比较函数）
    std::vector<int> arr2 = {3, 1, 4, 1, 5};
    std::sort(arr2.begin(), arr2.end(), std::greater<int>()); // 降序
    
    for (int num : arr2) {
        std::cout << num << " "; // 输出：5 4 3 1 1
    }
    std::cout << std::endl;

    return 0;
}

2. 调用 `std::stable_sort`（稳定排序）

特点：

时间复杂度 O(n log n)，但空间复杂度略高（可能为 O(n)）。
稳定排序（相等元素的相对顺序保持不变）。
使用场景：需要保留相等元素原始顺序时（如先按成绩排序，再按姓名排序，需保留姓名的原始顺序）。

使用方法：

cpp

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

int main() {
    // 示例：稳定排序（保留相等元素的原始顺序）
    std::vector<std::pair<int, int>> arr = {{2, 1}, {1, 2}, {2, 3}, {1, 4}};
    // 按第一个元素排序（值相等时，保留原始顺序）
    std::stable_sort(arr.begin(), arr.end(), 
        [](const auto& a, const auto& b) { return a.first < b.first; });
    
    for (auto& p : arr) {
        std::cout << "(" << p.first << "," << p.second << ") ";
        // 输出：(1,2) (1,4) (2,1) (2,3) （注意第二个元素的顺序与输入一致）
    }
    return 0;
}

3. 对自定义类型排序（需提供比较规则）

如果排序对象是自定义结构体/类，需通过重载 < 运算符或自定义比较函数告诉 std::sort 如何排序。

cpp

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

// 自定义结构体
struct Student {
    std::string name;
    int score;
};

int main() {
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 75},
        {"Charlie", 90}
    };

    // 方法1：使用 lambda 表达式定义比较规则（按分数升序）
    std::sort(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            return a.score < b.score; // 分数小的在前
        });

    // 输出排序结果
    for (auto& s : students) {
        std::cout << s.name << " (" << s.score << "), ";
        // 输出：Bob (75), Alice (85), Charlie (90), 
    }

    return 0;
}

总结：

大多数情况直接用 std::sort 即可，效率高且用法简单。
需要稳定排序时用 std::stable_sort。
支持升序、降序或自定义排序规则（通过比较函数或 lambda）。
适用容器：vector、array、deque 等可随机访问的容器，以及原生数组。

调用标准库函数是工程中最推荐的做法，因为其经过严格优化，且避免了手写排序的潜在 bug。

sort和qsort区别在哪里？

sort（C++标准库函数）和qsort（C标准库函数）都是用于排序的库函数，但它们来自不同的语言标准，在使用方式、功能和性能上有显著区别。以下是详细对比：

1. 所属标准与头文件

qsort：
来自 C标准库（C89及以后），定义在 <stdlib.h> 头文件中。
C++中也可使用（需包含 <cstdlib>），但本质是C的遗留函数。
sort：
来自 C++标准库（C++98及以后），定义在 <algorithm> 头文件中，是C++ STL的一部分。

2. 函数原型与参数

`qsort` 原型：

void qsort(
    void* base,        // 待排序数组的起始地址（void* 泛型指针）
    size_t nmemb,      // 数组元素个数
    size_t size,       // 每个元素的字节大小
    int (*compar)(const void*, const void*)  // 比较函数指针
);

必须显式指定数组地址、元素个数、每个元素的大小。
比较函数需手动处理指针类型转换（因为参数是 void*）。

`sort` 原型（简化版）：

cpp

template <class RandomIt>
void sort(
    RandomIt first,    // 排序范围的起始迭代器
    RandomIt last      // 排序范围的结束迭代器（前闭后开）
);

// 带自定义比较器的版本
template <class RandomIt, class Compare>
void sort(
    RandomIt first, 
    RandomIt last, 
    Compare comp       // 比较函数/函数对象/lambda
);

通过迭代器指定排序范围（如 vector.begin() 到 vector.end()），无需手动计算元素个数和大小。
模板自动推导元素类型，无需手动类型转换。

3. 支持的数据类型

qsort：
只能排序 原生数组（如 int arr[10]），且需手动处理类型转换。
对自定义类型（如C++的结构体/类）排序时，需在比较函数中显式转换 void* 为对应类型指针，容易出错。
sort：
支持 所有可随机访问的容器（如 vector、array、deque）和原生数组，通过迭代器统一接口。
对自定义类型（如 struct、class）排序时，可通过重载 < 运算符或自定义比较器（lambda、函数对象）实现，类型安全且方便。

4. 比较函数的差异

`qsort` 的比较函数：

必须返回 int 类型：
- 若 a < b，返回负数；
- 若 a == b，返回 0；
- 若 a > b，返回正数。

参数为 const void*，需手动转换为具体类型指针，例如排序 int 数组：

int compareInt(const void* a, const void* b) {
    // 必须先转换为 int*，再解引用
    int val1 = *(const int*)a;
    int val2 = *(const int*)b;
    return val1 - val2; // 升序
}

`sort` 的比较器：

可以是函数、函数对象或lambda表达式，返回 bool 类型：
若希望 a 排在 b 前面，返回 true，否则返回 false。

无需类型转换，模板自动推导，例如排序 int 数组：

cpp

// 升序（默认，可省略）
sort(arr.begin(), arr.end(), [](int a, int b) { return a < b; });
// 降序
sort(arr.begin(), arr.end(), [](int a, int b) { return a > b; });

5. 排序算法与性能

qsort：
通常实现为 快速排序（某些库可能用混合算法），但由于C语言的限制（无模板、需类型转换），性能略低，尤其是对小数据或简单类型（如 int）。
时间复杂度：平均 O(n log n)，最坏 O(n²)（取决于实现）。
sort：
C++标准未规定具体算法，但主流实现（如GCC的 libstdc++）采用 ** introsort（内省排序）**，结合快速排序、堆排序和插入排序，在不同场景下自动切换，性能更优。
时间复杂度：稳定在 O(n log n)（最坏情况也会保证）。
此外，sort 利用模板 inline 优化，避免了 qsort 中函数指针的调用开销，对简单类型排序速度通常比 qsort 快2-3倍。

6. 稳定性

qsort：不稳定排序（相等元素的相对顺序可能改变）。
sort：不稳定排序（同 qsort），但C++提供 stable_sort 实现稳定排序，而C标准库没有对应的稳定排序函数。

7. 使用示例对比

排序 `int` 数组：

cpp

// qsort 示例（C风格）
#include <cstdlib>
#include <iostream>
using namespace std;

int compareInt(const void* a, const void* b) {
    return *(int*)a - *(int*)b; // 手动转换
}

int main() {
    int arr[] = {3, 1, 4, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    qsort(arr, n, sizeof(int), compareInt); // 需指定大小和比较函数
    for (int num : arr) cout << num << " "; // 1 1 3 4 5
    return 0;
}

cpp

// sort 示例（C++风格）
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {3, 1, 4, 1, 5};
    sort(arr.begin(), arr.end()); // 无需手动指定大小和类型
    for (int num : arr) cout << num << " "; // 1 1 3 4 5
    return 0;
}

排序自定义类型：

cpp

// qsort 排序结构体（需手动转换）
#include <cstdlib>
#include <string>
using namespace std;

struct Student { string name; int score; };

int compareStudent(const void* a, const void* b) {
    // 手动转换为 Student*
    Student* s1 = (Student*)a;
    Student* s2 = (Student*)b;
    return s1->score - s2->score;
}

int main() {
    Student arr[] = {{"Bob", 75}, {"Alice", 85}};
    qsort(arr, 2, sizeof(Student), compareStudent);
    return 0;
}

cpp

// sort 排序结构体（类型安全）
#include <algorithm>
#include <vector>
using namespace std;

struct Student { string name; int score; };

int main() {
    vector<Student> arr = {{"Bob", 75}, {"Alice", 85}};
    // 用lambda指定排序规则（按分数升序）
    sort(arr.begin(), arr.end(), [](const Student& a, const Student& b) {
        return a.score < b.score;
    });
    return 0;
}

总结：如何选择？

在C++中：优先使用 std::sort，原因是：
类型安全、接口简洁（迭代器）、性能更优、支持自定义类型和lambda，且有 stable_sort 可选。
在纯C中：只能使用 qsort，但需注意类型转换和函数指针的使用。

简单来说，sort 是C++中更现代、高效、安全的排序方案，而 qsort 是C语言的遗留产物，仅在兼容C时使用。

介绍一下std::sort函数的时间复杂度

std::sort 是 C++ 标准库中最常用的排序函数，其时间复杂度设计为 平均和最坏情况下均为 O(n log n)，这是通过灵活的算法选择实现的。具体细节如下：

1. 底层算法：内省排序（Introsort）

C++ 标准并未强制规定 std::sort 的具体实现，但主流编译器（如 GCC 的 libstdc++、Clang 的 libc++）均采用 内省排序（Introsort） 作为核心算法，其逻辑如下：

初始阶段：使用快速排序（Quicksort），利用其平均 O(n log n) 的高效性。
深度控制：跟踪递归深度，当深度超过阈值（通常为 2 * log2(n)）时，切换为堆排序（Heapsort），避免快速排序在最坏情况下（如已排序数组）退化为 O(n²)。
小规模优化：当子数组长度小于阈值（通常为 16）时，切换为插入排序（Insertionsort），利用其对小规模数据的高效性（减少递归开销）。

这种混合策略确保了 std::sort 在各种场景下的稳定性和高效性。

2. 时间复杂度的保证

平均情况：O(n log n)（来自快速排序的特性）。
最坏情况：O(n log n)（通过堆排序兜底，避免快速排序的最坏情况）。
空间复杂度：O(log n)（主要来自快速排序的递归栈，堆排序阶段为 O(1) 原地排序）。

3. 与其他排序函数的对比

相比 C 语言的 qsort（通常为纯快速排序，最坏 O(n²)），std::sort 最坏情况下更稳定。
相比 std::stable_sort（稳定排序，最坏 O(n log n)，但空间复杂度可能为 O(n)），std::sort 空间效率更高，但不稳定。

总结

std::sort 通过内省排序（快速排序 + 堆排序 + 插入排序的混合策略），在理论和实践中均保证了 O(n log n) 的时间复杂度，兼顾了平均效率和最坏情况性能，是 C++ 中排序的首选方案。

给我这些排序的特点、原理、cpp可实现代码，方便我学习以及亲自手敲代码 ​

1. 选择排序（Selection Sort） ​

特点 ​

原理 ​

C++实现 ​

2. 冒泡排序（Bubble Sort） ​

特点 ​

原理 ​

C++实现 ​

3. 插入排序（Insertion Sort） ​

特点 ​

原理 ​

C++实现 ​

4. 希尔排序（Shell Sort） ​

特点 ​

原理 ​

C++实现（步长采用n/2递减） ​

5. 快速排序（Quick Sort） ​

特点 ​

原理 ​

C++实现（随机枢轴优化） ​

6. 归并排序（Merge Sort） ​

特点 ​

原理 ​

C++实现 ​

7. 堆排序（Heap Sort） ​

特点 ​

原理 ​

C++实现 ​

8. 计数排序（Counting Sort） ​

特点 ​

原理 ​

C++实现（假设数据范围为[minVal, maxVal]） ​

9. 基数排序（Radix Sort） ​

特点 ​

原理 ​

C++实现（按低位排序，基数为10） ​

10. 桶排序（Bucket Sort） ​

特点 ​

原理 ​

C++实现（假设数据范围为[0,1)的浮点数） ​

11. 锦标赛排序（Tournament Sort） ​

特点 ​

原理 ​

C++实现（最小值锦标赛） ​

12. Tim排序 ​

特点 ​

原理 ​

C++实现（简化版，实际实现复杂） ​

学习建议 ​

如果我想偷懒调用库函数，如何写，或者调用? ​

1. 调用 std::sort（快速排序的优化版本，非稳定排序） ​

特点： ​

使用方法： ​

2. 调用 std::stable_sort（稳定排序） ​

特点： ​

使用方法： ​

3. 对自定义类型排序（需提供比较规则） ​

总结： ​

sort和qsort区别在哪里？ ​

1. 所属标准与头文件 ​

2. 函数原型与参数 ​

qsort 原型： ​

sort 原型（简化版）： ​

3. 支持的数据类型 ​

4. 比较函数的差异 ​

qsort 的比较函数： ​

sort 的比较器： ​

5. 排序算法与性能 ​

6. 稳定性 ​

7. 使用示例对比 ​

排序 int 数组： ​

排序自定义类型： ​

总结：如何选择？ ​

介绍一下std::sort函数的时间复杂度 ​

1. 底层算法：内省排序（Introsort） ​

2. 时间复杂度的保证 ​

3. 与其他排序函数的对比 ​

总结 ​

给我这些排序的特点、原理、cpp可实现代码，方便我学习以及亲自手敲代码

1. 选择排序（Selection Sort）

特点

原理

C++实现

2. 冒泡排序（Bubble Sort）

特点

原理

C++实现

3. 插入排序（Insertion Sort）

特点

原理

C++实现

4. 希尔排序（Shell Sort）

特点

原理

C++实现（步长采用n/2递减）

5. 快速排序（Quick Sort）

特点

原理

C++实现（随机枢轴优化）

6. 归并排序（Merge Sort）

特点

原理

C++实现

7. 堆排序（Heap Sort）

特点

原理

C++实现

8. 计数排序（Counting Sort）

特点

原理

C++实现（假设数据范围为[minVal, maxVal]）

9. 基数排序（Radix Sort）

特点

原理

C++实现（按低位排序，基数为10）

10. 桶排序（Bucket Sort）

特点

原理

C++实现（假设数据范围为[0,1)的浮点数）

11. 锦标赛排序（Tournament Sort）

特点

原理

C++实现（最小值锦标赛）

12. Tim排序

特点

原理

C++实现（简化版，实际实现复杂）

学习建议

如果我想偷懒调用库函数，如何写，或者调用?

1. 调用 `std::sort`（快速排序的优化版本，非稳定排序）

特点：

使用方法：

2. 调用 `std::stable_sort`（稳定排序）

特点：

使用方法：

3. 对自定义类型排序（需提供比较规则）

总结：

sort和qsort区别在哪里？

1. 所属标准与头文件

2. 函数原型与参数

`qsort` 原型：

`sort` 原型（简化版）：

3. 支持的数据类型

4. 比较函数的差异

`qsort` 的比较函数：

`sort` 的比较器：

5. 排序算法与性能

6. 稳定性

7. 使用示例对比

排序 `int` 数组：

排序自定义类型：

总结：如何选择？

介绍一下std::sort函数的时间复杂度

1. 底层算法：内省排序（Introsort）

2. 时间复杂度的保证

3. 与其他排序函数的对比

总结