这不是家庭作业，我没有钱上学，所以我在高速公路上的收费站轮类工作时自学(漫长的夜晚，几乎没有顾客)

我试图通过首先思考实现一个简单的“合并排序”，如果你喜欢一些实际的学习，稍微拉伸(stretch)一下我的大脑，然后然后看看解决方案在我使用的手册上:“2008-08-21 | 算法设计手册 | Springer | Steven S. Skiena | ISBN-1848000693”。

我想出了一个解决方案，它使用数组作为缓冲区来实现“合并”步骤，我将其粘贴在下面。作者使用队列所以我想知道:

• 是否应该改用队列？
• 一种方法与另一种方法相比有哪些优势？ (显然他的方法会更好，因为他是顶级算法学家而我是初学者，但我不能完全确定它的优点，请帮助我)
• 影响他选择的权衡/假设是什么？

这是我的代码(为了完整起见，我也包括了我对拆分功能的实现，但我认为我们只是在审查这里的 merge 步骤；我不认为这是一个顺便说一下代码审查帖子，因为我的问题只针对一种方法，并且是关于它与另一种方法相比的性能):

package exercises;
public class MergeSort {
  private static void merge(int[] values, int leftStart, int midPoint,
      int rightEnd) {
    int intervalSize = rightEnd - leftStart;
    int[] mergeSpace = new int[intervalSize];
    int nowMerging = 0;
    int pointLeft = leftStart;
    int pointRight = midPoint;
    do {
      if (values[pointLeft] <= values[pointRight]) {
        mergeSpace[nowMerging] = values[pointLeft];
        pointLeft++;
      } else {
        mergeSpace[nowMerging] = values[pointRight];
        pointRight++;
      }
      nowMerging++;
    } while (pointLeft < midPoint && pointRight < rightEnd);
    int fillFromPoint = pointLeft < midPoint ? pointLeft : pointRight;
    System.arraycopy(values, fillFromPoint, mergeSpace, nowMerging,
        intervalSize - nowMerging);
    System.arraycopy(mergeSpace, 0, values, leftStart, intervalSize);
  }
  public static void mergeSort(int[] values) {
    mergeSort(values, 0, values.length);
  }
  private static void mergeSort(int[] values, int start, int end) {
    int intervalSize = end - start;
    if (intervalSize < 2) {
      return;
    }
    boolean isIntervalSizeEven = intervalSize % 2 == 0;
    int splittingAdjustment = isIntervalSizeEven ? 0 : 1;
    int halfSize = intervalSize / 2;
    int leftStart = start;
    int rightEnd = end;
    int midPoint = start + halfSize + splittingAdjustment;
    mergeSort(values, leftStart, midPoint);
    mergeSort(values, midPoint, rightEnd);
    merge(values, leftStart, midPoint, rightEnd);
  }
}

这是教科书中的引用解决方案:(它是用C语言编写的，所以我添加了标签)

merge(item_type s[], int low, int middle, int high)
{
  int i; /* counter */
  queue buffer1, buffer2; /* buffers to hold elements for merging */
  init_queue(&buffer1);
  init_queue(&buffer2);
  for (i=low; i<=middle; i++) enqueue(&buffer1,s[i]);
  for (i=middle+1; i<=high; i++) enqueue(&buffer2,s[i]);
  i = low;
  while (!(empty_queue(&buffer1) || empty_queue(&buffer2))) {
    if (headq(&buffer1) <= headq(&buffer2))
      s[i++] = dequeue(&buffer1);
    else
      s[i++] = dequeue(&buffer2);
  }
  while (!empty_queue(&buffer1)) s[i++] = dequeue(&buffer1);
  while (!empty_queue(&buffer2)) s[i++] = dequeue(&buffer2);
}

最佳答案

抽象地说，队列只是一些支持入队、出队、查看和清空操作的对象。它可以通过许多不同的方式实现(使用循环缓冲区、使用链表等)

从逻辑上讲，合并算法最容易用队列来描述。您从两个保存要合并的值的队列开始，然后对这些队列重复应用 peek、is-empty 和 dequeue 操作以重建单个排序序列。

在使用数组的实现中，您实际上在做与使用队列相同的事情。您刚刚选择了使用数组来实现这些队列。不一定比使用队列“更好”或“更差”。使用队列使合并算法的高级操作更加清晰，但可能会带来一些低效率(尽管如果没有基准测试就很难确定)。使用数组可能稍微更有效(同样，您应该测试一下!)，但可能会掩盖算法的高级操作。从 Skienna 的角度来看，使用队列可能更好，因为它使算法的高级细节变得清晰。从您的角度来看，由于性能问题，数组可能更好。

希望这对您有所帮助!

关于Java归并排序， "merge"这一步应该用队列还是数组来完成？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12062861/