我在哪里可以获得__merge_without_buffer()C++ STL 中使用的算法的高级描述？我正在尝试用 D 编程语言重新实现此代码，并进行一些增强。仅仅阅读 STL 源代码，我似乎无法理解它在算法级别上所做的事情，因为有太多的低级细节掩盖了它。此外，我不想只是盲目地翻译代码，因为那样的话，如果它不起作用，我将不知道为什么，并且我将无法添加我的增强功能。
dsimcha
问问题
613 次
1 回答
12
__merge_without_buffer()正在执行就地合并，作为就地合并排序的合并步骤。它将两个数据范围作为输入，[first, middle)并且[middle, last)假定它们已经排序。和参数分别等于两个输入范围的长度，len1即和。len2(middle - first)(last - middle)
首先，它选择一个枢轴元素。然后，它将数据重新排列为 order A1 B1 A2 B2，其中A1是[first, middle)小于枢轴A2的元素集， 是[first, middle)大于或等于枢轴B1的元素集， 是[middle, last)小于枢轴的元素集，并且B2是[middle, last)大于或等于枢轴的元素集合。注意，数据本来就是按顺序排列的A1 A2 B1 B2，所以我们要做的就是转A2 B1成B1 A2. 这是对 的调用std::rotate()，它就是这样做的。
现在我们已经将小于枢轴 ( A1and B1) 的元素与大于或等于枢轴 ( A2and B2) 的元素分开了，所以现在我们可以递归地合并两个子范围A1 A2and B1 B2。
我们如何选择支点？在我正在查看的实现中，它从较大的子范围中选择中值元素（即，如果[first, middle)元素多于[middle, last)，它选择 的中值[first, middle)；否则，它选择 的中值[middle, last)）。由于子范围已经排序，因此选择中位数是微不足道的。这种枢轴选择确保在递归合并两个子范围时，每个子问题不超过当前问题大小的 3/4，因为在最坏的情况下，至少有 1/4 的元素大于或小于枢轴.
这个的运行时间是多少？std::rotate()调用需要 O(N) 时间，我们对自己进行了两次递归调用。这相当于 O(N log N) 的运行时间。但是，请注意这只是归并排序中的一个步骤：请记住，在归并排序中，您首先对两半进行递归排序，然后再合并。因此，归并排序运行时间的递推关系现在为：
T(N) = 2T(N/2) + O(N log N)
把它代入主定理，你会得到现在的归并排序在 O(N log 2 N) 时间内运行！
作为有趣的最后一点，请考虑基于比较的排序算法的以下三个特性：
- 到位
- 稳定的
- 在 O(N log N) 时间内运行
您通常一次只能获得其中的 2 个 - 快速排序获得 (1) 和 (3)，合并排序获得 (2) 和 (3)，就地合并排序获得 (1) 和 (2)。非基于比较的排序（例如计数排序）可以实现全部 3 个，但这些排序只能对某些数据类型进行排序。可能存在实现所有 3 个的基于比较的排序，但如果存在，我不知道它的存在，而且它几乎肯定要复杂得多。
于 2009-01-13T05:36:49.873 回答