在合并排序java中跟踪递归 [英] Tracing recursion in merge sort java

问题描述

 public class Mergesort2 
 {
 
 public static void main（String [] args）
 {
 int array [] = { 8,3,5,2,7,1,4,6}; 
 sort（array）; 
 
} 
 static void sort（int array []）
 {
 int mid = array.length / 2; 
 
 if（array.length == 1）
 return; 
 
 int part1 [] = new int [mid]; 
 int part2 [] = new int [array.length-mid]; （b i = 0; i< array.length; i ++）
 $ 
 if（i< mid）
 {
 part1 [i] = array [i]; 
 
 
} 
其他
 {
 part2 [i-mid] = array [i]; 
 
} 
} 
 
 sort（part1）; 
 sort（part2）; 
 merge（part1，part2，array）; 
 printarray（array）; 
 
 
} 
 static void merge（int [] part1，int [] part2，int [] array）
 {
 int index1 = 0; 
 int index2 = 0; 
 
 for（int k = 0; k< array.length; k ++）
 {
 if（index1 == part1.length）
 {
阵列[K] = 2部分[索引2]; 
 index2 ++; 
 
} 
 else if（index2 == part2.length）
 {
 array [k] = part1 [index1]; 
 index1 ++; 
 
} 
 else if（part1 [index1]< = part2 [index2]）
 {
 array [k] = part1 [index1]; 
 index1 ++; 
 
} 
 else 
 {
 array [k] = part2 [index2]; 
 index2 ++; 
 
} 
} 
} 
 static void printarray（int [] array）
 {
 
 for（int i = 0; i< array.length; i ++）
 {
 System.out.print（array [i] +，）; 
} 
 System.out.println（）; 
 System.out.println（========================）; 
} 
 
} 
 // OUTPUT 
 // 3,8，
 // ============= =========== 
 // 2,5，
 // ======================= = 
 // 2,3,5,8，
 // ======================== 
 / / 1,7，
 // ======================== 
 // 4,6，
 / / ======================== 
 // 1,4,6,7，
 // ===== =================== 
 // 1,2,3,4,5,6,7,8，
 // === ===================== 

我的追踪第一次追踪是正确的它给了我一个3,8的输出，但在第二我不知道该怎么做，因为你可以在merge（int [] part1，int [] part2，int [] array）方法中看到方法没有调用sort（）方法我不知道程序如何回到sort（part1）方法。在执行printarray（数组）方法后跟踪时，伙计们可以帮助我

解决方案

我会创建一个静态类变量ArrayList或Vector of strings。

然后printarray（数组）里面排序和合并，但前缀为例如

sort0：array

sort1：array

merge0 ：array

然后在主打印出整个字符串列表。

你也可以在main（）中的sort（）之前放一个printarray（数组）来显示原始数组。

public class Mergesort2 
{

	public static void main(String[] args) 
	{
		int array[]={8,3,5,2,7,1,4,6};
		sort(array);
	
	}
	static void sort(int array[])
	{
		int mid=array.length / 2;
		
		if(array.length==1)
			return;
		
		int part1[]=new int[mid];
		int part2[]=new int[array.length-mid];
		
		
		for(int i=0; i<array.length; i++)
		{
			if(i<mid)
			{
				part1[i]=array[i];
				
				
			}
			else
			{
				part2[i-mid]=array[i];
				
			}
		}
		
	   sort(part1);
       sort(part2);
	   merge(part1,part2,array);
	   printarray(array);
	
		
	}
	static void merge(int []part1,int []part2,int []array)
	{
		int index1=0;
		int index2=0;
		
		for(int k=0; k<array.length; k++)
		{
			if(index1==part1.length)
			{
				array[k]=part2[index2];
				index2++;
				
			}
			else if(index2==part2.length)
			{
				array[k]=part1[index1];
				index1++;
				
			}
			else if(part1[index1]<=part2[index2])
			{
				array[k]=part1[index1];
				index1++;
				
			}
			else
			{
				array[k]=part2[index2];
				index2++;
				
			}
		}
	}
	static void printarray(int []array)
	{
		
		for(int i=0; i<array.length; i++)
		{
		System.out.print(array[i]+",");
		}
		System.out.println();
		System.out.println("========================");
	}

}
//OUTPUT
//3,8,
//========================
//2,5,
//========================
//2,3,5,8,
//========================
//1,7,
//========================
//4,6,
//========================
//1,4,6,7,
//========================
//1,2,3,4,5,6,7,8,
//========================

my tracing first tracing is correct it gives me an output of 3,8 but in second i dont know what to do because as you can see in merge(int []part1,int []part2,int []array) method theres no calling of sort()method i don't know how the program back to the sort(part1)method. guys can you help me when tracing after the printarray(array)method is executed

解决方案

I would make a static class variable ArrayList or Vector of strings.
Then printarray(array) inside both sort and merge but with prefix for example
sort0: array
sort1: array
merge0: array
then in main print out whole list of strings.
You could also put one printarray(array) before sort() in main() to show original array.

这篇关于在合并排序java中跟踪递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！