首页 > 文章列表 > C++ 搜索和排序函数的性能比较

C++ 搜索和排序函数的性能比较

488 2025-01-22

性能最佳的 C++ 搜索和排序函数:搜索: std::binary_search(O(log n))排序: std::sort(O(n log n))

C++ 搜索和排序函数的性能比较

C++ 搜索和排序函数的性能比较

简介

在许多编程应用中,搜索和排序算法是不可或缺的。C++ 标准库提供了各种各样的搜索和排序函数,涵盖了不同的复杂度和实现。本文将比較 C++ 搜索和排序函数的性能,并提供一个实战案例来说明它们的应用。

函数比较

搜索函数

函数时间复杂度用途
std::findO(n)在容器中查找第一个匹配元素
std::binary_searchO(log n)在已排序容器中查找元素
std:: lower/upper_boundO(log n)返回已排序容器中指定元素的第一个下限/上限迭代器

排序函数

函数时间复杂度用途
std::sortO(n log n)泛型排序算法,主要用于未排序容器
std::stable_sortO(n log n)稳定排序算法,保持相等元素的相对顺序
std:: partial_sortO(n)部分排序算法,对容器的前 n 个元素进行排序
std:: nth_elementO(n)选择算法,将容器中的第 n 个元素排序到正确的位置

实战案例

考虑以下问题:在一个包含 100 万个整数的数组中,查找给定整数并计算排序后的数组中指定整数的索引。

搜索

由于数组很大,因此使用二分查找 (std::binary_search) 是明智的选择:

bool found = std::binary_search(array.begin(), array.end(), target);

排序

对于大数组, std::sort 是一个可靠且高效的选项:

std::sort(array.begin(), array.end());

索引计算

一旦数组排序,就可以使用 std:: lower_bound 轻松计算目标整数的索引:

auto it = std::lower_bound(array.begin(), array.end(), target);
int index = std::distance(array.begin(), it);

性能分析

在具有 100 万个元素的数组上的测试表明,对于搜索和排序,std::binary_searchstd::sort 显着快于其他函数。性能差异如下:

函数搜索时间 (微秒)排序时间 (微秒)
std::find13001600000
std::binary_search20200000
std::lower_bound20-
std::sort-200000
std::stable_sort-220000
std::partial_sort-120000
std::nth_element-110000