| 在论坛和生活中总是碰到不停的找JAVA排序和查找算法的人，问哪里有源代码，呵呵。其实JAVA本身给大家提供了一个很好的类，那就是Arrays。Arrays隶属书The Collections Framework。这个类提供了数组的填充，查找，比较，排序等一系列的对数组的操作。
一 填充：
Arrays.fill(type[] a, type val)系列方法是给，数组填充。就是简单的把一个数组全部或者某段数据填成一个特殊的值。
?
二 查找：
binarySearch(type[] a, type key)系列方法是，在某类型的数组中用2分法查找特定的Key的元素，返回元素号。前提是这个数组是经过排序的，如果有多个元素和Key值相等的情况下，无法预料，返回的是哪一个。对于返回值，有以下规律，返回值 < 0表示没有找到，返回值 >= 0说明找到了。
对于插入，Arrays没有特殊算法，一般对数组的插入都是转化为Collection之后再做的，但是binarySearch还是能帮你找到数组的插入点的，插入点位置为返回值的绝对值减1(|返回值| - 1)。
对排序过的数组查找，算法用2分法已经相当快了，呵呵。
?
三 比较:
equals(type[] a, type[] b) 系列方法是做两个数组的比较的，相等返回true。这个方法运用的时候，有些地方要注意。
比较两个float数组的时候，对每个元素比较，程序不是用的==来判断的，而是用new Float(f1).equals(new Float(f2))，这个方法认为NaN等于它本身，0.0f不等于-0.0f。对于double数组也是一样的。
对于Object[]数组呢，是用的(e1==null ? e2==null : e1.equals(e2))。
?
四 排序:
sort(type[] a)系列方法是对数组排序的。Sun用的排序算法是调整快速排序法,采用的是Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993)。这个算法排序要n* O(n)时间的大量数据，只需要O(n1ogn)时间。
关于快速排序法参考：(http://algorithm.myrice.com/algorithm/commonalg/sort/internal_sorting/quick_sort/quick_sort.htm
快速排序 Quick Sort
我们已经知道，在决策树计算模型下，任何一个基于比较来确定两个元素相对位置的排序算法需要Ω(nlogn)计算时间。如果我们能设计一个需要O(n1ogn)时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。快速排序算法它在平均情况下需要O(nlogn)时间。这个算法是由C.A.R.Hoare发明的。)
?
五 数组的转换:
用Arrays.asList(Object[] a)能够实现数组到ArrayList的转换。同时利用Collection.toArray()能将一些集合类型的数据方便的变成数组。
?
六 杂谈:
查看源代码的发现:针对double类型的比较时，在相等的情况下，Sun的源代码种都作了进一步的比较。
例子1：
??? if (a[i]==0 && Double.doubleToLongBits(a[i])==NEG_ZERO_BITS) {
例子2：
????? if (midVal < key) {
??????????????? cmp = -1;?? // Neither val is NaN, thisVal is smaller
??????????? } else if (midVal > key) {
??????????????? cmp = 1;??? // Neither val is NaN, thisVal is larger
??????????? } else {
??????????????? long midBits = Double.doubleToLongBits(midVal);
??????????????? long keyBits = Double.doubleToLongBits(key);
??????????????? cmp = (midBits == keyBits ?? 0 : // Values are equal
?????????????????????? (midBits < keyBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
??????????????????????? 1));???????????????????? // (0.0, -0.0) or (NaN, !NaN)
??????????? }
看来在double类型的比较上，如果用==比从精度上考虑，还是有问题的。
另外对于对象数组的查找和排序的时候比普通类型数组多一个方法：
public static int binarySearch(Object[] a, Object key, Comparator c)
public static void sort(Object[] a, Comparator c)
这个地方Comparator是你自己为对象比较定义的算法，在运行的时候，将对象的比较代理给Comparator的public int compare(Object?o1, Object?o2)不过Comparator是一个接口，具体实现就是你自己的算法了。
?
[参考文献]
JavaTM 2 Platform, Standard Edition, v 1.3.1 API Specification
JDK源代码
http://algorithm.myrice.com/algorithm/commonalg/sort/internal_sorting/quick_sort/quick_sort.htm 
|
本类阅读TOP10