map/reduce的先祖归并排序
归并排序是利用分治的思想进行排序的策略。
- 分：通过递归将一个大的数据集进行递归分割，直到只有两个元素进行比较。
- 治：将分的阶段的分割单元进行合并。
分
可以理解为一个二叉树，通过深层递归拆成小的序列。
治
分成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]© 著作权归作者所有
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-03-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录