检查向量是否排序的最佳算法

考虑多个CPU核心

它取决于您的平台和向量中的项数。你必须通过基准来找出最好的。

这是不可能回答的:有没有比检查v[i]<=v[i+1]的循环更快的东西?
用:没有。

因为…计算机现在有多个CPU/核心/超线程。因此,通过将检查的工作拆分为多个线程,利用计算机中的平行性可能要快得多,因此每个CPU可以并行地检查一个小范围。

最好是通过一个库函数来实现这一点,而不是自己实现它。新版本的图书馆将利用平行论。因此,如果您选择std::sort,那么当您针对较新的STL实现进行构建时,您可能会发现,它们将为您并行执行该操作,而不必担心它。我不知道是否有现成的STL版本已经做到了这一点,但值得坚持的是库函数,这样当您升级到这样的版本时,这种优化是为您而进行的,而不需要进行任何更改。

有比环路更快的吗 检查v[i]<=v[i+1]?

不。

如果您希望经常检查这一点,那么您可能需要创建一个包装类,该类保留一个以false开头的“sorted”标志,在每次添加项时设置为false,并添加一个成员函数sort(),在排序后将该标志设置为true。

最好的方法是使用 std::is_sorted :

is_sorted(v.begin(), v.end())

-)

std::adjacent_find(v.begin(), v.end(), std::greater<type>()) == v.end()

当然,我不知道你的问题域,所以如果我说的话不相关,请忽略我,但在我看来,如果我要求每次访问一个集合时都要对其进行排序,那么自然不排序的集合就像 vector<T> 可能不是最好的选择。

有没有比检查v[i]<=v[i+1]的循环更快的东西?

您将需要检查任何值以查看它是否被排序,因此它不会比O(N)更快,除非您在改变向量的同时自己跟踪更改,或者使用已经排序的数据结构。

还是每次调用sort都更好(尽管“v已经排序”的情况很常见)?

请记住,当列表已经排序(并且透视被错误地选择)时,会发生QuickSports最坏情况行为。为了避免这种行为,您可能需要检查std::stable_sort作为替换。

如果您希望列表非常接近排序,尝试修改 insertion sort . 如果列表已经排序,它只执行一次传递,并告诉您。如果列表非常接近排序,它将很快排序。如果列表未排序,则在进行一些交换后脱离排序,切换到快速排序(或稳定排序)。

C++- 11包含IsIn排序in & lt;

有没有比检查v[i]<=v[i+1]的循环更快的东西?

不。

但是,如果要执行检查来决定是否对向量进行排序,那么最好总是进行排序 如果 使用正确的排序算法,即std::stable_sort,而不是std::sort。

为了检查排序,您必须检查每个项目。所以v[i]<=v[i+1]是最快的检查。

正如其他人所指出的,确定排序状态的谓词是o(n)。但从你提到的分类旗,我想知道你是否不想要这样的东西:

我们的应用程序的基础库包括一个容器类,可以查询成员资格。下面是一个简图:

class ObjList {
public:
    ObjList() {};
    ~ObjList() {};

    bool isMember(const Item *);
    void add(const Item *, bool sort = false);

private:

    unsigned int last_sorted_d;

    bool sorted_d;
    unsigned int count_d;
    Item *store_d;
};

IsMeimes() 在上使用二进制搜索 排序范围 元素,然后对排序范围后的项进行线性搜索。根据程序员的选择,插入可以触发一类项目,或者不触发。例如,如果您知道将在一个紧密的循环中添加数千个项,那么在最后插入之前不要排序。

上面只是一个示意图,存储比指针数组更复杂,但是你明白了。

如果在插入项目时使用二进制搜索来查找插入点,则不会对其进行排序。

如果C++标准库实现包含AlgReTimm iSySoReD(),则是最好的选择。