英文:
Can someone code and explain the merge portion of mergesort?
问题
我一直在尝试理解归并排序中合并部分，已经花了几个小时，看了很多教程和演示。但我不太理解归并排序的合并部分。从理论上来说，我明白。但是尝试通过代码来实现它是我遇到困难的地方。并不是说我不理解它的任何合并部分。我明白为什么需要一些指针来跟踪索引以及while循环中条件语句背后的原因。但在那之后，我卡住了。我在合并方法中写了一条注释，说明我卡在哪里。如果有人能解释一下我需要在Java中编写什么代码以及背后的原因，那就太好了。
编辑：在合并方法中添加了两个新的while循环。我认为我要做的就是如何将排序后的分区复制到input数组中。我想在那之后应该可以正常工作... 希望如此。
编辑2：不要理会上面的，我刚刚看到它没有正确排序。希望有人可以修改我的代码并解释他们的过程。
public static void merge(int[] input, int start, int mid, int end) {
if (input[mid - 1] <= input[mid]) {
return;
}
int i = start;
int j = mid;
int tempIndex = 0;
int[] temp = new int[end - start];
// 如果i大于mid或j大于end，这意味着数组的一半已经排序
while (i < mid && j < end) {
temp[tempIndex++] = input[i] <= input[j] ? input[i++] : input[j++];
}
// 添加了下面两个循环
while (i < mid) {
temp[tempIndex++] = input[i++];
}
while (j < end) {
temp[tempIndex++] = input[j++];
}
// 现在你需要将排序后的temp数组复制回input数组
System.arraycopy(temp, 0, input, start, tempIndex);
}
英文:
Ive been trying to understand the merge portion of mergesort for a few hours now, and Ive looked at a bunch of tutorials and walkthroughs. And im not understanding the merge part of mergesort. Theoretically, I understand it. But trying to implement it through code is where Im having a hard time. It's not like I dont understand any of the merge portion of it. I get why you need a couple pointers to keep track of the indices and the reasoning behind the conditional statement in the while loop. But after that I get stuck. I wrote a comment in the merge method on where im stuck. If anyone could just explain to me what I need to code in Java and the reasoning behind it, it'd be great.
EDIT: Added two new while loops the the merge method. All thats left I think for me to do is how to copy the sorted partitions into the input array. I think after that it should be working fine... hopefully.
EDIT2: Nevermind the above, I just saw that its not sorting it correctly. Hopefully someone can just modify my code and explain there process
public static void merge(int[] input, int start, int mid, int end) {
if (input[mid - 1] <= input[mid]) {
return;
}
int i = start;
int j = mid;
int tempIndex = 0;
int[] temp = new int[end - start];
//If i is greater than mid or j is greater than end, that means that half of the array is sorted
while (i < mid && j < end) {
temp[tempIndex++] = input[i] <= input[j] ? input[i++] : input[j++];
}
//added the two loops below
while(i < mid){
temp[tempIndex++] = input[i++];
}
while(j < end){
temp[tempIndex++] = input[j++];
}
}
```
</details>
# 答案1
**得分**: 1
MergeSort是一种分治策略。
假设你有8个元素。
- 这8个元素被分成每个4个元素（左/右），并对每个元素调用mergeSort。现在我们先忽略merge，深入探讨一下。
- 这4个元素进一步分成每个2个元素，并在2个元素数组上调用mergeSort。
- 这2个元素再进一步分成每个1个元素，并在每个元素上调用mergeSort，此时它会立即返回而不执行任何操作。
- 所以最终我们到达了第一次调用merge。那么merge做什么呢？merge将两个已排序的列表合并在一起。当它们每个都只有1个元素时，只需要选择其中一个。所以让我们跳到4个元素并提供下面的示例：
在4个元素子列表调用merge时，它可能具有以下内容：
```plaintext
1 3 2 4
每个子数组（1, 3）和（2, 4）已经由前面的merge排序。所以现在我们需要在合并它们的同时对数组进行排序，像这样（我将使用一个单独的输出数组来演示应该发生的事情，但它也可以原地进行）：
for (int i = 0, j = 2, k = 0; k < 4; k++)
{
int idx;
if ((j >= 4) || (i < 2 && inputArray[i] < inputArray[j]))
{
idx = i++;
}
else // j < 4 && (i > 2 || inputArray[j] < inputArray[i])
{
idx = j++;
}
outputArray[k] = inputArray[idx];
}
正如你所看到的，最初i指向1，j指向2。因为1 < 2，所以选择i，输出1。因为选择了i，所以i被递增。现在，i指向3，j指向2。因为2 < 3，所以选择j...如此循环，直到我们用尽所有元素。
合并后，它将在具有2个4元素侧的较大数组上调用，重复上述过程。
以下是没有硬编码的通用代码：
public void Merge(int[] input, int start, int mid, int end)
{
if (input[mid - 1] <= input[mid])
{
}
else
{
int[] tmp = new int[end - start];
for (int i = start, j = mid, k = 0; k < tmp.Length; k++)
{
int idx;
if ((j >= end) || (i < mid && input[i] < input[j]))
{
idx = i++;
}
else // j < end && (i > mid || inputArray[j] < inputArray[i])
{
idx = j++;
}
tmp[k] = input[idx];
}
for (int i = start, j = 0; i < end; i++, j++)
{
input[i] = tmp[j];
}
}
}
英文:
MergeSort is a divide and conquor strategy.
Let's say you have 8 elements.
- The 8 elements get split into 4 elements each (left/right) and mergeSort is invoked on each of them. We'll ignore merge for now and delve deeper.
- The 4 elements are further split into 2 elements each, and mergeSort is invoked on the 2 element array.
- The 2 elements are further split into 1 elements each, and mergeSort is invoked on each of these at which time, it returns without doing anything.
- So we are finally at the first invocation of merge. So what does merge do? Merge joins 2 SORTED lists. When they are 1 element each, it's just a matter of picking one over the other. So lets skip forward to the 4 elements and provide an example below:
By the time the 4 element sub-list invokes merge, it may have the following:
1 3 2 4
Each sub-array (1, 3) and (2, 4) are already sorted by the previous merge. So we now need to sort the array while merging them like this (I will use a separate output array to demonstrate what should be happening but it can be done in place):
for (int i = 0, j = 2, k = 0; k < 4; k++)
{
int idx;
if ((j >= 4) || (i < 2 && inputArray[i] < inputArray[j]))
{
idx = i++;
}
else // j < 4 && (i > 2 || inputArray[j] < inputArray[i])
{
idx = j++;
}
outputArray[k] = inputArray[idx];
}
As you can see, initially we have i pointing to 1, j pointing to 2. Because 1 < 2, i is selected, and the 1 is output. Because i was selected, i gets incremented. Now, we have i pointing to 3 and j pointing to 2. Because 2 < 3, j gets selected... and so on until we run out of elements.
And after the merge, it will get called on the larger array with 2 4-element sides, repeating the above.
Below is the generalized code without hard coding
public void Merge(int[] input, int start, int mid, int end)
{
if (input[mid - 1] <= input[mid])
{
}
else
{
int[] tmp = new int[end - start];
for (int i = start, j = mid, k = 0; k < tmp.Length; k++)
{
int idx;
if ((j >= end) || (i < mid && input[i] < input[j]))
{
idx = i++;
}
else // j < end && (i > mid || inputArray[j] < inputArray[i])
{
idx = j++;
}
tmp[k] = input[idx];
}
for (int i = start, j = 0; i < end; i++, j++)
{
input[i] = tmp[j];
}
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论