Java的归并，如若＆QUOT;合并＆QUOT;步骤与队列或数组做了什么？ [英] Java mergesort, should the "merge" step be done with queues or arrays?

问题描述

这是不做作业，我没有钱上学，所以我自学而轮班工作，在收费站上高速公路（漫长的夜晚与一些客户）

我是想实现一个简单的归并通过的想的第一，拓展我的大脑，如果你喜欢的一些实际的学习，而则很少的望着解决方案说明书上我使用。2008-08-21 |算法设计手册|斯普林格|由史蒂芬S. Skiena | ISBN-1848000693

我想出了一个解决方案，实现了合并使用数组作为缓冲区一步，我下面粘贴。笔者采用排队，所以我在想：

• 在使用时应队列呢？
• 什么是一种方法的VS其他优势？ （很明显，他的方法会更好，因为他是一个顶级algorist，我是个初学者，但我不能完全查明它的优势，帮我请）
• 什么是权衡/是支配他的选择？
假设

下面是我的code（我包括我的执行分离功能，以及出于完整性的，但我认为我们只是检讨合并一步在这里，我不相信这是因为我的问题是具体到只有一个方法，并对其性能相比于其它的方式）一个code审查后：

 包练习;
公共类归并{
  私有静态无效合并（INT []价值观，诠释leftStart，INT中点，
      INT rightEnd）{
    INT intervalSize = rightEnd  -  leftStart;
    INT [] mergeSpace =新INT [intervalSize]
    INT nowMerging = 0;
    INT pointLeft = leftStart;
    诠释pointRight =中点;
    做 {
      如果（值[pointLeft]其中; =值[pointRight]）{
        mergeSpace [nowMerging] =值[pointLeft]
        pointLeft ++;
      } 其他 {
        mergeSpace [nowMerging] =值[pointRight]
        pointRight ++;
      }
      nowMerging ++;
    }而（pointLeft＆LT;中点和放大器;＆安培; pointRight＆LT; rightEnd）;
    INT fillFromPoint = pointLeft＆LT;中点 ？ pointLeft：pointRight;
    System.arraycopy（值，fillFromPoint，m​​ergeSpace，nowMerging，
        intervalSize  -  nowMerging）;
    System.arraycopy（mergeSpace，0，价值观，leftStart，intervalSize）;
  }
  公共静态无效归并（INT []值）{
    归并（值，0，values​​.length）;
  }
  私有静态无效归并（INT []价值观，诠释开始，诠释完）{
    INT intervalSize =结束 - 启动;
    如果（intervalSize 2）{
      返回;
    }
    布尔isIntervalSizeEven = intervalSize％2 == 0;
    INT splittingAdjustment = isIntervalSizeEven？ 0：1;
    INT halfSize = intervalSize / 2;
    INT leftStart =启动;
    INT rightEnd =结束;
    INT中点=启动+ halfSize + splittingAdjustment;
    归并（值，leftStart，中点）;
    归并（值，中点，rightEnd）;
    合并（值，leftStart，中点，rightEnd）;
  }
}
 

下面是从教科书的参考解决方案：（这在C所以我加入了标签）

 合并（ITEM_TYPE S []，INT低，诠释中间，诠释高）
{
  INT I; /* 计数器 */
  队列缓冲器1，缓冲器2; / *缓冲区来承载用于合并元素* /
  init_queue（安培;缓冲器1）;
  init_queue（安培;缓冲器2）;
  对于（i =低; I＆LT; =中间;我++）入队（放大器;缓冲器1，S [I]）;
  对于（I =中等+ 1; I＆LT; =高;我++）入队（放大器;缓冲器2，S [I]）;
  I =低;
  而（（empty_queue（安培;！缓冲器1）|| empty_queue（安培;缓冲器2）））{
    如果（headq（安培;缓冲器1）＆LT; = headq（安培;缓冲器2））
      S [我++] =出队（安培;缓冲器1）;
    其他
      S [我++] =出队（安培;缓冲器2）;
  }
  （！empty_queue（安培;缓冲器1）），而S [我++] =出队（安培;缓冲器1）;
  （！empty_queue（安培;缓冲器2）），而S [我++] =出队（安培;缓冲器2）;
}
 

解决方案

抽象地，一个队列就是支持入队，出队，偷看，而且是空操作某个对象。它可以在许多不同的方式来实现（使用循环缓冲器，使用链表等）

从逻辑上说，该合并算法是最容易描述排队的条款。你开始用两个队列持有的价值观融合在一起，然后重复应用偷看，是空的，并在这些队列队列操作重建一个排序序列。

在您的使用实现数组，你实际上在做同样的事情，如果你使用的队列。你刚才选择实施使用数组的队列。没有一定比用队列好或差。使用队列使得合并算法更清晰的高位运行，但可能会引进一些低效率（尽管它很难说肯定没有基准）。使用数组可能会略微高效（同样，你应该测试这个！），但可能会掩盖算法的高位运行。从Skienna的角度来看，使用队列可能会更好，因为它使算法清晰的高层次细节。从您的角度来看，数组可能是因为性能问题越好。

希望这有助于！

This is not homework, I don't have money for school so I am teaching myself whilst working shifts at a tollbooth on the highway (long nights with few customers)

I was trying to implement a simple "mergesort" by thinking first, stretching my brain a little if you like for some actual learning, and then looking at the solution on the manual I am using: "2008-08-21 | The Algorithm Design Manual | Springer | by Steven S. Skiena | ISBN-1848000693".

I came up with a solution which implements the "merge" step using an array as a buffer, I am pasting it below. The author uses queues so I wonder:

• Should queues be used instead?
• What are the advantages of one method Vs the other? (obviously his method will be better as he is a top algorist and I am a beginner, but I can't quite pinpoint the strengths of it, help me please)
• What are the tradeoffs/assumptions that governed his choice?

Here is my code (I am including my implementation of the splitting function as well for the sake of completeness but I think we are only reviewing the merge step here; I do not believe this is a Code Review post by the way as my questions are specific to just one method and about its performance in comparison to another):

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

Here is the reference solution from the textbook: (it's in C so I am adding the tag)

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

解决方案

Abstractly, a queue is just some object that supports the enqueue, dequeue, peek, and is-empty operations. It can be implemented in many different ways (using a circular buffer, using linked lists, etc.)

Logically speaking, the merge algorithm is easiest to describe in terms of queues. You begin with two queues holding the values to merge together, then repeatedly apply peek, is-empty, and dequeue operations on those queues to reconstruct a single sorted sequence.

In your implementation using arrays, you are effectively doing the same thing as if you were using queues. You have just chosen to implement those queues using arrays. There isn't necessarily "better" or "worse" than using queues. Using queues makes the high-level operation of the merge algorithm clearer, but might introduce some inefficiency (though it's hard to say for certain without benchmarking). Using arrays might be slightly more efficient (again, you should test this!), but might obscure the high-level operation of the algorithm. From Skienna's point of view, using queues might be better because it makes the high-level details of the algorithm clear. From your point of view, arrays might be better because of the performance concerns.

Hope this helps!

这篇关于Java的归并，如若＆QUOT;合并＆QUOT;步骤与队列或数组做了什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！