- 浏览: 336227 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
yueshang520:
太厉害了
Spring读取XML配置源码解析 -
levin_china:
jianyan163qq 写道好文章!我现在遇到一个调用的问题 ...
Java中Runtime.exec的一些事 -
wenlongsust:
exec可能存在注入漏洞,如何控制安全问题啊?
Java中Runtime.exec的一些事 -
RainWu:
...
设计模式感触之代理模式应用 -
ch_dj:
面向对象涉及原则:1.开闭原则2.少用继承,多用聚合3.针对 ...
设计模式感触之代理模式应用
java类库中Arrays的排序算法探析(Object与泛型类型)
- 博客分类:
- Java基础库
在Arrays中关于基本类型如int,long,float等都在java类库中Arrays的排序算法探析(基础类型)做了一定分析,本篇主要关于Object类型的sort,以及之后的泛型sort。
直接查看源码中的方法定义及实现:
public static void sort(Object[] a) { Object[] aux = (Object[])a.clone(); mergeSort(aux, a, 0, a.length, 0); } public static void sort(Object[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex);//验证参数是否合法 Object[] aux = copyOfRange(a, fromIndex, toIndex);//创建待排序数组临时存储区 mergeSort(aux, a, fromIndex, toIndex, -fromIndex); }
由上可见,两个重载方法的具体实现指向了同一个具体实现,应该是个私有方法:
/** * Src is the source array that starts at index 0 * Dest is the (possibly larger) array destination with a possible offset * low is the index in dest to start sorting * high is the end index in dest to end sorting * off is the offset to generate corresponding low, high in src */ private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off) { int length = high - low; // Insertion sort on smallest arrays if (length < INSERTIONSORT_THRESHOLD) { for (int i=low; i<high; i++) for (int j=i; j>low && ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--) swap(dest, j, j-1); return; } // Recursively sort halves of dest into src int destLow = low; int destHigh = high; low += off; high += off; int mid = (low + high) >>> 1; mergeSort(dest, src, low, mid, -off); mergeSort(dest, src, mid, high, -off); // If list is already sorted, just copy from src to dest. This is an // optimization that results in faster sorts for nearly ordered lists. if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) { System.arraycopy(src, low, dest, destLow, length); return; } // Merge sorted halves (now in src) into dest for(int i = destLow, p = low, q = mid; i < destHigh; i++) { if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0) dest[i] = src[p++]; else dest[i] = src[q++]; } }
当然,如果能直接看代码一眼就完全明白的话,那到此就可以为止了。
先理一下流程:
1 如果待排序的数组大小小于设置的插入排序阈值,则直接采用插入排序解决;
2 如果不满足1,则将其一分为二,递归处理;这样经过多次递归,其实最终还是分段采用插入排序将其拆分为了N个有序的段;
3 到了这里,前面是多个分别有序的段,这里需要将其逐一连接起来,使其更大长度上有序,这一部分展示的就是:如果前一段的最后一个值(也就是前一段的最大值)小于紧挨着的后一个段的第一个值(也就是这一段的最小值),则这两段总体是有序的;
4 如果没有3那种理想状态,则需要我们来处理,这里处理的思想就是:前后两段逐一开始比较,小的先放,依次放第二小的,直到两段都为空;
5 3或4逐级返回,最终构成一个整体的有序数组。
再说泛型的排序:
public static <T> void sort(T[] a, Comparator<? super T> c) { T[] aux = (T[])a.clone(); if (c==null) mergeSort(aux, a, 0, a.length, 0); else mergeSort(aux, a, 0, a.length, 0, c); } public static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) { rangeCheck(a.length, fromIndex, toIndex); T[] aux = (T[])copyOfRange(a, fromIndex, toIndex); if (c==null) mergeSort(aux, a, fromIndex, toIndex, -fromIndex); else mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c); }
可以看出来,泛型排序的处理过程几乎和对象数组的一模一样,值得注意的是,如果Comparator为null,则使用默认的Comparable接口的自然序。下面看具体调用的实现方法:
private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off, Comparator c) { int length = high - low; // Insertion sort on smallest arrays if (length < INSERTIONSORT_THRESHOLD) { for (int i=low; i<high; i++) for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--) swap(dest, j, j-1); return; } // Recursively sort halves of dest into src int destLow = low; int destHigh = high; low += off; high += off; int mid = (low + high) >>> 1; mergeSort(dest, src, low, mid, -off, c); mergeSort(dest, src, mid, high, -off, c); // If list is already sorted, just copy from src to dest. This is an // optimization that results in faster sorts for nearly ordered lists. if (c.compare(src[mid-1], src[mid]) <= 0) { System.arraycopy(src, low, dest, destLow, length); return; } // Merge sorted halves (now in src) into dest for(int i = destLow, p = low, q = mid; i < destHigh; i++) { if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0) dest[i] = src[p++]; else dest[i] = src[q++]; } }
仔细看来,无Comparator的实现和对象数组的事项没有任何差别,具有Comparator的也仅仅在比较使采取的是compare方法来决定数组顺序。
这个实现值得学习的有几点:
1 小规模的比较采取的是插入排序,这就避免了递归到一个数组只有一个元素那种情况,在小规模情况下,插入排序实现简单,效率也还可以(类库中设置的是7);
2 在相邻两段的连接时,如果发现两个段的连接处构成正确顺序,则直接返回,减少了需要逐个比较元素重新插入一遍带来的性能影响;
3 无符号位运算取中间值,代替/;
4 对外接口与对内实现的独立,对外可能有多个接口,但内部实现其实是一样的,这样非常方便于后续调整和性能优化;
总体感觉就是这些方法的实现极大的优化了性能,并且给后续调整留下了空间,便于维护。
唯一感到有点不足的就是:
就是临时变量实在是有点多,刚开始难以理解~
发表评论
-
警告:编码 EUC_CN 的不可映射字符
2013-04-01 15:49 3574使用javac编译时显示: 警告:编码 EUC_CN 的不 ... -
异常处理几则(javac异常与get请求中文乱码)
2013-03-31 18:36 11651 仅当显式请求注释处理时才接受类名称错误 好久没用ja ... -
Java内存管理知识(基础篇)
2013-01-20 16:02 1486第一部分 基础知识 1.1 内存模型 1.2 垃圾回 ... -
Java虚拟机之垃圾收集
2013-01-12 15:07 2933垃圾收集虽说不是JVM ... -
maven坐标查询
2012-12-10 23:11 3284使用maven时,一个经常用到的操作就是去 中央仓库查询相关库 ... -
Maven报错“未结束的字符串字面值” “需要为 class、interface 或 enum”等
2012-12-10 17:26 5891eclipse里面编译完全正常,mvn clean in ... -
String, StringBuilder和StringBuffer性能比较的正确写法
2012-11-22 22:54 2114关于String连接性能的分 ... -
No embedded stylesheet instruction for file:奇怪的错误
2012-11-17 08:14 1331908:09:43,395 INFO [main] Ma ... -
Java中Runtime.exec的一些事
2012-09-09 16:32 500570 预备知识 1 不正确的 ... -
代码重构(一)
2012-08-26 10:55 0真实代码 /** 支付状态校验 * ... -
JAVA正则表达式
2012-08-22 23:04 0JAVA中的正则知识 1.2正则表达式入门 一 ... -
JAVA字节码学习一(初识)
2012-08-20 21:42 0public class MyClass { pub ... -
java类库中Arrays的排序算法探析(基础类型)
2012-03-06 23:32 2575java.util.Arrays中有非常方便的array转换为 ... -
Java中List与Array的转换
2012-02-28 18:42 1530在编码中,经常会用到两种存储结构之间的转换,而对 ... -
Java中的桥方法
2012-01-10 00:27 6108Java中的桥方法是合成方法(synthetic met ... -
设计模式感触之代理模式-远程代理
2012-01-08 16:33 36611 远程代理的意义 远程代理为一个位于不同的地址空间的 ... -
设计模式感触之代理模式应用
2012-01-03 17:30 4341设计模式感触之代理模式应用 如果说看完设计模式之 ... -
Java泛型学习
2010-11-06 22:19 1082泛型程序设计(Generic Programming)可以使编 ... -
正在学JAVA的请看看:JAVA学习之路
2010-11-05 15:32 1157JAVA是一种平 ... -
JAVA学习路线图
2010-11-05 15:29 1449最近论坛上看到好几个朋友都在问,如何学习 Java的问 ...
相关推荐
这个资源是关于Java中排序算法实现的简单示例。排序算法是计算机科学中的基础概念,用于按升序或降序排列数据集。这里提供了两种常见的排序算法实现:冒泡排序和选择排序。 冒泡排序(Bubble Sort) 是一种基本的...
031112_【第11章:Java常用类库】_Arrays笔记
•转换 javabeans, maps, collections, java arrays 和 XML 成为 json 格式数据 •转换 json 格式数据成为 javabeans 对象 Json-lib 需要的 jar 包 •commons-beanutils-1.8.3.jar •commons-collections-3.2.1.jar...
## 九种内部排序算法的Java实现及其性能测试 ### 9种内部排序算法性能比较 第九种为java.util.Arrays.sort(改进的快速排序方法) 1. 100000的随机数据集 ![](http://7xlkoc.com1.z0.glb.clouddn.com/sort1.jpg) ...
在Java中对于字符串数组的排序,我们可以使用Arrays.sort(String[])方法很便捷的进行排序。例如: String[] arrays = new String[] { gyu, sdf, zf, 大同, 收到, 地方, 三等分, 的人, 反对高铁, 泛代数, 上的投入...
Java期末复习-常用类库 StringBuffer、Runtime、国际化程序、System、日期操作类、Math、Random、NumberFormat、BigInteger、BigDecimal、对象克隆技术、Arrays、Comparable、正则表达式、定时调度
算法(冒泡,选择,插入,数组排序) package Teacher; import java.io.*; import java.util.Scanner; public class Tset { public static void main(String args[]) throws IOException { // 需要排序的数组,...
String[] strs2=new String[]{"希尔排序","直接插入排序","折半插入排序","冒泡排序"}; new SortTest().test(strs2,100000,1900000,100000); } private void testErr(String[] strings) throws Exception{...
排序算法,基本的高级语言都有一些提供。C语言有qsort()函数,C++有sort()函数,java语言有Arrays类(不是Array)。用这些排序时,都可以写自己的排序规则
主要介绍了Java数组高级算法与Arrays类常见操作,结合实例形式总结分析了Java数组常见的排序算法、查找算法相关原理、实现与使用技巧,需要的朋友可以参考下
含有冒泡、选择、插入、快速、arrays排序
对于整形和其他的基本类型, Arrays.sort() 综合利用了双枢轴快速排序、归并排序和启发式插入排序。这个算法是很强大的,可以在很多情况下通用。针对大规模的数组还支持更多变种。我拿自己仓促写的排序算法跟Java...
Java Methods-Arrays.ppt
/** *Arrays提供数组操作的一系列实用方法 *1输出 *2排序 *3二分查找 *4复制 *5扩容 */
现有股票数据XX条,无序...注意:实现排序算法可以使用冒泡排序,插入排序,堆排序,选择排序,快速排序等,任何的排序算法都是可以被接受的,但不能使用系统库中自带的排序函数,如List.sort() 或者 Arrays.sort()。
Java, Java, Java, Object-Oriented Problem Solving (3rd Edition) 3rd Edition by Ralph Morelli (Author), Ralph Walde (Author) 856 pages (June 25, 2017) 出版社: Prentice Hall; 3 edition Language: ...
泛型类型:定义泛型类型时,使用尖括号,并在尖括号中指定类型参数。例如,List表示一个字符串类型的列表。 泛型方法:定义泛型方法时,在方法名后面使用尖括号,并在尖括号中指定类型参数。例如,public static <T>...
java arrays类
可视化三种不同排序算法的Java应用程序:冒泡排序,快速排序和数组排序,可以选择对排序时进行的每个比较播放不同的音调。 该应用程序包含4个控件和一个按钮,用于开始可视化。 排序方法ChoiceBox允许在不同的排序...
Toward Long Distance, Sub-diffraction Imaging Using Coherent Camera Arrays一文中的算法,采用Fourier ptychographic imaging原理,用多幅低分辨率图像重建高分辨率的图像