Java归并排序问题

Question

老师您好，这里截取了你GitHub中的代码，我主要想问的问题有两个，一个是红色函数的参数是对应蓝色部分的参数的吗？，第二个是l,r指是什么？
l是指的是最左边的元素的，r是最右边的元素,下面这个又好像不对（这两个问题理解上有点乱。）

int mid = (l+r)/2;

//追问补充补充

 1. package SF;
 2. 
 3. import java.util.Arrays;
 4. 
 5. public class MergeSort {
 6. 
 7. 	private MergeSort(){
 8. 		
 9. 	}
 10. 	private static void merge(int [] arr,int l,int mid ,int r) {
 11. 		
 12. 		int [] aux =Arrays.copyOfRange(arr, l, r+1);
 13. 		
 14. 		int i=l;
 15. 		int j=mid+1;
 16. 		for (int k=l;k<=r;k++) {
 17. 			if(i>mid) {
 18. 				arr[k]=aux[j];
 19. 				j++;
 20. 			}
 21. 			else if(j>r) {
 22. 				arr[k]=aux[i];
 23. 				i++;
 24. 			}
 25. 			
 26. 			else if(aux[i-l]<aux[j-l]) {
 27. 			
 28. 				arr[k]=aux[i-1];
 29. 				i++;
 30. 			}
 31. 			else 
 32. 			{
 33. 				arr[k]=aux[j-l];
 34. 				j++;
 35. 			}
 36. 		}
 37. 	}
 38. 	
 39. 	private static void sort(int [] arr,int l, int r) {
 40. 		 System.out.println("l =" + l + ", r =" + r );
 41. 		if(l>=r)
 42. 			return ;
 43. 		int mid =(l+r)/2;
 44. 		sort(arr,l,mid);
 45. 		sort(arr,mid+1,r);
 46. 		merge(arr,l,r, mid);
 47. 		
 48. 	}
 49. 	
 50. 	
 51. 	public static void sort(int [] arr) {
 52. 		int n =arr.length;
 53. 		sort(arr, 0, n-1);
 54. 	}
 55. 	public static void main(String[] args) {
 56. 		int [] arr= {9,8,7,6,5,4,3,2,1};
 57. 		InsertSort.sort(arr);
 58. 		for (int i = 0; i < arr.length; i++) {
 59. 			System.out.print(arr[i]);;
 60. 			System.out.print(" ");
 61. 		}
 62. 	}
 63. }

Answer 1

liuyubobobo 2019-03-11 05:23:03

我不确定我是不是完全理解了你的问题。

函数声明中的参数是参数名；（蓝色）

具体函数调用，是传得具体参数内容；（红色）

比如，你可以设计一个函数，计算一个arr数组的和：int sum(int[] arr)，

但具体调用的时候，你传入的数组可能叫scores: sum(scores)；

也可能叫nums: score(nums);

也可能叫salaries: score(salaries)；

对于sort这个函数定义，

void sort(Comparable[] arr, int l, int r){
    ......
}

传的三个参数名叫做arr, l和r。

在具体逻辑中：

int mid = (l + r) / 2，使用传来的l和r，计算出了mid；

之后sort(arr, l, mid)再次调用了sort，这一次调用sort，相当于调用sort，

其中arr参数传arr；l参数传l，r参数传mid

再之后，sort(arr, mid + 1, r)再次调用了sort，

这一次调用sort，相当于调用sort，

其中arr参数传arr；l参数传mid + 1，r参数传r

最初的调用 sort(arr, 0, n - 1)，相当于调用sort，

其中arr参数传arr；l参数传0，r参数传n - 1

最后，是的，整个sort(Comparable[] arr, int l, int r)函数的语义是，对arr[l...r]范围内的元素进行（归并）排序。

如果对整个递归过程不够理解，可以尝试使用这个问答的方式进行调试跟踪：https://coding.imooc.com/learn/questiondetail/102550.html

加油！：）

• 提问者 fengback #1

  老师，我尝试在40行增加了 System.out.println("l =" + l + ", r =" + r );去追踪l和r的值，但是40行的代码没有输出，我在问题中补充的代码，你可以帮我看一下吗？

• liuyubobobo 回复 提问者 fengback #2

  你调用的是InsertSort.sort，不是MergeSort.sort。单步跟踪一下，看看程序走到了哪里？：）

• 提问者 fengback 回复 liuyubobobo #3

  使用元素追踪花了很长时间去理解他们的执行过程，最后想确认一下：
       从开始运行开始，是不是sort(arr,l,mid);运行多少次，下面两个也运行多少次。
  	sort(arr,mid+1,r);
  	merge(arr,l,r, mid);

点开查看后面2条评论