面试题：C++中STL算法sort的基础性能优化问题

使用自定义比较函数：
- 原理：std::sort默认使用<进行比较。如果数组元素有特定的比较需求，例如整数数组需要按照绝对值大小排序等。自定义比较函数可以避免不必要的比较操作。比如，若比较操作复杂，自定义比较函数可以缓存中间结果等优化比较过程，从而提升性能。
- 示例：

#include <iostream>
#include <algorithm>
#include <vector>
// 自定义比较函数，按照绝对值大小排序
bool compareByAbs(int a, int b) {
    return std::abs(a) < std::abs(b);
}
int main() {
    std::vector<int> arr(10000);
    // 初始化数组
    for (int i = 0; i < 10000; ++i) {
        arr[i]=rand();
    }
    std::sort(arr.begin(), arr.end(), compareByAbs);
    return 0;
}

预排序（若数组有一定规律）：
- 原理：如果数组部分有序，先进行预排序，使得数组更接近有序状态。std::sort一般采用快速排序等算法，对于接近有序的数组，快速排序的性能会更好（减少不必要的划分操作）。例如，可以先使用插入排序对小段数组进行预排序，因为插入排序在数组接近有序时性能较好，时间复杂度接近O(n)。
- 示例：

#include <iostream>
#include <algorithm>
#include <vector>
// 插入排序函数
void insertionSort(std::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;
    }
}
int main() {
    std::vector<int> arr(10000);
    // 初始化数组
    for (int i = 0; i < 10000; ++i) {
        arr[i]=rand();
    }
    // 先对小段数组（如每100个元素一段）进行插入排序
    for (int i = 0; i < 10000; i += 100) {
        insertionSort(arr, i, std::min(i + 99, 9999));
    }
    // 再使用std::sort进行整体排序
    std::sort(arr.begin(), arr.end());
    return 0;
}

使用并行排序：
- 原理：现代CPU通常是多核的，并行排序可以充分利用多核优势。std::execution::par策略可以启用并行算法，std::sort在并行模式下会将数据划分到多个线程并行处理，加快排序速度。例如，在多核CPU上，并行排序能同时处理不同的数据块，减少整体排序时间。
- 示例：

#include <iostream>
#include <algorithm>
#include <vector>
#include <execution>
int main() {
    std::vector<int> arr(10000);
    // 初始化数组
    for (int i = 0; i < 10000; ++i) {
        arr[i]=rand();
    }
    std::sort(std::execution::par, arr.begin(), arr.end());
    return 0;
}

星途面试题库

面试题：C++中STL算法sort的基础性能优化问题

知识考点

面试题答案