STL __merge_without_buffer算法？ [英] STL __merge_without_buffer algorithm?

问题描述

在哪里可以得到C ++ STL中 __ merge_without_buffer（）中使用的算法的高级描述？我正在尝试以D编程语言重新实现此代码，并进行了一些增强。从阅读STL源代码开始，我似乎无法理解它在算法级别上的作用，因为有太多的底层细节使它难以理解。而且，我不想只是盲目地翻译代码，因为那样的话，如果它不起作用，我将不知道为什么，并且也无法添加我的增强功能。

Where can I get a decent high-level description of the algorithm used in __merge_without_buffer() in the C++ STL? I'm trying to reimplement this code in the D programming language, with some enhancements. I can't seem to grok what it's doing at the algorithmic level from just reading the STL source code because there are too many low-level details obscuring it. Also, I don't want to just blindly translate the code because then, if it didn't work I wouldn't know why, and I wouldn't be able to add my enhancements.

推荐答案

__ merge_without_buffer（）正在执行就地合并，作为合并就地合并排序的步骤。它以两个数据范围 [第一个，中间）和 [中间，最后）作为输入被排序。 len1 和 len2 参数等于两个输入范围的长度，即（中间-第一）和（最后-中间）。

__merge_without_buffer() is performing an in-place merge, as the merge step of an in-place merge sort. It takes as input two ranges of data [first, middle) and [middle, last) which are assumed to already be sorted. The len1 and len2 parameters are equal to the lengths of the two input ranges, namely (middle - first) and (last - middle) respectively.

首先，它选择一个 pivot 元素。然后，它将数据重新排列为 A1 B1 A2 B2 的顺序，其中 A1 是<$中元素的集合c $ c> [first，middle）小于枢轴， A2 是 [大于或等于枢轴， B1 是 [中间，最后一个]中的元素集小于中心点，并且 B2 是 [中，最后一个] 大于或等于枢轴。请注意，数据最初是按照 A1 A2 B1 B2 的顺序排列的，因此我们要做的只是将 A2 B1 放入 B1 A2 。这是通过调用 std :: rotate（）来完成的。

First, it picks a pivot element. Then, it rearranges the data into the order A1 B1 A2 B2, where A1 is the set of elements in [first, middle) that are less than the pivot, A2 is the set of elements in [first, middle) greater than or equal to the pivot, B1 is the set of elements in [middle, last) less than the pivot, and B2 is the set of elements in [middle, last) greater than or equal to the pivot. Note that the data is originally in the order A1 A2 B1 B2, so all we need to do is to turn A2 B1 into B1 A2. This is with a call to std::rotate(), which does just that.

现在我们已经从大于或等于这些元素的元素中分离出小于支点的元素（ A1 和 B1 ）枢纽（ A2 和 B2 ），因此现在我们可以递归合并两个子范围 A1 A2 和 B1 B2 。

Now we've separated out the elements which are less than the pivot (A1 and B1) from those that are greater than or equal to the pivot (A2 and B2), so now we can recursively merge the two subranges A1 A2 and B1 B2.

我们如何选择枢纽？在我正在研究的实现中，它从较大的子范围中选择中位数元素（即，如果 [first，middle）的元素要多于 [中，最后），它选择 [中，第一] 的中位数；否则，它选择 [中，最后））的中位数。由于已经对子范围进行了排序，因此选择中位数是微不足道的。这种枢纽选择可确保在递归合并两个子范围时，每个子问题不超过当前问题的大小的3/4，因为在最坏的情况下，至少有1/4的元素大于或小于枢纽

How do we choose a pivot? In the implementation I'm looking at, it chooses the median element from the larger subrange (i.e. if [first, middle) has more elements than [middle, last), it chooses the median of [first, middle); otherwise, it chooses the median of [middle, last)). Since the subranges are already sorted, choosing the median is trivial. This pivot choice ensures that when recursively merging the two subranges, each subproblem is no more than 3/4 the size of the current problem, because in the worst case, at least 1/4 of the elements are larger than or smaller than the pivot.

这是什么时间？ std :: rotate（）调用花费O（N）时间，并且我们对自己进行了两个递归调用。这相当于运行时间为O（N log N）。但是，请注意，这只是mergesort中的一个步骤：请记住，在mergesort中，您首先要对两个半部分进行递归排序，然后再进行合并。因此，mergesort运行时间的递归关系现在为：

What is the running time of this? The std::rotate() call takes O(N) time, and we make two recursive calls to ourselves. This equates to a running time of O(N log N). However, note that this is only one step in mergesort: remember that in mergesort you first recursively sort both halves and then merge. Thus, the recurrence relation for the running time of mergesort is now:

T（N）= 2T（N / 2）+ O（N登录N）

将其插入主定理，您会得到mergesort现在以O（N log ² N）时间运行！

Plug this into the Master theorem, and you get that mergesort now runs in O(N log² N) time!

作为有趣的最后一点，请考虑以下三种基于比较的排序算法的质量：

As an interesting final point, consider the following three qualities of a comparison-based sorting algorithm:

1. 就地


2. 稳定


3. 运行时间为O（N log N）

您通常只能一次获得其中的2个-quicksort使您拥有（1）和（3），mergesort使您拥有（2）和（3），而就地mergesort使您拥有（1）和（2）。基于非比较的排序（例如计数排序）可以实现全部3种，但是这些排序只能对某些数据类型进行排序。可能有一个基于比较的排序可以达到全部3个，但是如果有，我不知道它的存在，而且几乎可以肯定要复杂得多。

You can usually only get 2 of these at once - quicksort gets you (1) and (3), mergesort gets you (2) and (3), and an in-place mergesort gets you (1) and (2). Non-comparison-based sorts such as count sort can achieve all 3, but those sorts can only sort certain data types. It's possible there exists a comparison-based sort which achieves all 3, but if there is, I'm not aware of its existence, and it's almost certainly much more complicated.

这篇关于STL __merge_without_buffer算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！