forked from damaohongtu/JavaInterview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMergeSort.java
More file actions
62 lines (53 loc) · 1.38 KB
/
MergeSort.java
File metadata and controls
62 lines (53 loc) · 1.38 KB
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package ALiBaBa;
import org.junit.Test;
/**
* @Author MaoTian
* @Classname MergeSort
* @Description TODO
* @Date 上午11:40 2019/8/17
* @Version 1.0
* @Created by mao<[email protected]>
*/
public class MergeSort {
public void mergeSort(int[] nums,int left,int right){
if(left<right){
int mid=(left+right)>>1;
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
merge(nums,left,right,mid);
}
}
public void merge(int[] nums,int left,int right,int mid){
int leftPos=left;
int pos=left;
int rightPos=mid+1;
int len=right-left+1;
int[] tmp=new int[nums.length];
while(leftPos<=mid&&rightPos<=right){
if(nums[leftPos]>nums[rightPos]){
tmp[pos++]=nums[rightPos++];
}else{
tmp[pos++]=nums[leftPos++];
}
}
while(leftPos<=mid){
tmp[pos++]=nums[leftPos++];
}
while(rightPos<=right){
tmp[pos++]=nums[rightPos++];
}
int m=left;
int n=left;
for(int i=0;i<len;i++){
nums[m++]=tmp[n++];
}
}
@Test
public void check(){
int[] nums={2,4,2,5,73,2};
mergeSort(nums,0,nums.length-1);
for(int i=0;i<nums.length;i++){
System.out.println(nums[i]);
}
}
}