http://dev.csdn.net/article/33/33116.shtm

在论坛和生活中总是碰到不停的找
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.ht m
快速排序 Quick Sort

我们已经知道, 在决策树计算模型下,任何一个基于比较来确定两个元素相对位置的排序算法需要 Ω(nlogn) 计算时间 。如果我们能设计一个需要 O(n1ogn) 时间的排序算法,则在渐近的意义上,这个排序算法就是最优的。许多排序算法都是追求这个目标。快速排序算法它在平均情况下需要 O(nlogn) 时间。这个算法是由 C.A.R.Hoare 发明的。 )


五 数组的转换:

Arrays.asList(Object[] a) 能够实现数组到 ArrayList 的转换。同时利用 Collection.toArray() 能将一些集合类型的数据方便的变成数组。