这是填补空白的问题。我无法删除和重写内容。我要填写的是“ // TO DO ....之后”之前的行,“ /是我的答案,上面的行正确吗?
我的问题是1、2、3a-d和4是正确的,如果是,为什么我会得到堆栈溢出错误。
截至目前,这将返回堆栈溢出错误。我的背景是Java入门课程的一半,现在是我学习数据结构和算法的全部时间。
分配:合并排序
开发合并排序方法,它将对整数值的数组进行排序
您需要在四个地方进行修改正确执行排序。这些地方均标有文档→//要做(#1),(#2),(#3a-d)和(#4)。
[如果您运行该应用程序并输入'8',输出应与列出的输出相同。
样本输出:
下面的示例输出显示了MergeSort算法以及调试输出的日志显示算法的进度:
合并排序测试
输入整数元素的数量:
8
输入8个整数元素
元素1:6
元素2:5
元素3:3
元素4:1
元素5:7
元素6:8
元素7:2
元素8:4
呼叫分类:低[0],高[4]
呼叫分类:低[0],高[2]
呼叫分类:低[0],高[1]
呼叫分类:低[1],高[2]
合并2个元素
当前数组:5 6
呼叫分类:低[2],高[4]
呼叫分类:低[2],高[3]
呼叫分类:低[3],高[4]
合并2个元素
当前数组:1 3
合并4个元素
当前数组:1 3 5 6
呼叫分类:低[4],高[8]
呼叫分类:低[4],高[6]
呼叫分类:低[4],高[5]
呼叫分类:低[5],高[6]
合并2个元素
当前数组:7 8
呼叫分类:低[6],高[8]
呼叫分类:低[6],高[7]
呼叫分类:低[7],高[8]
合并2个元素
当前数组:2 4
合并4个元素
当前数组:2 4 7 8
合并8个元素
当前数组:1 2 3 4 5 6 7 8
排序后的元素
1 2 3 4 5 6 7 8
package mergesort;
import java.util.Scanner;
/* Class MergeSort */
public class MergeSort
{
/* Merge Sort function */
public static void sort( int[] array, int low, int high )
{
int diff;
int midpoint;
/* Calculate Difference between low and high */
diff = high-low;
/* Recursion is called until diff is less than or equal to 1 */
/* Return if less than or equal to 1 */
if ( diff <= 1 )
{
return;
}
/* Calculate the midpoint between low and diff */
midpoint = low + diff/2;
// We will call sort recursively here, once for the lower half of the
// provided array and once for the upper half of the array
System.out.printf( "Calling sort: low [%d], high [%d]\n", low, midpoint );
//要做(#1):对数组的下半部分进行排序
sort(array, low, midpoint);
我的答案是上面的一行,对吗?
System.out.printf( "Calling sort: low [%d], high [%d]\n", midpoint, high );
//要做(#2):对数组的上半部分进行排序
sort(array, high - midpoint, high);
我的答案是上面的一行,对吗?
// Merge Two Sorted Subarrays
// Create temporary array and temporary variables
int[] temp = new int[diff];
int i = low, j = midpoint;
System.out.printf( "Merging %d Elements\n", diff );
for ( int k = 0; k < diff; k++ )
{
// Fill in temporary array as necessary
if ( i == midpoint )
{
要做(#3a)当涉及到如何将这两件事合并以及为什么需要4个条件时,我完全迷失了。我本来希望从头开始编写代码。
temp[k] = array[j++];
我的答案是上面的行,对吗?}否则(j == high)
{
//要做(#3b)
temp[k] = array[i++];
我的答案是上面的行,对吗?
}
else if ( array[j] < array[i] )
{
//要做(#3c)
temp[k] = array[j++];
我的答案是上面的行,对吗?
}
else
{
//要做(#3d)
temp[k] = array[i++];
我的答案是上面的行,对吗?
}
}
System.out.print( "Current Array: " );
for ( int k=0; k<diff; k++ )
{
//要做(#4):用临时数组元素填充数组
array[k] = temp[k];
我的答案是上面的行,对吗?
System.out.printf( "%d ", array[low+k] );
}
System.out.println();
}
/* Main method */
public static void main(String[] args)
{
Scanner keyboard = new Scanner( System.in );
int elements, lp;
int intArray[] = null;
System.out.println( "Merge Sort Test\n" );
/* Accept number of elements */
System.out.println( "Enter Number of Integer Elements: " );
elements = keyboard.nextInt();
/* Create array of n elements */
intArray = new int[ elements ];
/* Read Elements from the keyboard */
System.out.println( "\nEnter " + elements + " integer elements" );
for ( lp=0; lp<elements; lp++ )
{
System.out.print( "Element " + ( lp+1 ) + ": " );
intArray[lp] = keyboard.nextInt();
}
/* Call method sort */
sort( intArray, 0, elements );
/* Print sorted Array */
System.out.println( "\nElements After Sorting" );
for ( lp=0; lp<elements; lp++ )
{
System.out.print( intArray[lp] + " " );
}
System.out.println();
}
}
sort(array,low,midpoint);
sort(array,midpoint,high);
您不能做任何假设。如果您查看主要方法,则不包括“ high”。高是数组的长度,而不是最后一个元素的索引。
3a。
temp[k] = array[j++];
这意味着:
temp[k] = array[j];
j++;
为什么?这是为了防止您到达数组一半的末尾而又到达另一端的末尾。就是说,如果您已完成将第一个排序后的一半复制到temp数组中,然后从下一个一半中取出并增加该数组的索引。
3b。
temp[k] = array[i++];
为什么?见上文。
3c。
temp[k] = array[j++];
意思是,将较小的int放入temp数组,并将索引增加一半。3d。唯一剩余的条件与上述相反。在这种情况下,请执行相反的操作:
temp[k] = array[i++];
将临时数组复制到原始数组:
array [k] = temp [k];