1

我们有两个数组（未排序），容量为n和n+m。第一个数组有n 个元素。第二个数组有m个元素（另外还有n 个位置为更多元素保留）。

目标是合并两个数组并将结果以排序方式存储在第二个数组中，而不使用额外的空间。

目前，我使用快速排序对两个数组进行排序，然后使用合并排序将它们合并。有没有更有效的方法来实现这一点？？？

4

5 回答 5

2

您可以探索归并排序。

https://www.google.com/search?q=mergesort&ie=UTF-8&oe=UTF-8&hl=en&client=safari#itp=open0

或者根据大小，您可以对每个数组进行快速排序，然后使用合并排序技术将它们合并（或合并，然后快速排序）。

我会使用mergesort，它基本上通过单独排序每个数组，然后将它们按顺序放在一起

您正在查看合并排序的 O(nlogn) 和快速排序的 O(nlogn)，但快速排序可能是 O(n^2) 最坏的情况。

于 2013-04-23T11:48:14.580 回答
2

显然，最好的做法是将 N 的内容复制到 N+M 数组的空闲空间中，然后对 N+M 数组进行快速排序。

通过进行 2 次快速排序然后进行合并排序，您只会降低整个操作的效率。

这是一个心理练习，如果您必须对长度为 M 的数组进行排序，您会将其拆分为 2 个数组，M1 和 M2，对每个数组进行排序，然后将它们合并排序吗？不，如果你这样做了，你只会限制每次快速排序调用的可用信息，从而减慢进程。

那么，为什么要将两个起始数组分开？

于 2013-04-23T15:25:07.090 回答
0

如果我还想保证 O(n*log(n)) 行为，我将使用Heapsort的修改版本，它将使用这两个数组作为堆的基础，并将排序后的数据存储在附加部分中的数组。

这也可能比两个快速排序更快，因为它不需要额外的合并操作。当对小数组进行排序时，快速排序也非常慢（问题的大小没有提到问题的设置）。

于 2013-04-23T12:11:22.643 回答
0

让我们将较小的数组称为 N 数组，将另一个称为 M 数组。我假设 M 数组的元素最初位于 0 到 m-1 的位置。使用您最喜欢的技术对两个数组进行排序，这可能取决于其他标准，例如稳定性或限制最坏情况的行为。

if min(N) > max(M)
   copy N's elements over starting at location m [O(n) time]   
else
   move M's elements to the end of the M array (last down to first) [O(m) time]   
   if min(M) > max(N)
      copy N's elements over starting at location 0 [O(n) time for the copy]
   else
      perform classic merge: min of remaining m's and n's gets migrated
      to next available space in M [O(min(m,n) time]

总体而言，这主要由初始排序时间决定，合并阶段都是线性的。将 m 迁移到 M 数组的末尾可以保证没有空间冲突，因此根据您的规范，您不需要额外的侧存储。

于 2013-04-23T14:46:10.670 回答
0

如果您将存储在第二个数组中，那么您将使用额外的空间，但是您可以通过像这样帮助 GC 来最小化它：

  • 将两个数组加入第二个数组
  • 将先前的两个变量都设置为 null，以便它们有资格被垃圾收集
  • 对第二个数组进行排序，Arrays.sort(...)- O(n log(n))

查看此方法的 javadoc：

/**
  * Sorts the specified array into ascending numerical order.
  *
  * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
  * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
  * offers O(n log(n)) performance on many data sets that cause other
  * quicksorts to degrade to quadratic performance, and is typically
  * faster than traditional (one-pivot) Quicksort implementations.
  *
  * @param a the array to be sorted
  */
  public static void sort(int[] a) {
于 2013-04-23T12:06:04.750 回答