c++如何实现内存数据的快速排序并存入文件【技巧】-C++-PHP中文网

直接用 std::sort 更优，因其底层为 introsort（快排+堆排+插入排序混合），平均与最坏均为 O(n log n)，且优化充分、缓存友好；手写快排易栈溢出、被恶意数据卡成 O(n²)。

c++如何实现内存数据的快速排序并存入文件【技巧】

std::sort 为什么比手写快排更值得用

直接用 std::sort，别自己实现快排——它底层是 introsort（混合堆排+快排+插入排序），对小数组自动切到插入排序，对退化情况自动切到堆排，平均和最坏都是 O(n log n)，且高度优化、内联友好、缓存局部性好。自己写的递归快排容易栈溢出，三数取中不全还可能被恶意数据卡成 O(n²)。

实操建议：

确保数据在连续内存中（如 std::vector 或裸指针数组），std::sort 对随机访问迭代器效率最高
若元素较大（如含字符串或指针的结构体），优先按 key 排序：用 std::sort(v.begin(), v.end(), [](const auto& a, const auto& b) { return a.id
避免在排序时频繁调用虚函数或锁——这些会破坏分支预测，拖慢 2–3 倍

写文件前先 reserve + resize 避免反复 realloc

如果排序后要写入二进制文件（比如 std::vector 全量 dump），别边排序边 push_back，也别用 std::ofstream 格式化输出——那会把每个数转成字符串再写，慢一个数量级。

实操建议：

排序前确认容量：v.reserve(n); v.resize(n);，避免中间扩容拷贝
二进制写入用 write()：out.write(reinterpret_cast(v.data()), v.size() * sizeof(int));
务必检查 out.good() 或 !out，磁盘满或权限不足时 write() 不抛异常，只置 failbit

大数组（>100MB）要分块排序+归并，别硬塞进内存

当数据远超物理内存（比如 1GB 数据在 512MB 内存机器上），std::sort 会触发大量 swap，IO 成瓶颈，速度暴跌。这时得用外部排序：分段读入 → 排序 → 写临时文件 → 多路归并。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

实操建议：

每块大小设为可用内存的 70%（留余地给归并缓冲区），例如 400MB 内存就取 280MB 块
临时文件命名加序号（tmp_001.bin, tmp_002.bin），避免冲突；用 std::tmpfile() 更安全但不可跨进程
归并时用最小堆（std::priority_queue）管理各块首元素，每次取最小值写入主文件，再从对应块加载下一个

fstream 默认不缓冲，记得 setbuf 或用 mmap 加速写入

std::ofstream 默认使用小缓冲区（通常 8KB），对大块数据写入极其低效——每写几次就 flush 一次系统调用。而 mmap 在 Linux/macOS 上可绕过 stdio 缓冲，直接映射文件页写入，吞吐接近内存拷贝。

实操建议：

手动设置大缓冲：char buf[1pubsetbuf(buf, sizeof(buf));（注意必须在 open 前调用）
Linux 下用 mmap（需）：先 ftruncate 扩容，再 mmap(nullptr, size, PROT_WRITE, MAP_SHARED, fd, 0)，然后 memcpy 排序后数据过去，最后 msync 和 munmap
Windows 用 CreateFileMapping + MapViewOfFile，原理相同，但 API 更啰嗦