std :: sort和std :: stable_sort有什么区别？ [英] What is the difference between std::sort and std::stable_sort?

问题描述

我想知道std :: sort和std :: stable_sort在功能，内存和硬件方面有何不同？ 文档提到将[first，last）范围内的元素升序排列。顺序，例如排序，但stable_sort保留具有相等值的元素的相对顺序。，但这对我来说没有意义。什么是相对顺序和等效值？

I would like to know how std::sort and std::stable_sort differ with respect to functionality, memory and hardware? The documentation mentions that "Sorts the elements in the range [first,last) into ascending order, like sort, but stable_sort preserves the relative order of the elements with equivalent values.", but that didn't make sense to me. What is the "relative order" and "equivalent values"?

推荐答案

是的，正如您所说，这不是

Yes, it's as you said, and this is not a concept unique to C++.

稳定排序保留了语义等效值的物理顺序。

std :: sort ：

不能保证相等元素的顺序被保留。

复杂度：： O（N·log（N）），其中 N = std :: distance（第一个，最后一个）比较

std :: stable_sort ：

保证相等元素的顺序得以保留。

复杂性： O（N· log ^ 2（N）），其中 N = std :: distance（first，last） cmp 的应用程序。如果有更多可用内存，则复杂度为 O（N·log（N））。

The order of equal elements is guaranteed to be preserved.
Complexity: O(N·log^2(N)), where N = std::distance(first, last) applications of cmp. If additional memory is available, then the complexity is O(N·log(N)).

含义是 std :: stable_sort 在执行时间方面无法达到同样高效的效果，除非可用附加内存就内存消耗而言，执行效率不高。

The implication is that std::stable_sort cannot be performed quite as efficiently in terms of execution time, unless "additional memory is available" in which case it is not being performed as efficiently in terms of memory consumption.

这篇关于std :: sort和std :: stable_sort有什么区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！