排序一个向量，其中n个第一个元素已经被排序?

Consider a std::vector v of N elements, and consider that the n first elements have already been sorted withn < N and where (N-n)/N is very small:

考虑N个元素的std::向量v，考虑N个第一元素已经被N < N，其中(N- N)/N非常小:

Is there a clever way using the STL algorithms to sort this vector more rapidly than with a complete std::sort(std::begin(v), std::end(v)) ?

是否有一种聪明的方法使用STL算法对这个向量进行排序，而不是用一个完整的std::sort(std::begin(v)， std::end(v)) ?

EDIT: a clarification: the (N-n) unsorted elements should be inserted at the right position within the n first elements already sorted.

编辑:澄清一下:(n -n)未排序的元素应该插入到已排序的第n个元素中的正确位置。

EDIT2: bonus question: and how to find n ? (which corresponds to the first unsorted element)

附加问题:如何找到n ?(对应于第一个未排序元素)

7 个解决方案

#1

void foo( std::vector<int> & tab, int n ) {
     std::sort( begin(tab)+n, end(tab));
     std::inplace_merge(begin(tab), begin(tab)+n, end(tab));
}

for edit 2

编辑2

auto it = std::adjacent_find(begin(tab), end(tab),  std::greater<int>() );
if (it!=end(tab)) {
    it++;
    std::sort( it, end(tab));
    std::inplace_merge(begin(tab), it, end(tab));
}

#2

Sort the other range only, and then use std::merge.

只对其他范围进行排序，然后使用std::merge。

#3

The optimal solution would be to sort the tail portion independently and then perform in-place merge, as described here

最佳的解决方案是独立地对尾部进行排序，然后执行就地合并，如本文所述

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.5750

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.5750

The algorithm is quite convoluted and is usually regarded as "not worth the effort".

该算法相当复杂，通常被认为“不值得付出努力”。

Of course, with C++ you can use readily available std::inplace_merge. However, the name of that algorithm is highly misleading. Firstly, there's no guarantee that std::inplace_merge actually works in-place. And when it is actually in-place, there's no guarantee that it is not implemented as a full-blown sort. In practice it boils down to trying it and seeing whether it is good enough for your purposes.

当然，使用c++可以使用现成的std::inplace_merge。然而，该算法的名称具有高度的误导性。首先，不能保证std::inplace_merge确实有效。当它真正到位时，并不能保证它不是作为一种成熟的类型来实现的。在实践中，它可以归结为尝试它，看看它是否适合你的目的。

But if you really want to make it in-place and formally more efficient than a full sort, then you will have to implement it manually. STL might help with a few utility algorithms, but it does not offer any solid solutions of "just a few calls to standard functions" kind.

但是，如果您真的想让它就位并正式地比完全排序更有效，那么您将不得不手工实现它。STL可能对一些实用算法有所帮助，但它没有提供任何“只对标准函数进行一些调用”之类的可靠解决方案。

#4

Using insertion sort on N - n last elements:

在N - N最后一个元素上使用插入排序:

template <typename IT>
void mysort(IT begin, IT end) {
    for (IT it = std::is_sorted_until(begin, end); it != end; ++it) {
        IT insertPos = std::lower_bound(begin, it, *it);
        IT endRotate = it;
        std::rotate(insertPos, it, ++endRotate);
    }
}

#5

The Timsort sorting algorithm is a hybrid algorithm developed by Pythonista Tim Peters. It makes optimal use of already-sorted subsegments anywhere inside the array, including in the beginning. Although you may find a faster algorithm if you know for sure that in particular the first n elements are already sorted, this algorithm should be useful for the overall class of problems involved. Wikipedia describes it as:

Timsort排序算法是由python的Tim Peters开发的一种混合算法。它最优地利用了数组中任何地方的已经排序的子段，包括开始部分。虽然如果您确信前n个元素已经被排序，您可能会发现一个更快的算法，但是对于涉及的所有问题来说，该算法应该是有用的。*将它描述为:

The algorithm finds subsets of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently.

该算法查找已排序数据的子集，并使用这些知识更有效地对其余数据进行排序。

In Tim Peters' own words,

用蒂姆·彼得斯的话说，

It has supernatural performance on many kinds of partially ordered arrays (less than lg(N!) comparisons needed, and as few as N-1), yet as fast as Python's previous highly tuned samplesort hybrid on random arrays.

它在许多部分有序的数组(小于lg(N!)比较所需的性能，且只有N-1)上具有超乎寻常的性能，但速度与Python之前在随机数组上进行高度调优的samplesort杂交的速度一样快。

Full details are described in this undated text document by Tim Peters. The examples are in Python, but Python should be quite readable even to people not familiar with its syntax.

完整的细节在这个未标注日期的文本文档中由Tim Peters描述。示例是在Python中，但是即使对不熟悉其语法的人来说，Python也应该是可读的。

#6

Use std::partition_point (or is_sorted_until) to find n. Then if n-m is small do an insertion sort (linear search+std::rotate).

使用std::partition_point(或is_sorted_until)查找n，然后如果n-m很小，进行插入排序(线性搜索+std:::rotate)。

#7

I assume that your question has two aims:

我认为你的问题有两个目的:

• improve runtime (using a clever way)
• 改进运行时(使用一种巧妙的方式)
• with few effort (restricting to STL)
• 不费吹灰之力(仅限于STL)

Considering these aims, I'd strongly recommend against this specific optimization, unless you are sure that the effort is worth the benefit. As far as I remember, std::sort() implements the quick sort algorithm, which is almost as fast on presorted input as to determine, if / how-much-of the input is sorted.

考虑到这些目标，我强烈建议不要进行这种特定的优化，除非您确信这种努力是值得的。就我所知，std::sort()实现了快速排序算法，如果/ how- of输入被排序，那么它在预存输入上的速度几乎与确定输入的速度一样快。

Instead of meddling with std::sort you can try changing the data structure to a sorted/prioritized queue.

您可以尝试将数据结构更改为排序/优先队列。