Cam*_*lby 7 c++ sorting shell stdvector
我目前正在研究Vector如何在C++中工作.我已经很好地阅读并理解了他们的功能.
我正在寻找使用10,000 int排序矢量对象的不同方法,我使用了std :: sort方法和shell排序.
我注意到,向量的shell排序比排序简单的C样式数组要慢.我了解到这是因为"不支持在容器中间插入或移除快速元素"(http://www.cppreference.com/wiki/container/vector/start).所以很明显,一个包含大量随机访问的shell排序会很慢.
我想知道在任何人体验到一个更好的手动排序方法对于一个10,000 英寸的矢量？这是你看到的学习练习!:)
对于所有意图和目的,向量是具有额外细节的数组.随机访问与C风格的数组一样快.在向量中间删除/插入元素很慢 - 但同样适用于C风格的数组.Shell排序应该在向量上和在数组上一样快.对我来说,这听起来像是在做一些非正统的事情.
Quicksort或introsort(std::sort是一个)应该是您可以使用的最快的基于比较的排序.Mergesort比quicksort略慢,但它没有quicksort对病理病例的易感性.平均而言,所有这些都需要O(n lg n)时间(快速排序的二次最坏情况).
编辑更新
代码:C-array和基于Vector的shellsorts.通过优化或不进行优化,排序100万个元素需要两倍的向量,这是我不知道的原因.看起来STL 在访问向量时会进行大量的错误检查.