Eel*_*lke 27
实现可以自由使用他们想要的任何有效排序算法,因此这是高度依赖于实现的
但是我已经看到了libstdc ++在linux和libc ++上使用的性能比较,这是Apple/LLVM开发的新C++库.这两个库对排序或反向排序的数据非常有效(比随机列表快得多),新的库比旧的快得多,并且识别出更多的模式.
确定你应该考虑做自己的基准测试.
- 几个月前,我问Howard Hinnant他是如何在libc ++中实现`std :: sort`的.他的实现确实检查了排序和反向排序的输入,不仅在"完整"级别,而且在递归的每个级别,因此部分排序的输入也受益于加速.他认为在"混乱"案件中牺牲一些表现是非常重要的. (16认同)
- 澄清.libc ++实际上并没有在每个级别执行`is_sorted`检查(这会烧掉太多的cpu).但它接近于此.我相信libc ++在排序的序列上进行2N比较(并且没有交换)(`is_sorted`仅对排序的序列进行N次比较).libc ++在每个分区阶段计算交换.如果没有完成交换,则libc ++会切换到每个分区的"部分"插入排序.如果需要插入多个元素,则此插入排序将中止.回想一下,插入排序只对排序序列进行N次比较(并且没有移动). (16认同)
- -1:实际上,实现必须提供一个`std :: sort`,其中`Complexity:大约N log N(其中N == last-first)平均比较.(25.3.1.1 _Sorting_ [lib.sort]),所以允许的排序功能集是有限的. (6认同)
- msvc 2010(Dinkumware,我认为)中提供的STL也与Matthieu提到的类似.它与在输入上调用`is_sorted`不同,而是在快速排序分区中构建对部分排序的子范围的检查,因此对部分排序的序列很有用. (5认同)
- @Eelke:当然它们可以自由变化,但是在一组_non_-无限的算法中,我恐怕会使你的短语失效_"实现可以自由使用他们想要的任何排序算法,所以这是高度依赖于实现的"_ . (4认同)
- @Eelke:对于排序列表,冒泡排序非常_efficient_(O(n)).然而,该标准不允许它作为`std :: sort`的基础算法. (3认同)
- @phresnel你的行为就像一个无知的人.对于任何受过教育的人来说,"有效排序"的默认含义是O(N log N)比较.标准本身并未提及我们对"平均"部分的平均值 - 一位称职的从业者应该知道这一点.在Eelke的答案中,"高效"也是如此.(在C++ 14中注意,它不再是平均案例复杂性,而是最坏情况.) (2认同)
- @Eponymous:对于有工作的人来说,"默认含义"与实际商业案例无关.不同问题需要不同的算法.如果我的业务要求是"需要在2小时内完成",是的,我可以回到你认为的"默认含义".如果我的业务要求是"为1700个客户中的每一个,每秒两次计算其跟踪代码的订购前五名(十亿分之一)",则默认含义为零.如果我的问题是要进行销售,那么一个称职的人不会回到名字叫,顺便说一句. (2认同)
iam*_*ind 20
不.此外,is_sorted()调用任何STL实现是不合逻辑的.因为,is_sorted()已经可以作为一个独立的.并且许多用户可能不希望在他们已经知道他们的容器未被分类时不必要地浪费执行周期来调用该功能.
STL也应遵循C++理念:" 按使用付费 ".
- @Lex Fridman:这意味着如果你使用它就会花费_only_.`std :: sort`不会调用`std :: is_sorted`,因为`std :: sort`除了它自己之外还会产生`std :: is_sorted`的成本.也就是说,如果你想要阻止`std :: sort`一个排序列表的NlogN,那么_you_要支付调用`std :: is_sorted`的价格.此外,如果您有几乎排序的列表,您应该使用冒泡排序或其他具有良好排序特征的其他排序列表. (15认同)
- @Martin:已经排序的列表是几种类型的O(n),其中大多数执行比冒泡排序更好.例如,插入排序.(Quicksort可以用这种方式编写,但我不认为最常见的实现是....) (4认同)
- @Billy:这就是为什么原始评论还提到其他排序**<quote>使用冒泡排序或具有良好排序特征的其他东西</ quote>**.这就是你用**表达你感叹的方式,看起来你怀疑冒泡排序对于几乎排序的列表具有良好的特征. (4认同)
- "按使用付费"是什么意思？ (2认同)
- @Lex,用Bjarne Stroustrup的话说,"只为你使用的东西付钱."我不记得他在哪个采访中说过这个.但这个短语很容易在网上找到. (2认同)
How*_*ant 11
哇!你一直在优化吗？
您平台上的代码结果(请注意垂直轴上的值).
- 请参阅 http://stackoverflow.com/questions/6567326/does-stdsort-check-if-a-vector-is-already-sorted/6567699#6567699 下的第三条评论 (2认同)