在vector<int>中手动排序C++
我目前正在研究矢量是如何在C++中工作的。我很好地阅读和理解了它们的功能。
我正在研究用10,000个ints对向量对象进行排序的不同方法，我使用了std::sort方法和shell排序。
我注意到，向量的shell排序比排序简单的C样式数组要慢。我了解到这是因为“不支持在容器中间插入或移除快速元素”(http://www.cppreference.com/wiki/container/vector/start)。因此，很明显，具有大量随机访问的shell排序将非常慢。
我在想，在任何人的经验中，有什么更好的手工排序方法会是一个有10,000个ints的向量呢？这是你看到的一个学习练习！:)
回答 3
Stack Overflow用户
发布于 2011-04-10 00:17:14
尝试快速选择或快速排序算法(非常类似，但取决于您需要什么)。在任何情况下，这些只是相对简单和流行的算法-更重要的是，在实践中它们是快速的(尽管它们确实有坏的最坏的情况)。
致以敬意，
丹尼斯M.
Stack Overflow用户
发布于 2011-04-10 00:16:00
对于所有意图和目的，向量都是具有附加细节的数组。随机访问和C型数组一样快.在向量中间移除/插入元素是缓慢的，但C样式数组也是如此。Shell排序对向量的速度应该与对数组的速度一样快。对我来说，听起来你在做一些非正统的事。
快速排序或内向排序(std::sort是其中之一)应该是可用的最快的基于比较的排序。Mergesort比quicksort稍慢，但它对病理病例的易感性不高。平均而言，所有这些都需要O(n lg n)时间(对于快速排序来说是二次最坏的情况)。
编辑更新
代码:基于C阵列和向量的外壳。不管优化与否，对100万个元素进行排序所需的时间是向量的两倍，原因我不知道。看起来，当您访问一个向量时，STL正在执行一个错误检查。
Stack Overflow用户
发布于 2011-04-10 00:20:15
像快速排序这样的算法是对数据进行就地排序的理想方法，就像对向量的排序一样。也就是说，没有插入或删除，只是在固定大小的缓冲区中移动数据.
https://stackoverflow.com/questions/5608834
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号