c++中如何对数组进行排序_c++数组排序算法汇总

std::sort 是对普通数组排序最简单可靠的方法，底层为 introsort，平均时间复杂度 O(n log n)，需传指针范围如 std::sort(arr, arr + 5)，避免手写快排的边界错误。

用 std::sort 对普通数组排序最简单可靠

绝大多数情况下，直接调用 std::sort 是最优解。它底层是 introsort（混合快排+堆排+插入排序），平均 O(n log n)，且经过高度优化，比手写快排更稳、更快。

注意：必须传入指针范围，不能直接传数组名（会退化为指针，丢失长度）。

• 对 int arr[5] 排序：用 std::sort(arr, arr + 5)，不是 std::sort(arr, arr + sizeof(arr))
• 若用 std::vector，写法更安全：std::sort(vec.begin(), vec.end())
• 自定义比较：传第三个参数，比如降序 std::sort(arr, arr + n, std::greater())

手动实现快排时，partition 边界容易出错

手写快排常见崩溃或死循环，基本都出在 partition 函数的 while 循环条件和指针移动顺序上。尤其当数组含重复元素或已有序时，边界越界或左右指针卡住很常见。

推荐使用「Lomuto 分区方案」并严格检查索引：

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

• 循环中 j （不是 ），避免访问 arr[high] 两次
• 返回前必须执行 std::swap(arr[i + 1], arr[high])，否则 pivot 位置错误
• 递归调用时，区间为 [low, pi - 1] 和 [pi + 1, high]，不能漏掉 +1/-1

对 std::array 或 std::vector 排序，别忘了包含头文件

新手常因漏掉 #include 导致 std::sort 报错，而编译器提示可能只显示 “not declared in this scope”，并不明确指出缺头文件。

• std::array a = {3,1,4,1,5}; → 排序写法同原生数组：std::sort(a.begin(), a.end())
• std::vector v = {3,1,4,1,5}; → 同样用 v.begin()/v.end()，支持动态大小
• 如果用 C++20，还可直接 std::ranges::sort(v)，但需额外包含

结构体数组排序必须提供合法的比较逻辑

对结构体数组调用 std::sort 时，若没传比较函数，编译器会尝试调用 operator。如果没定义，就报错；如果定义了但逻辑有误（比如未覆盖所有字段、返回非严格弱序），运行时可能行为异常（如排序不完整、崩溃）。

推荐显式传 lambda，清晰且不易出错：

struct Person {
    std::string name;
    int age;
};
std::vector people = {{"Alice", 30}, {"Bob", 25}};
std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return a.age < b.age; // 按年龄升序
});

• lambda 参数加 const Person& 避免拷贝开销
• 比较逻辑必须满足严格弱序：反对称、传递、不可比性可传递
• 若需多级排序（先按 age，age 相同时按 name），写成 a.age != b.age ? a.age

C++ 数组排序真正难的不是算法本身，而是指针边界、容器迭代器有效性、比较谓词的数学正确性——这些地方一错，轻则结果错，重则段错误，且很难调试。