Java归并排序问题

来源:3-2 归并排序法的实现

fengback

2019-03-10

图片描述

老师您好,这里截取了你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. }

写回答

1回答

liuyubobobo

2019-03-11

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


函数声明中的参数是参数名;(蓝色)

具体函数调用,是传得具体参数内容;(红色)


比如,你可以设计一个函数,计算一个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


加油!:)

0
5
fengback
回复
liuyubobobo
非常感谢
2019-03-14
共5条回复

算法与数据结构(C++版) 面试/评级的算法复习技能包

课程专为:短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程