归并排序
2021-02-12 23:16
标签：空间 ++ imp 数组 code out color ati java 归并排序是建立在归并操作的基础上,同样也是利用了分治法来进行解答. 作为一种典型的分而治之思想的算法应用, 归并排序实现两种方法: 自上而下的递归 自下而上的迭代(所有递归都可以使用迭代重写) 首先申请空间, 设定两个指针,位于两个排序好的序列的初始位置, 比较两个序列的值然后放入最终序列, 直到某一个序列为空,将另一个追加在序列后 归并排序 标签：空间 ++ imp 数组 code out color ati java 原文地址：https://www.cnblogs.com/codingLiu/p/12729171.html思路分析:
代码:
import java.util.Arrays;
public class Merge {
public int[] sort(int[] arr){
if(arr.length ){
return arr;
}
int middle = arr.length / 2; //每次在中间将数组分割
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
return merge(sort(left), sort(right)); //合并分割的数组
}
public int[] merge(int[] left, int[] right){ //合并数组
int[] result = new int[left.length + right.length];
int i = 0;
while(left.length > 0 && right.length > 0){
if(left[0] ]){
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}else{
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
}
while(left.length > 0){
result[i++] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
}
while(right.length > 0){
result[i++] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
public static void main(String[] args) {
int[] arr = {7,4,2,8,5};
Merge merge = new Merge();
int[] arrays = merge.sort(arr);
for(int i = 0; i ){
System.out.println(arrays[i]);
}
}
}