首页 > 代码库 > Java的Arrays部分算法详解
Java的Arrays部分算法详解
java的java.util.Arrays工具类提供了很多有用的方法,而且有很多方法是重载(overload)的,现在来研究一些部分算法的应用。
1. 二分查找double数组
public static int binarySearch(double[] a, int fromIndex, int toIndex, double key) { rangeCheck(a.length, fromIndex, toIndex); return binarySearch0(a, fromIndex, toIndex, key); } // Like public version, but without range checks. private static int binarySearch0(double[] a, int fromIndex, int toIndex, double key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; double midVal = a[mid]; if (midVal < key) low = mid + 1; // Neither val is NaN, thisVal is smaller else if (midVal > key) high = mid - 1; // Neither val is NaN, thisVal is larger else { long midBits = Double.doubleToLongBits(midVal); long keyBits = Double.doubleToLongBits(key); if (midBits == keyBits) // Values are equal return mid; // Key found else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN) low = mid + 1; else // (0.0, -0.0) or (NaN, !NaN) high = mid - 1; } } return -(low + 1); // key not found. }
需要注意的是,对于两个double类型的数m和n,不能够使用m==n来判断二者是不是相等,只能通过Math.abs(m-n)<=e(e是精确度,比如0.0000001)来判定。
这里使用了long java.lang.Double.doubleToLongBits(double value)来实现相等判断的。
long midBits = Double.doubleToLongBits(midVal); long keyBits = Double.doubleToLongBits(key);
long java.lang.Double.doubleToLongBits(double value)是为了
“Returns a representation of the specified floating-point value according to the IEEE 754 floating-point "double format" bit layout.(根据IEEE754规范,返回一个代表着一个浮点数的bit数) ”,
该方法源码的实现中涉及到了一个本地方法,没找到源代码==
public static native long doubleToRawLongBits(double value);
2. 判断两个数组A,B是否相等
过程:
判断引用是不是相等,相等,返回true;
A和B中是不是null,有null,返回false;
判断A和B的长度是不是相等,不相等,返回false;
遍历A和B中的元素,是不是相等,不相等,返回fasle;
返回true;
public static boolean equals(boolean[] a, boolean[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; i<length; i++) if (a[i] != a2[i]) return false; return true; }
3. public static void sort(double[] a, int fromIndex, int toIndex)的实现
public static void sort(double[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex);//检查参数是否合法 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1); }
java.util.DualPivotQuicksort的优势在于,通过判断数组的长度,选择合适的排序算法,如插入、merge、快排、计数排序等。会在下一篇博客中介绍DualPivotQuicksort类。
Java的Arrays部分算法详解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。