我目前正在研究向量如何在 C++ 中工作。我已经阅读并很好地理解了它们的功能。
我正在研究对具有 10,000 个整数的向量对象进行排序的不同方法，我使用了 std::sort 方法和 shell 排序。
我注意到对向量进行 shell 排序比对简单的 C 样式数组进行排序要慢。我了解到这是因为“不支持在容器中间快速插入或删除元素”（http://www.cppreference.com/wiki/container/vector/start）。因此，显然具有大量随机访问的 shell 排序会非常慢。
我想知道在任何人的经验中，对于具有 10,000 个整数的向量，更好的手动排序方法是什么？这是一个你看到的学习练习！:)
出于所有意图和目的，向量是具有附加细节的数组。随机访问与 C 样式数组一样快。在向量中间删除/插入元素很慢 - 但同样适用于 C 样式数组。Shell 排序在向量上的速度应该与在数组上的速度一样快。对我来说，这听起来像是你在做一些非正统的事情。
Quicksort 或 introsort（std::sort是其中之一）应该是您可用的最快的基于比较的排序。Mergesort 比快速排序稍慢，但它没有快速排序对病理情况的敏感性。平均而言，所有这些都需要 O(n lg n) 时间（快速排序的二次最坏情况）。
编辑更新
代码：基于C 数组和向量的 shellsorts。无论是否进行优化，对 100 万个元素进行排序所需的时间是向量的两倍，原因我不知道。当您访问向量时，看起来 STL 正在执行大量错误检查。
诸如快速排序之类的算法非常适合就地排序数据，就像使用向量一样。也就是说，没有插入或删除，只是在固定大小的缓冲区中移动数据。