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()
能将一些集合类型的数据方便的变成数组。