归并排序
基本介绍图示代码
基本介绍
是利用归并的思想实现的排序方法, 该算法采用经典的分治(divide-and-conquer)策略 分治法将问题分(divide)成一些小的问题然后递归求解, 而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之。
图示
代码
public class MergetSort {
public static void main(String
[] args
) {
int[] arr
= {8,4,5,7,1,3,6,2};
int[] temp
= new int[arr
.length
];
mergeSort(arr
,0,arr
.length
-1,temp
);
System
.out
.println("排序:" + Arrays
.toString(arr
));
}
public static void mergeSort(int[] arr
,int left
,int right
,int[] temp
){
if (left
< right
){
int mid
= (left
+ right
) / 2;
mergeSort(arr
,left
,mid
,temp
);
mergeSort(arr
,mid
+1,right
,temp
);
merge(arr
,left
,mid
,right
,temp
);
}
}
public static void merge(int[] arr
,int left
,int mid
,int right
,int[] temp
){
int i
= left
;
int j
= mid
+ 1;
int t
= 0;
while (i
<= mid
&& j
<= right
){
if (arr
[i
] <= arr
[j
]){
temp
[t
] = arr
[i
];
t
+= 1;
i
+= 1;
}else {
temp
[t
] = arr
[j
];
t
+= 1;
j
+= 1;
}
}
while (i
<= mid
){
temp
[t
] = arr
[i
];
t
+= 1;
i
+= 1;
}
while (j
<= right
){
temp
[t
] = arr
[j
];
t
+= 1;
j
+= 1;
}
t
= 0;
int tempLeft
= left
;
while (tempLeft
<= right
){
arr
[tempLeft
] = temp
[t
];
t
+= 1;
tempLeft
+= 1;
}
}
}
【结果】
转载请注明原文地址:https://blackberry.8miu.com/read-1353.html