C++如何进行浮点数数组的快速排序？（自定义比较函数）

裘德小鎮的故事

发布时间：2026-02-26 07:21:07

251人浏览过

来源于php中文网

原创

std::sort 可以直接排序浮点数数组，因其默认使用 operator

std::sort 为什么不能直接排浮点数数组？

因为 std::sort 默认用 比较，而浮点数的 <code> 在极小差值下会失效——比如 <code>1e-16 级别的误差会让两个“逻辑相等”的数被误判大小，导致排序不稳定甚至崩溃（std::sort 要求比较函数满足严格弱序）。这不是 bug，是 IEEE 754 的必然结果。

实操建议：

立即学习“C++免费学习笔记（深入）”；

永远不要对 float 或 double 数组直接用默认 std::sort

必须传自定义比较函数，把“相等容忍”逻辑显式写进去

容忍阈值（epsilon）要和数据量级匹配：处理 1e6 级数值时，用 1e-10 可能不够，用 1e-3 又太松

怎么写一个安全的浮点数比较函数？

核心是先判断是否“数值上可视为相等”，再决定大小关系。别用 abs(a - b) 做唯一判断——它在跨数量级比较时会失效（比如比较 <code>1e20 和 1e20 + 1）。

实操建议：

立即学习“C++免费学习笔记（深入）”；

用相对误差： abs(a - b) ，再 fallback 到绝对误差防零除

把 epsilon 定义为 const double eps = 1e-9;，避免 magic number

函数签名必须是 bool cmp(double a, double b)，返回 true 表示 a 应排在 b 前面

示例：

Meituan CatPaw
美团推出的智能AI编程Agent

下载
const double eps = 1e-9;
auto float_less = [](double a, double b) {
    double diff = a - b;
    double scale = fmax(fabs(a), fabs(b));
    if (fabs(diff) <= eps * scale || (scale == 0 && fabs(diff) <= eps))
        return false; // 视为相等，不交换
    return diff < 0;
};
std::sort(arr, arr + n, float_less);
std::stable_sort 和 std::sort 选哪个？

如果数组里有大量“数值相等但来源不同”的浮点数（比如从不同传感器读来的近似值），且你希望它们保持原始相对顺序，就得用 std::stable_sort。但代价是：它通常比 std::sort 慢 20%–50%，且额外占用 O(n) 内存。

实操建议：

立即学习“C++免费学习笔记（深入）”；

只要没明确要求“相等元素保序”，一律用 std::sort

std::stable_sort 不解决精度问题——它照样依赖你提供的比较函数是否满足严格弱序

某些 STL 实现（如 libstdc++）对 double 有特殊优化，但不可依赖；统一走自定义比较最稳妥

排序后怎么验证结果是否靠谱？

浮点排序没法像整数那样用“相邻元素非递减”简单断言。一次 for 循环检查可能漏掉因精度累积导致的局部乱序（比如第 1000 个数比第 999 个略小，但差值在 epsilon 内）。

实操建议：

立即学习“C++免费学习笔记（深入）”；

验证重点不是“完全有序”，而是“没有明显反序”：遍历检查 arr[i+1] - arr[i] >= -eps

对首尾、中位数附近几个点做高精度打印（用 std::setprecision(17)），看是否符合预期分布

如果排序后用于后续计算（如积分、插值），建议在排序前先做一次 std::unique 配合自定义谓词去重——但注意：去重本身也要用同样 epsilon 逻辑

真正麻烦的是多维浮点数据或带权重的排序场景，这时候 epsilon 的尺度选择会更敏感，得按业务单位单独校准。