java 算法之归并排序详解及实现代码
作者:lqh 时间:2021-12-27 01:52:11
java 算法之归并排序详解
一、思想
归并排序:将一个数组排序,可以先(递归地)将它分成两半部份分别排序,然后将结果归并起来;
二、概念
归并:将两个有序的数组归并成一个更大的有序数组;
三、特点
优点:能够保证将任意长度为N的数组排序所需要的时间和NlogN成正比;
缺点:需要额外的空间和N成正比;
四、实现方法
将两个不同的有序数组归并到第三个数组中;
先将前半部分排序,在将后半部分排序,然后在数组中移动元素而不需要使用额外的空间;
五、代码
/**
* 归并排序
*
* @author pengcx
*
*/
public class Merge extends Sort {
/** 归并所需的辅助数组 */
private static Comparable[] aux;
public static void main(String[] args) {
String[] a = { "d", "a", "w", "b", "q" };
Merge.sort(a);
show(a);
}
public static void sort(Comparable[] a) {
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
/**
* 排序数组的a[lo]至a[hi]元素
*
* @param a
* 数组a
* @param lo
* 最小元素位置lo
* @param hi
* 最大元素位置hi
*/
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) {
return;
}
// 计算数组中间位置
int mid = lo + (hi - lo) / 2;
// 排序数组a左边的元素
sort(a, lo, mid);
// 排序数组a右边的元素
sort(a, mid + 1, hi);
// 合并数组a左边和右边的元素
merge(a, lo, mid, hi);
}
/**
* 将数组a的a[lo]至a[mid]的元素与a[mid]至a[hi]的元素合并
*
* @param a
* 合并的数组a
* @param lo
* 最小数组元素lo
* @param mid
* 中间元素位置mid
* @param hi
* 最大元素位置hi
*/
public static void merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
for (int k = lo; k <= hi; k++) {
// 如果左边的元素用尽,取右边的元素
if (i > mid) {
a[k] = aux[j++];
}
// 如果右边的元素用尽,取左边的元素
else if (j > hi) {
a[k] = aux[i++];
}
// 如果右半边的当前元素小于左半边的当前元素,取右半边元素
else if (less(aux[j], aux[i])) {
a[k] = aux[j++];
}
// 如果右半边的当前元素大于等于左半边的当前元素,取左半边元素
else {
a[k] = aux[i++];
}
}
}
}
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
来源:http://blog.csdn.net/p106786860/article/details/17750515
标签:java,归并排序
0
投稿
猜你喜欢
浅谈JVM中的JOL
2022-10-06 15:44:49
Java静态代理和动态代理总结
2022-01-02 18:49:21
c# 可选参数、命名参数
2022-08-06 05:38:41
浅谈java 面对对象(抽象 继承 接口 多态)
2022-04-01 07:23:50
java对象拷贝详解及实例
2023-01-20 08:27:00
Java7和Java8中的ConcurrentHashMap原理解析
2022-06-09 22:06:28
分享两种实现Winform程序的多语言支持的多种解决方案
2023-10-17 21:24:17
SpringBoot整合Shiro实现登录认证的方法
2022-03-23 01:12:19
JavaWeb详细讲述Cookie和Session的概念
2022-03-23 08:39:44
基于Flutter实现图片选择和图片上传
2023-07-06 04:28:50
Spring boot随机端口你都不会还怎么动态扩容
2021-09-29 10:10:14
Java中this关键字的用法详解
2023-10-04 05:05:53
java多线程模拟抢红包功能
2023-07-25 01:09:58
java仿QQ微信聊天室功能的实现
2022-05-14 17:44:28
Java 求解如何把二叉搜索树转换为累加树
2021-11-19 14:09:54
Java 反射调用静态方法的简单实例
2021-10-09 06:47:58
centos7下安装java及环境变量配置技巧
2022-06-05 08:06:13
Java面试题解析之判断以及防止SQL注入
2023-05-26 18:08:59
Java编程swing组件JLabel详解以及使用示例
2023-12-15 22:28:50
Java 发送http请求(get、post)的示例
2022-02-15 12:20:56