- 浏览: 336256 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
yueshang520:
太厉害了
Spring读取XML配置源码解析 -
levin_china:
jianyan163qq 写道好文章!我现在遇到一个调用的问题 ...
Java中Runtime.exec的一些事 -
wenlongsust:
exec可能存在注入漏洞,如何控制安全问题啊?
Java中Runtime.exec的一些事 -
RainWu:
...
设计模式感触之代理模式应用 -
ch_dj:
面向对象涉及原则:1.开闭原则2.少用继承,多用聚合3.针对 ...
设计模式感触之代理模式应用
java.util.Arrays中有非常方便的array转换为list的方法,在 Java中List与Array的转换已经提及了,这里再介绍下其中的排序算法:
在java.util.Arrays中,排序(sort)部分占的篇幅最大,大量用到了重载,一种是根据参数类型的重载,也就是如:
public static void sort(long[] a); public static void sort(int[] a); ……
另外一种就是参数个数的重载,是和上面的相对应的:
public static void sort(int[] a); public static void sort(int[] a, int fromIndex, int toIndex);
其实在原理上都差不多,第一种重载是根据传入数组的类型选择对应的排序;第二种是根据传入的条件多少来决定,下面以
long[]的实现为例初步分析下过程:
public static void sort(long[] a) { sort1(a, 0, a.length); }
其相同类型的重载为:
public static void sort(long[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); sort1(a, fromIndex, toIndex-fromIndex); }
可以看出,有起始限制的sort首先是验证传入的起始限界是否合法,而没有起始限制的sort默认就是全排序了:/**
* Sorts the specified sub-array of longs into ascending order. */ private static void sort1(long x[], int off, int len) { // Insertion sort on smallest arrays //如果待排序的范围很小,就选择插入排序,最是简洁,复杂度O(n2) if (len < 7) { for (int i=off; i<len+off; i++) for (int j=i; j>off && x[j-1]>x[j]; j--) swap(x, j, j-1); return; } // Choose a partition element, v //选择快排,先找出一个分区值,这里有个小技巧,取一半时采用的是移位,比 有时候使用的len/2要好一点,预设为中间位置的值 int m = off + (len >> 1); // Small arrays, middle element if (len > 7) { int l = off; int n = off + len - 1; if (len > 40) { // Big arrays, pseudomedian of 9,就是找9点点来确定更好的分区点,下面可以看出,这9个点是较均匀的插值,med3是计算x数组中后面三个位置上的哪个值在中间的一个方法 int s = len/8; l = med3(x, l, l+s, l+2*s); m = med3(x, m-s, m, m+s); n = med3(x, n-2*s, n-s, n); } m = med3(x, l, m, n); // Mid-size, med of 3,找到分区值 } long v = x[m]; // Establish Invariant: v* (<v)* (>v)* v*,其实就是构建区域,和分区值相等的区域,所有元素都小于分区值的区域,所有元素都大于分区值的区域,和分区值相等的区域 int a = off, b = a, c = off + len - 1, d = c; while(true) { //将与分区值相等的值移到头部,尾部为全部小于分区值的元素 while (b <= c && x[b] <= v) { if (x[b] == v) swap(x, a++, b); b++; } //将与分区值相等的值移到尾部,头部为全部大于分区值的元素 while (c >= b && x[c] >= v) { if (x[c] == v) swap(x, c, d--); c--; } //中止条件 if (b > c) break; swap(x, b++, c--); } // Swap partition elements back to middle,交换,成为三个区域,分别为小于、等于和大于分区值的三个 int s, n = off + len; s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); // Recursively sort non-partition-elements,在两边的区域递归 if ((s = b-a) > 1) sort1(x, off, s); if ((s = d-c) > 1) sort1(x, n-s, s); }
区域交换算法,简洁美:
/** * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. */ private static void vecswap(long x[], int a, int b, int n) { for (int i=0; i<n; i++, a++, b++) swap(x, a, b); }
返回三个数中间数的算法,稍微有点晕:
/** * Returns the index of the median of the three indexed longs. */ private static int med3(long x[], int a, int b, int c) { return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a) : (x[b] > x[c] ? b : x[a] > x[c] ? c : a)); }
关于long数组的排序就结束了!
其它基本类型如int, byte, char处理过程完全类似;
folat和double的后期处理也一样,只是会多一个初始化过程,这是由于浮点数的特性决定的,以float为例,在执行sort1之前的预处理:
private static void sort2(float a[], int fromIndex, int toIndex) {
final int NEG_ZERO_BITS = Float.floatToIntBits(-0.0f);
/*
* The sort is done in three phases to avoid the expense of using
* NaN and -0.0 aware comparisons during the main sort.避免事实上不需要比较,如NaN,-0.0和0.0事实上相等等
*/
/*
* Preprocessing phase: Move any NaN's to end of array, count the
* number of -0.0's, and turn them into 0.0's.预处理阶段,将NaN移到队尾,计算-0.0的个数并转换为0.0
*/
int numNegZeros = 0;
int i = fromIndex, n = toIndex;
while(i < n) {
if (a[i] != a[i]) {
float swap = a[i];
a[i] = a[--n];
a[n] = swap;
} else {
if (a[i]==0 && Float.floatToIntBits(a[i])==NEG_ZERO_BITS) {
a[i] = 0.0f;
numNegZeros++;
}
i++;
}
}
// Main sort phase: quicksort everything but the NaN's,主流程,和上面long的除了数组类型和元素类型不同之外完全相同
sort1(a, fromIndex, n-fromIndex);
// Postprocessing phase: change 0.0's to -0.0's as required。后处理阶段,将之前转换为0.0的归位为-0.0
if (numNegZeros != 0) {
int j = binarySearch0(a, fromIndex, n, 0.0f); // posn of ANY zero
do {
j--;
} while (j>=0 && a[j]==0.0f);
// j is now one less than the index of the FIRST zero
for (int k=0; k<numNegZeros; k++)
a[++j] = -0.0f;
}
}
在传入对象数组的时候,采用的是归并排序,算法和上面的快排有所区别,后面探讨。
发表评论
-
警告:编码 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 1487第一部分 基础知识 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 2115关于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 500580 预备知识 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的排序算法探析(Object与泛型类型)
2012-03-10 21:16 1634在Arrays中关于基本类型如int,long,fl ... -
Java中List与Array的转换
2012-02-28 18:42 1531在编码中,经常会用到两种存储结构之间的转换,而对 ... -
Java中的桥方法
2012-01-10 00:27 6108Java中的桥方法是合成方法(synthetic met ... -
设计模式感触之代理模式-远程代理
2012-01-08 16:33 36611 远程代理的意义 远程代理为一个位于不同的地址空间的 ... -
设计模式感触之代理模式应用
2012-01-03 17:30 4342设计模式感触之代理模式应用 如果说看完设计模式之 ... -
Java泛型学习
2010-11-06 22:19 1083泛型程序设计(Generic Programming)可以使编 ... -
正在学JAVA的请看看:JAVA学习之路
2010-11-05 15:32 1157JAVA是一种平 ... -
JAVA学习路线图
2010-11-05 15:29 1449最近论坛上看到好几个朋友都在问,如何学习 Java的问 ...
相关推荐
031112_【第11章:Java常用类库】_Arrays笔记
这个资源是关于Java中排序算法实现的简单示例。排序算法是计算机科学中的基础概念,用于按升序或降序排列数据集。这里提供了两种常见的排序算法实现:冒泡排序和选择排序。 冒泡排序(Bubble Sort) 是一种基本的...
## 九种内部排序算法的Java实现及其性能测试 ### 9种内部排序算法性能比较 第九种为java.util.Arrays.sort(改进的快速排序方法) 1. 100000的随机数据集 ![](http://7xlkoc.com1.z0.glb.clouddn.com/sort1.jpg) ...
•转换 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期末复习-常用类库 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 { // 需要排序的数组,...
在Java中对于字符串数组的排序,我们可以使用Arrays.sort(String[])方法很便捷的进行排序。例如: String[] arrays = new String[] { gyu, sdf, zf, 大同, 收到, 地方, 三等分, 的人, 反对高铁, 泛代数, 上的投入...
排序算法,基本的高级语言都有一些提供。C语言有qsort()函数,C++有sort()函数,java语言有Arrays类(不是Array)。用这些排序时,都可以写自己的排序规则
String[] strs2=new String[]{"希尔排序","直接插入排序","折半插入排序","冒泡排序"}; new SortTest().test(strs2,100000,1900000,100000); } private void testErr(String[] strings) throws Exception{...
含有冒泡、选择、插入、快速、arrays排序
主要介绍了Java数组高级算法与Arrays类常见操作,结合实例形式总结分析了Java数组常见的排序算法、查找算法相关原理、实现与使用技巧,需要的朋友可以参考下
Java Methods-Arrays.ppt
对于整形和其他的基本类型, Arrays.sort() 综合利用了双枢轴快速排序、归并排序和启发式插入排序。这个算法是很强大的,可以在很多情况下通用。针对大规模的数组还支持更多变种。我拿自己仓促写的排序算法跟Java...
/** *Arrays提供数组操作的一系列实用方法 *1输出 *2排序 *3二分查找 *4复制 *5扩容 */
现有股票数据XX条,无序...注意:实现排序算法可以使用冒泡排序,插入排序,堆排序,选择排序,快速排序等,任何的排序算法都是可以被接受的,但不能使用系统库中自带的排序函数,如List.sort() 或者 Arrays.sort()。
java arrays类
可视化三种不同排序算法的Java应用程序:冒泡排序,快速排序和数组排序,可以选择对排序时进行的每个比较播放不同的音调。 该应用程序包含4个控件和一个按钮,用于开始可视化。 排序方法ChoiceBox允许在不同的排序...
Toward Long Distance, Sub-diffraction Imaging Using Coherent Camera Arrays一文中的算法,采用Fourier ptychographic imaging原理,用多幅低分辨率图像重建高分辨率的图像
在Java中,Arrays类是一个实用工具类,用于在数组上执行各种操作,包括排序、搜索、比较等。它提供了一组静态方法,以便在数组中进行常见的操作。下面是一个超级详细的介绍Java中Arrays类的常用方法和功能。
Beginning Java 9 Fundamentals Arrays, Objects, Modules, JShell, and Regular Expressions 英文无水印pdf pdf所有页面使用FoxitReader和PDF-XChangeViewer测试都可以打开 本资源转载自网络,如有侵权,请联系...