5

【这是一道面试题。我找不到副本。]

一个数组包含两个子排序数组。给出一个就地算法对两个子数组进行排序。

例如： I/P：1 4 5 7 8 9 2 3 6 10 11 O/P：1 2 3 4 5 6 7 8 9 10 11

我考虑了就地合并排序、插入排序（因为子数组已经排序）和快速排序，但想不出比使用标准排序方法更复杂的解决方案。

请帮助我找到一种算法，该算法允许我们利用排序的子数组属性并导致比在输入上运行 Quicksort 更好的时间复杂度。

这是我想到的合并排序模拟，使用这个例子：

  1) For position 0, Comparing 1 & 2, 1 is smaller let it stay at it's original place
  2) For position 1, Comparing 2 & 4, 2 is smaller so swap 2 and 4
  3) For position 2, Comparison now is between 4 and 3 (5 > 4 anyways) swap 3 and 5
  4) For position 3, Comparison between 4 & 5, swap 4 and 7
  5) For position 4, Comparison between 7 & 5, swap 8 and 5 
  6) For position 5, Comparison between 7 & 8 (OUCH!!) it should have been between 7 & 6

似乎这个问题类似于对矩阵的排序行进行排序，其中就地合并太复杂了。

4

4 回答 4

6

请参阅http://comjnl.oxfordjournals.org/content/38/8/681.full.pdf+html了解用于解决此确切问题的线性时间算法，并说明在提出该解决方案时花费了多少精力。

我的猜测是面试官有一些他们认为有效的可爱答案，但事实并非如此。第二个最好的猜测是他们没有指定复杂性是有原因的。

在一次采访中，我实际上会说，“我不知道如何有效地做到这一点，尽管我确信有关于这个问题的研究。但这是一个低效的答案。” 然后我会做一些明显有效的事情。

于 2013-03-14T16:42:22.463 回答
4

有一个就地合并排序具有 O(n log n) 最坏情况的行为，但正如论文所说，“由于涉及的常数因素，该算法主要具有理论意义。” 见https://stackoverflow.com/a/2571104/56778

如果您不能分配一个与已排序子数组之一一样大的临时缓冲区，则就地合并将非常困难。

于 2013-03-14T03:48:51.343 回答
0 
    // since both are sorted use array b as min heap
    // if a[i] > b[0] (top of min-heap), exch it and heapify b
    // order : O(nlog(n))
   void inplaceMerge(vector<int>& a, vector<int>& b)
   {
     for (int i=0; i < a.size(); i++)  {
         if (a[i] > b[0]) {
                swap(a[i], b[0]);
                sink(b, 0, b.size()-1); // bubbleDown() operation in heap() 
         }
      }
      sort(b.begin(), b.end());   
    }

   void sink(vector<int>& b, int i, int n)
   {
            int j = 2*i + 1;
            while (j <= n) {
                 if (j+1 < n && b[j+1] < b[j]) j++;
                 if (b[j] < b[i]) swap(b[i], b[j]);
                 else break;
                 i = j;
                 j = 2*i + 1;
            }
   }
于 2013-07-25T12:29:19.923 回答
0

对于面试问题，在您的算法中，一旦交换结果数组就不再单独排序。您应该“冒泡”较大的交换元素，直到它到达正确的位置，然后继续。

为简单起见，让我们取 2 个数组，其中 topA 和 topB 作为当前位置（最初都是 0）。令所需的结果数组为 A[1..m]..B[1..n]。这是一个伪代码：

if (A[topA] < B[topB]) {
    swap (A[topA], B[topB])
    index = topB;
    while (B[index] < B[index + 1]) {
        swap(B[index], B[index + 1])
    }
    topB++
} else {
  topA++;
}

在上述每次运行结束时，生成的数组被排序并变小。这可以持续到其中一个阵列用完为止。然而，由于冒泡阶段，复杂度将大于 O(m+n)。

于 2013-03-14T05:23:03.677 回答