这不是家庭作业,我没有钱上学,所以我一边在高速公路上的收费站轮班工作,一边自学(长夜,顾客很少)
我试图通过首先思考来实现一个简单的“合并排序”,如果你喜欢一些实际的学习,请稍微伸展一下我的大脑,然后查看我正在使用的手册上的解决方案:“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);
}