归并排序是利用分治的思想进行排序的策略。
可以理解为一个二叉树,通过深层递归拆成小的序列。
分成A,B两个小的序列,如果A序列的有序序列小于B有序序列的最小值,则A放在一个临时队列的最前面,以此类推。
我们为了便于理解可以将归并过程理解成Map/Reduce的过程。
Map
public static void main(String[] args) { int[] arr = {8,4,5,7,1,3,6,2};
sort(arr);
System.out.println(Arrays.toString(arr));
} private static void sort(int[] arr){ int[] temp = new int[arr.length]; map(arr,0,arr.length-1,temp);
} private static void map(int[] arr,int left,int right,int[] temp){ if(left < right){ int mid = (left + right) / 2; map(arr,left,mid,temp); map(arr,mid+1,right,temp);
reduce(arr,left,mid,right,temp);
}
}
Reduce
private static void reduce(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++];
}else {
temp[t++] = arr[j++];
}
} while (i<=mid){
temp[t++] = arr[i++];
} while (j<=right){
temp[t++] = arr[j++];
}
t = 0; while (left <= right){
arr[left++] = temp[t++];
}
}
输出结果
[1, 2, 3, 4, 5, 6, 7, 8]
© 著作权归作者所有