※归并排序(merge sort)
/**
- 归并排序:通常以递归的方式来实现,它反复将所处理的数组分成两半,并分别对这两半进行排序, 最后再把经过排序的数组归并在一起。
*/
归并排序的伪代码实现:
将数组分为两半
对左半部分排序
对右半部分排序
合并左右两部分
合并算法的伪代码描述:
i1 = 0; //左半部分的索引
i2 = 0;//右半部分的索引
for(数组中元素的个数){
if(左半部分下标为i1的元素值<= 右半部分下标为i2的元素值){
将左半部分的当前值保存到新数组
i1++;
}else{
将右半部分的当前值保存到新数组
i2++;
}
-----------------------------------------------------------------------------------------------------------
//代码实现:
public static void mergeSort(int[] num) {
// 将数组分为两半
int[] left = Arrays.copyOfRange(num, 0, num.length / 2);// 不包括终点元素
int[] right = Arrays.copyOfRange(num, num.length / 2, num.length);
if (left.length > 1) {
mergeSort(left);
mergeSort(right);
merge(num, left, right);
}
}
public static void merge(int[] result, int[] left, int[] right) {
int i1 = 0; // index of left array
int i2 = 0; // index of right array
for (int i = 0; i < result.length; i++) {
if (i2 >= right.length || (i1 < left.length && left[i1] <= right[i2])) {
result[i] = left[i1]; // take from left
i1++;
} else {
result[i] = right[i2]; // take from right
i2++;
}
}
}
////end
最新文章
- Android 解析聊天表情的笔记
- FFmpeg-20160428-snapshot-bin
- 关于 Redis 访问安全性的问题
- .NET对象与Windows句柄(三):句柄泄露实例分析
- Prince2的七大原则(5)
- Logs
- 来自平时工作中的css知识的积累---持续补充中
- (转)SqlServer2008 数据库同步的两种方式 (发布、订阅)
- Finding Nemo(bfs)
- DelphiXE7如何调用Java Class,JAR等文件?
- nexus 7 2013 驱动安装及root
- JVM学习笔记一:Java运行时数据区域
- xml 和数组的相互转化
- 使用TCP模拟登陆
- 开发者中心没有勾选 ipad却需要传宣传图片的解决方法
- Confluence 6 数据库整合的方法 1:基本流程
- 处理器 趣事 CPU/GPU/TPU/DPU/BPU
- java爬取网站信息和url实例
- nuxtjs中使用路由守卫
- Python连接mysql基本操作
热门文章
- C++标准库 vector排序
- Docker 的基本使用
- JAVA基础数组
- xmpp消息回执(6)
- [angular1.6]Error: ";transition superseded"; ui-router 在angular1.6 报错误问题解决
- <;MyBatis>;入门四 传入的参数处理
- python list排序(正倒)以及获取重复数据
- LINUX应用开发工程师职位(含答案)
- 腾讯云,体验域名注册解析与SSL证书
- FJoi2017 1月21日模拟赛 comparison(平衡树+thita重构)