java实现归并排序算法
2024-10-21 02:58:54
归并排序算法思想:
分而治之(divide - conquer);每个递归过程涉及三个步骤
第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
第三, 合并: 合并两个排好序的子序列,生成排序结果.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
public static void mergeSort( int [] a, int [] tmp, int left, int right) { if (left < right) { int mid = left + (right - left) / 2 ; mergeSort(a, tmp, left, mid); // 左排序 mergeSort(a, tmp, mid + 1 , right); // 右排序 merge(a, tmp, left, mid + 1 , right); // 左右合并 } } public static void merge( int [] a, int [] tmp, int left, int rightPos, int right) { int leftEnd = rightPos - 1 ; int tmpPos = left; int num = right - left + 1 ; while (left <= leftEnd && rightPos <= right) { if (a[left] < a[rightPos]) { tmp[tmpPos++] = a[left++]; } else { tmp[tmpPos++] = a[rightPos++]; } } while (left <= leftEnd) { tmp[tmpPos++] = a[left++]; } while (rightPos <= right) { tmp[tmpPos++] = a[rightPos++]; } for ( int i = 0 ; i < num; i++, right--) { a[right] = tmp[right]; } } |
归并算法示意图:
最新文章
- Java:基于LinkedList实现栈和队列
- js命名空间笔记
- 安装python-devel 在升级到python2.7之后
- MemCache超详细解读 图
- 你需要知道的三个CSS技巧
- 全面理解BFC
- android之APN
- 【BZOJ】1925: [Sdoi2010]地精部落 DP+滚动数组
- Qt的事件模型(5种使用办法,通常重新实现event handler即可。只有定义控件才需要管理信号的发射)
- Linux系统安装rar压缩软件
- truetype技术和矢量字库的技术原理及实现(转)
- 微信开发(2)---微信小程序开发实战part1
- SWIG 的应用(一)
- 【C++ Primer 第11章】2. 关联容器操作
- Zabbix故障总结(持续更新)
- C语言 &#183; 选最大数
- 执行js,通过js显示隐藏的输入框,或者给input赋值
- centos7 --ngnix 常用命令:
- bzoj 1218: [HNOI2003]激光炸弹
- 火速提升Android仿真器的运行速度 ——仿真器Genymotion
热门文章
- NoSQL 数据库应用
- CentOS 6.7下配置 yum 安装 Nginx
- Vue组件之props,$emit与$on以及slot分发
- Java基础知识(二)
- Java工具类-加密算法
- Flask实战第60天:帖子分页技术实现
- python 去掉换行符或者改为其他方式结尾的方法(end=&#39;&#39;)
- 【线段树】I Hate It
- 【线段树】洛谷 P3372 【模板】线段树 1
- 【计算几何】【分类讨论】Gym - 101173C - Convex Contour