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()
能將一些集合類型的數據方便的變成數組。