归并排序 (分而治之算法) java代码实现（java完整代码）java递归实现（分而治之）MergeSort（分治法）

归并排序是分而治之算法策略的典型代表之一

分而治之算法的思路：

分而治之三步骤：分解原问题，解决子问题，合并问题解
1.分解原问题：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
2.解决子问：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。
3.合并：将各子问题的解合并为原问题的解。

归并排序：

以数组为例，假设数组长度为n
1.首先把其拆分n组每组一个，
2.然后每相连的两组进行比较，并排序；
（第一遍排序之变成了n/2组，每组为2个，当然若n为奇数，则最后一组只有一个元素；）
3.继续执行2，直到排序后只有一组。
它的时间复杂度是O(nlogn).

java完整代码（递归实现）：

public void toMergeSort(int []arr,int left,int right) {
	//递归出口
	if(left >= right) {										
		return;
	}
	int mid = (int)((left+right)/2);
	toMergeSort(arr,left,mid);     //先左边递归
	toMergeSort(arr,mid+1,right);     //再右边递归
	toSort(arr,left,mid,right);						//调用排序函数
}
public void toSort(int []arr,int left,int mid, int right) {
	int i = left ,j = mid+1 ,tempIndex = left;				//i指向左半边，j指向右半边
	int []tempArr = arr.clone();
	while(i <= mid && j <= right) {
		if(tempArr[i]>tempArr[j]) {
			arr[tempIndex] = tempArr[j];
			j++;
			tempIndex++;
		}
		else {
			arr[tempIndex] = tempArr[i];
			i++;
			tempIndex++;
		}
	}
	while(i<=mid) {				//左边还没有完，右边已完
		arr[tempIndex] = tempArr[i];
		i++;
		tempIndex++;
	}
	while(j<=right){
		arr[tempIndex] = tempArr[j];  //右边还没有完，左边已完
		j++;
		tempIndex++;
	}
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
 

测试算法，运行结果:

文章来源: blog.csdn.net，作者：Mr.Yushiwen，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/MrYushiwen/article/details/107179355