首页 / JAVA / 二路归并排序java实现
二路归并排序java实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二路归并排序java实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2793字，纯文字阅读大概需要4分钟。
内容图文
二路归并排序：
其核心思想时将问题一分为二，并递归调用一分为二方法，使问题分割到不能再分各的原子问题，然后再归并，从实现原子问题开始，层层向上归并，最终解决整体问题。即所谓“分而治之，万流归一”
二路归并排序的时间复杂度计算如下：
参考资料：算法导论------递归算法的时间复杂度求解：
二路归并java实现：
1
public
class
MergeSort {
2
3
public
static
void
main(String[] args) {
4
int [] array = {1,8,6,7,2,4,11,17,6,48,3};
5//int [] array ={9,8,7,6,5,4,3,2,1}; 6int [] temp = newint [array.length];
7 sort(array, temp, 0, array.length - 1);
8 System.out.println("排序后：");
9for (int i = 0; i < array.length; i++) {
10 System.out.print(array[i] + " ");
11 }
12 }
13/**14 * 总的sort循环。先将问题一分为二，再将问题解决后的两个子问题结果合并
15 * 要想清楚 子数组 边界的处理。
16 * 如子数组为 下标为(k,k + 1):则再分解为(K),(K+1)。
17 * 如子数组下标为(k,k+1,k+2)：则分解为(k,k+1)和(k+2)。再递归调用分解(k,k+1)
18 * @param array
19 * @param temp
20 * @param start
21 * @param end
22*/23publicstaticvoid sort (int [] array, int [] temp, int start, int end){
24if (start < end) {
25int mid = (start + end)/2;
26//解决左边子问题27 sort(array, temp, start, mid);
28//解决右边子问题29 sort(array, temp, mid + 1, end);
30//合并两个子问题31 merge(array,temp,start,end,mid);
32 }
33 }
34/**35 * 归并函数
36 * @param array 原始数组
37 * @param temp 辅助数组
38 * @param start 归并开始坐标
39 * @param end 归并结束坐标
40 * @param mid = (start + end)/2
41*/42publicstaticvoid merge(int[] array, int[] temp, int start, int end, int mid) {
43// TODO Auto-generated method stub
44//i：左子问题的操作下标； j：右子问题的操作下标45int i = start;
46int j = mid + 1;
47int k = start;
48while (i <= mid && j <= end){
49if (array[i] < array[j]) {
50 temp[k] = array[i];
51 k++;
52 i++;
53 }else {
54 temp[k] = array[j];
55 k++;
56 j++;
57 }
58 }
59//左子数组还有元素60while (i <= mid){
61 temp[k] = array[i];
62 k++;
63 i++;
64 }
65//右子数字还是元素66while (j <= end){
67 temp[k] = array[j];
68 k++;
69 j++;
70 }
7172//将辅助数组中排好序的元素复制到原数组
73//注意：辅助数组与原数组一一对应74for (int index = start; index <= end; index ++){
75 array[index] = temp[index];
76 System.out.println("temp[" + index +"]" + "....." + temp[index]);
77 }
78 System.out.println("===============");
79 }
80 }
通过控制台输出，我们可以看到排序的过程：
temp[0].....1 temp[1].....8 =============== temp[0].....1 temp[1].....6 temp[2].....8 =============== temp[3].....2 temp[4].....7 =============== temp[3].....2 temp[4].....4 temp[5].....7 =============== temp[0].....1 temp[1].....2 temp[2].....4 temp[3].....6 temp[4].....7 temp[5].....8 =============== temp[6].....11 temp[7].....17 =============== temp[6].....6 temp[7].....11 temp[8].....17 =============== temp[9].....3 temp[10].....48 =============== temp[6].....3 temp[7].....6 temp[8].....11 temp[9].....17 temp[10].....48 =============== temp[0].....1 temp[1].....2 temp[2].....3 temp[3].....4 temp[4].....6 temp[5].....6 temp[6].....7 temp[7].....8 temp[8].....11 temp[9].....17 temp[10].....48 =============== 排序后： 1 2 3 4 6 6 7 8 11 17 48
原文：https://www.cnblogs.com/wtting/p/8970455.html
内容总结
以上是互联网集市为您收集整理的二路归并排序java实现全部内容，希望文章能够帮你解决二路归并排序java实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。