在原地对具有两个已排序子数组的数组进行排序

Question

一个数组包含两个子排序数组。请提供一种原地算法来对这两个子数组进行排序。

例如：输入：1 4 5 7 8 9 2 3 6 10 11，输出：1 2 3 4 5 6 7 8 9 10 11

我考虑使用原地归并排序、插入排序（由于子数组已经排序）和快速排序等方法，但是无法想到比使用标准排序方法更好的复杂度解决方案。

请帮助我找到一种算法，利用已排序的子数组属性，使得时间复杂度优于在输入上运行快速排序。

这是我想到的归并排序模拟，使用以下示例：

  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

看起来这个问题类似于对矩阵的排序，其中就地合并过于复杂。

- user1071840

---

考虑归并排序。 - phs

可能是重复的问题：如何使用O(n)时间和O(1)空间成本在原地合并两个已排序的整数数组 - Rafał Dowgird

Answer 1

请参考http://comjnl.oxfordjournals.org/content/38/8/681.full.pdf+html，这是一个线性时间算法用于解决这个确切的问题，并且显示了解决这个问题所需的努力程度。

我猜面试官可能有一个他们认为有效的聪明答案，实际上并不是。其次最好的猜测是他们没有指定复杂性的原因。

在面试中，我会说：“虽然我确定有关于这个问题的研究，但我不知道如何高效地解决它。不过，这里有一个低效率的答案。” 然后我会做一些显然可行的事情。

- btilly

Answer 2

有一种原地归并排序的最坏时间复杂度为O(n log n)，但正如论文所说，“由于涉及到常数因子，该算法主要是理论上的兴趣。”请参见https://dev59.com/f3E85IYBdhLWcg3w3Xn6#2571104

如果无法分配一个与已排序的子数组之一一样大的临时缓冲区，则原地合并变得非常困难。

- Jim Mischel

Answer 3

    // 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;
            }
   }

- Jimmy

---

欢迎来到Stack Exchange，Jimmy！在未来，更详细地解释你的方法会更有帮助。感谢你的贡献！ - Jesse Smith

Answer 4

有一种在这种情况下有效的间隙方法。代码将如下所示。

时间复杂度：O(n log n)

空间复杂度：O(1)

int[] merge(int[] a) {
  int tot=a.length;
  int gap=tot/2 + tot%2;
  while(gap > 0) {
   int p1=0, p2=gap;
   while(p2 < tot) {
     if(a[p1] > a[p2])
       swap(a, p1, p2);

     p1++;
     p2++;
   }
   p2 = nextgap(gap);
  }

  return a;
}

void swap(int[] a,int i,int j) {
   int temp=a[i];
   a[i]=a[j];
   a[j]=temp;
}

int nextgap(int gap) {
 if(gap<=1)
  return 0;
 return gap/2 + gap%2;
}

- Debashis

Answer 5

关于面试问题，根据你的算法，在交换后的数组中，各自不再是排序好的。你应该将较大的交换元素向下“冒泡”，直到它到达正确的位置，然后继续。

我们为了简单起见，假设有两个数组，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)。

- user1952500