performance - 使用自定义 API 进行排序 - removeAndAppend

Question

我们得到了一个 API -

removeAndAppend(val)
//Removes val and appends it to the given collection 

我们需要使用这个 API 对集合进行排序。

我知道我可以通过-

for i <- N to 1
    extract max //in O(n) 
    removeAndAppend.. //Consider this O(1)

这是二次...

问题是我能做得比这更好吗？

编辑:我们可以对集合进行 READ 操作，例如 - compare(val1, val2)

Answer 1

没有额外的数据结构/常量空间限制:

O(n<sup>2</sup>)您描述的算法本质上是 selection sort .

如果您可以访问某种迭代器(如果不能，您还能如何访问集合中的元素？)，我相信使用自定义 merge-sort 可以做得更好如下:

• 比较元素 1 和 2。removeAndAppend较小的，然后 removeAndAppend剩下的一个。对元素 3 和 4、5 和 6，...以及元素 n-1 和 n 执行相同的操作。

  现在您将对每个包含 2 个元素的子集合进行排序。

• 合并索引 (1,2) 和 (3,4)。为此，从头开始有 2 个迭代器。首先将 one 递增两次。然后像往常一样使用 removeAndAppend 进行合并排序。功能。对 (5,6) 和 (7,8)、(9,10) 和 (11,12)、... 以及 (n-3,n-2) 和 (n-1,n) 执行相同的操作。

  现在您将对每个包含 4 个元素的子集合进行排序。

• 合并与上述类似的大小为 4 的集合，然后合并 8、16、32 等，直到达到集合大小。

整个过程看起来像这样:

// setSize is how large sets we're currently merging
for setSize = 1; setSize <= n/2; setSize *= 2
  iterator left = begin
           right = begin
  for pos = 1 to n/(2*setSize)
    // here right and left are both at the beginning
    // even after the previous iteration of the loop,
    //   since we've removed and appended all other elements
    // so we only need to increase right by setSize
    right += setSize

    for i = 1 to 2*setSize
      if (left.value <= right.value)
        removeAndAppend(left)
      else
        removeAndAppend(right)

以上只是一个基本草稿，它可能不是 100% 正确，并且没有考虑到集合不是 2 的幂(这种情况经常发生)。在这种情况下您需要小心，否则您可能会回绕，或者走得不够远并最终得到部分排序的集合。

复杂性分析应该与常规合并排序几乎相同，并导致 O(n log n)运行时间。

有额外的数据结构/没有常量空间限制:

将所有元素提取到另一个集合中，在 O(n log n) 中排序(使用您选择的排序算法)并遍历排序集，调用 removeAndAppend在每个原始集合上。

如果您不允许提取元素，仍然可以通过使用索引集合来使用此方法，并且要进行比较，只需查找适用的元素即可。但是，为了提高效率，您需要按索引进行持续的时间查找。