STL排序算法详解

目录前言1. sort 算法1.1 算法原理1.2 函数签名1.3 特点1.4 应用举例2. partial_sort 算法2.1 算法原理2.2 函数签名2.3 特点2.4 应用举例3. stable_sort 算法3.1 算法原理3.2 函数签名3.3 特点3.4 应用举例4. 三种排序算法的性能比较4.1 测试环境4.2 测试代码4.3 测试结果4.4 性能分析5. 适用场景总结6. 代码优化建议7. 结论前言本文详细解析了STL中的三种排序算法sort混合排序不稳定O(nlogn)、partial_sort堆排序思想获取前N个元素O(nlogk)和stable_sort归并排序稳定但需额外空间。通过性能测试对比了它们的效率差异并提供了具体应用场景建议sort适用于通用排序partial_sort适合Top-K问题stable_sort用于需要保持元素顺序的情况。1. sort 算法1.1 算法原理sort算法是STL中最常用的排序算法它实现了一种混合排序算法通常是** introsort**内省排序结合了快速排序、堆排序和插入排序的优点快速排序用于处理大部分情况平均时间复杂度为 O(n log n)堆排序当快速排序的递归深度超过阈值时使用保证最坏情况时间复杂度为 O(n log n)插入排序当数据量较小时使用对于小规模数据效率更高1.2 函数签名templatetypename RandomIt void sort(RandomIt first, RandomIt last); templatetypename RandomIt, typename Compare void sort(RandomIt first, RandomIt last, Compare comp);1.3 特点不稳定排序相等元素的相对顺序可能会改变原地排序不需要额外的存储空间时间复杂度平均 O(n log n)最坏 O(n log n)空间复杂度O(log n)用于递归调用栈1.4 应用举例例1基本用法#include iostream #include vector #include algorithm int main() { std::vectorint v {5, 2, 9, 1, 5, 6}; std::sort(v.begin(), v.end()); std::cout Sorted: ; for (int num : v) { std::cout num ; // 输出: 1 2 5 5 6 9 } std::cout std::endl; return 0; }例2使用自定义比较函数#include iostream #include vector #include algorithm int main() { std::vectorint v {5, 2, 9, 1, 5, 6}; std::sort(v.begin(), v.end(), [](int a, int b) { return a b; // 降序排序 }); std::cout Sorted in descending order: ; for (int num : v) { std::cout num ; // 输出: 9 6 5 5 2 1 } std::cout std::endl; return 0; }2. partial_sort 算法2.1 算法原理partial_sort算法用于对序列的前 N 个元素进行排序而不是对整个序列排序。它使用堆排序的思想首先构建一个大小为 N 的最大堆然后遍历剩余元素将每个元素与堆顶元素比较如果当前元素小于堆顶元素则替换堆顶并重新调整堆最后对堆中的元素进行排序2.2 函数签名templatetypename RandomIt void partial_sort(RandomIt first, RandomIt middle, RandomIt last); templatetypename RandomIt, typename Compare void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp);2.3 特点不稳定排序相等元素的相对顺序可能会改变原地排序不需要额外的存储空间时间复杂度O(n log k)其中 k 是要排序的元素个数即 middle - first空间复杂度O(1)不需要额外空间2.4 应用举例例1获取前N个最小元素#include iostream #include vector #include algorithm int main() { std::vectorint v {5, 2, 9, 1, 5, 6, 3, 8, 7, 4}; // 排序前5个元素 std::partial_sort(v.begin(), v.begin() 5, v.end()); std::cout First 5 sorted elements: ; for (int i 0; i 5; i) { std::cout v[i] ; // 输出: 1 2 3 4 5 } std::cout std::endl; std::cout Remaining elements: ; for (int i 5; i v.size(); i) { std::cout v[i] ; // 输出: 9 6 8 7 5 } std::cout std::endl; return 0; }例2获取前N个最大元素#include iostream #include vector #include algorithm int main() { std::vectorint v {5, 2, 9, 1, 5, 6, 3, 8, 7, 4}; // 排序前5个最大元素 std::partial_sort(v.begin(), v.begin() 5, v.end(), std::greaterint()); std::cout First 5 largest elements: ; for (int i 0; i 5; i) { std::cout v[i] ; // 输出: 9 8 7 6 5 } std::cout std::endl; return 0; }3. stable_sort 算法3.1 算法原理stable_sort算法是一种稳定的排序算法它保证相等元素的相对顺序不变。通常实现为归并排序将序列递归地分成两半对每一半进行排序将排序后的两半合并成一个有序序列3.2 函数签名templatetypename RandomIt void stable_sort(RandomIt first, RandomIt last); templatetypename RandomIt, typename Compare void stable_sort(RandomIt first, RandomIt last, Compare comp);3.3 特点稳定排序相等元素的相对顺序保持不变非原地排序需要额外的存储空间时间复杂度平均 O(n log n)最坏 O(n log n)空间复杂度O(n)需要额外的存储空间用于归并3.4 应用举例例1基本用法#include iostream #include vector #include algorithm int main() { std::vectorint v {5, 2, 9, 1, 5, 6}; std::stable_sort(v.begin(), v.end()); std::cout Stably sorted: ; for (int num : v) { std::cout num ; // 输出: 1 2 5 5 6 9 } std::cout std::endl; return 0; }例2稳定排序的重要性#include iostream #include vector #include algorithm struct Person { std::string name; int age; Person(const std::string n, int a) : name(n), age(a) {} }; int main() { std::vectorPerson people { {Alice, 25}, {Bob, 30}, {Charlie, 25}, {David, 30} }; // 先按年龄排序 std::sort(people.begin(), people.end(), [](const Person a, const Person b) { return a.age b.age; }); std::cout After sort (unstable): std::endl; for (const auto p : people) { std::cout p.name ( p.age ) std::endl; } // 重新初始化 people { {Alice, 25}, {Bob, 30}, {Charlie, 25}, {David, 30} }; // 用stable_sort按年龄排序 std::stable_sort(people.begin(), people.end(), [](const Person a, const Person b) { return a.age b.age; }); std::cout \nAfter stable_sort: std::endl; for (const auto p : people) { std::cout p.name ( p.age ) std::endl; } return 0; }4. 三种排序算法的性能比较4.1 测试环境硬件Intel Core i5 处理器8GB 内存软件Visual Studio 2022C17数据规模100,000 个随机整数4.2 测试代码#include iostream #include vector #include algorithm #include random #include chrono void test_sort() { const int size 100000; std::vectorint v(size); // 生成随机数据 std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution dist(1, 1000000); for (int i 0; i size; i) { v[i] dist(gen); } // 测试 sort std::vectorint v1 v; auto start std::chrono::high_resolution_clock::now(); std::sort(v1.begin(), v1.end()); auto end std::chrono::high_resolution_clock::now(); auto duration std::chrono::duration_caststd::chrono::milliseconds(end - start); std::cout sort: duration.count() ms std::endl; // 测试 partial_sort (前50000个元素) std::vectorint v2 v; start std::chrono::high_resolution_clock::now(); std::partial_sort(v2.begin(), v2.begin() 50000, v2.end()); end std::chrono::high_resolution_clock::now(); duration std::chrono::duration_caststd::chrono::milliseconds(end - start); std::cout partial_sort: duration.count() ms std::endl; // 测试 stable_sort std::vectorint v3 v; start std::chrono::high_resolution_clock::now(); std::stable_sort(v3.begin(), v3.end()); end std::chrono::high_resolution_clock::now(); duration std::chrono::duration_caststd::chrono::milliseconds(end - start); std::cout stable_sort: duration.count() ms std::endl; } int main() { std::cout Testing sorting algorithms with 100,000 elements... std::endl; test_sort(); return 0; }4.3 测试结果排序算法平均运行时间 (ms)特点sort15-25不稳定原地排序平均 O(n log n)partial_sort (前50%)10-18不稳定原地排序O(n log k)stable_sort20-30稳定需要额外空间O(n log n)4.4 性能分析sort最快的通用排序算法适用于需要完整排序的场景空间开销小partial_sort当只需要前 N 个元素有序时比完整排序更快特别适用于 Top-K 问题时间复杂度与 K 有关K 越小性能越好stable_sort当需要保持相等元素的相对顺序时使用由于需要额外的存储空间通常比 sort 慢适用于对包含多个字段的对象进行排序的场景5. 适用场景总结算法适用场景不适用场景sort大多数排序场景对稳定性无要求需要保持元素相对顺序的场景partial_sortTop-K 问题只需要部分元素有序需要完整排序的场景stable_sort需要保持相等元素相对顺序的场景对空间使用有严格限制的场景6. 代码优化建议选择合适的排序算法如果只需要前 N 个元素有序使用partial_sort如果需要保持元素相对顺序使用stable_sort其他情况使用sort优化比较函数尽量使用简单的比较函数对于复杂对象考虑使用成员函数或 lambda 表达式数据预处理对于大规模数据可以考虑先进行数据清洗或预处理对于几乎有序的数据stable_sort可能表现更好内存管理对于stable_sort确保有足够的内存空间对于大规模数据可以考虑分块处理7. 结论STL 提供了多种排序算法每种算法都有其特定的适用场景sort是最通用、最高效的排序算法适用于大多数场景partial_sort适用于只需要部分元素有序的场景如 Top-K 问题stable_sort适用于需要保持相等元素相对顺序的场景选择合适的排序算法可以显著提高程序的性能和正确性根据具体的应用场景和需求选择最合适的排序方法是每个 C 开发者应该掌握的技能。