问题描述
C ++标准库中的std :: sort（）的复杂性是什么？应用哪种类型？是否有应用任何特定排序算法的规则？
What is the complexity of std::sort() in the C++ Standard Library? Which sort is applied? Is there any rule of applying any particular sorting algorithm there?
推荐答案
std :: sort 必须具有平均情况线性（n log n）时间复杂度。可以使用任何算法，只要满足时间复杂度要求。
std::sort must have average case linearithmic (n log n) time complexity. Any algorithm may be used so long as that time complexity requirement is met. There is no worst case time complexity requirement.
如果你想要一个保证的最坏情况时间复杂度函数，使用 std :: stable_sort ，其具有拟线性最坏情况时间复杂度（n log ^ 2 n）。
If you want a guaranteed worst case time complexity function, use std::stable_sort, which has quasilinear worst case time complexity (n log^2 n).
这篇关于在C ++标准库中，std :: sort（）的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！