3

我在哪里可以获得__merge_without_buffer()C++ STL 中使用的算法的高级描述?我正在尝试用 D 编程语言重新实现此代码,并进行一些增强。仅仅阅读 STL 源代码,我似乎无法理解它在算法级别上所做的事情,因为有太多的低级细节掩盖了它。此外,我不想只是盲目地翻译代码,因为那样的话,如果它不起作用,我将不知道为什么,并且我将无法添加我的增强功能。

4

1 回答 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 B1B1 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) 时间内运行!

作为有趣的最后一点,请考虑基于比较的排序算法的以下三个特性:

  1. 到位
  2. 稳定的
  3. 在 O(N log N) 时间内运行

您通常一次只能获得其中的 2 个 - 快速排序获得 (1) 和 (3),合并排序获得 (2) 和 (3),就地合并排序获得 (1) 和 (2)。非基于比较的排序(例如计数排序)可以实现全部 3 个,但这些排序只能对某些数据类型进行排序。可能存在实现所有 3 个的基于比较的排序,但如果存在,我不知道它的存在,而且它几乎肯定要复杂得多。

于 2009-01-13T05:36:49.873 回答