月亮的太陽

1.  數(shù)組的基本特性

         數(shù)組與其它種類的容器(List/Set/Map)之間的區(qū)別在于效率、確定的類型和保存基本類型數(shù)據(jù)的能力。數(shù)組是一種高效的存儲和隨機(jī)訪問對象引用序列的方式，使用數(shù)組可以快速的訪問數(shù)組中的元素。但是當(dāng)創(chuàng)建一個數(shù)組對象(注意和對象數(shù)組的區(qū)別)后，數(shù)組的大小也就固定了，當(dāng)數(shù)組空間不足的時候就再創(chuàng)建一個新的數(shù)組，把舊的數(shù)組中所有的引用復(fù)制到新的數(shù)組中。

         Java中的數(shù)組和容器都需要進(jìn)行邊界檢查，如果越界就會得到一個RuntimeException異常。這點(diǎn)和C++中有所不同，C++中vector的操作符[]不會做邊界檢查，這在速度上會有一定的提高，Java的數(shù)組和容器會因?yàn)闀r刻存在的邊界檢查帶來一些性能上的開銷。

         Java中通用的容器類不會以具體的類型來處理對象，容器中的對象都是以Object類型處理的，這是Java中所有類的基類。另外，數(shù)組可以保存基本類型，而容器不能，它只能保存任意的Java對象。

         一般情況下，考慮到效率與類型檢查，應(yīng)該盡可能考慮使用數(shù)組。如果要解決一般化的問題，數(shù)組可能會受到一些限制，這時可以使用Java提供的容器類。 

2.  操作數(shù)組的實(shí)用功能

         在java.util.Arrays類中，有許多static靜態(tài)方法，提供了操作數(shù)組的一些基本功能：

         equals()方法----用于比較兩個數(shù)組是否相等，相等的條件是兩個數(shù)組的元素個數(shù)必須相等，并且對應(yīng)位置的元素也相等。

         fill()方法----用以某個值填充整個數(shù)組，這個方法有點(diǎn)笨。

         asList()方法----接受任意的數(shù)組為參數(shù)，將其轉(zhuǎn)變?yōu)?/SPAN>List容器。

         binarySearch()方法----用于在已經(jīng)排序的數(shù)組中查找元素，需要注意的是必須是已經(jīng)排序過的數(shù)組。當(dāng)Arrays.binarySearch()找到了查找目標(biāo)時，該方法將返回一個等于或大于0的值，否則將返回一個負(fù)值，表示在該數(shù)組目前的排序狀態(tài)下此目標(biāo)元素所應(yīng)該插入的位置。負(fù)值的計(jì)算公式是“-x-1”。x指的是第一個大于查找對象的元素在數(shù)組中的位置，如果數(shù)組中所有的元素都小于要查找的對象，則x = a.size()。如果數(shù)組中包含重復(fù)的元素，則無法保證找到的是哪一個元素，如果需要對沒有重復(fù)元素的數(shù)組排序，可以使用TreeSet或者LinkedHashSet。另外，如果使用Comparator排序了某個對象數(shù)組，在使用該方法時必須提供同樣的Comparator類型的參數(shù)。需要注意的是，基本類型數(shù)組無法使用Comparator進(jìn)行排序。

         sort()方法----對數(shù)組進(jìn)行升序排序。

         在Java標(biāo)準(zhǔn)類庫中，另有static方法System.arraycopy()用來復(fù)制數(shù)組，它針對所有類型做了重載。

3.  數(shù)組的排序

         在Java1.0和1.1兩個版本中，類庫缺少基本的算法操作，包括排序的操作，Java2對此進(jìn)行了改善。在進(jìn)行排序的操作時，需要根據(jù)對象的實(shí)際類型執(zhí)行比較操作，如果為每種不同的類型各自編寫一個不同的排序方法，將會使得代碼很難被復(fù)用。一般的程序設(shè)計(jì)目標(biāo)應(yīng)是“將保持不變的事物與會發(fā)改變的事物相分離”。在這里，不變的是通用的排序算法，變化的是各種對象相互比較的方式。

Java有兩種方式來實(shí)現(xiàn)比較的功能，一種是實(shí)現(xiàn)java.lang.Comparable接口，該接口只有一個compareTo()方法，并以一個Object類為參數(shù)，如果當(dāng)前對象小于參數(shù)則返回負(fù)值，如果相等返回零，如果當(dāng)前對象大于參數(shù)則返回正值。另一種比較方法是采用策略(strategy)設(shè)計(jì)模式，將會發(fā)生變化的代碼封裝在它自己的類(策略對象)中，再將策略對象交給保持不變的代碼中，后者使用此策略實(shí)現(xiàn)它的算法。因此，可以為不同的比較方式生成不同的對象，將它們用在同樣的排序程序中。在此情況下，通過定義一個實(shí)現(xiàn)了Comparator接口的類而創(chuàng)建了一個策略，這個策略類有compare()和equals()兩個方法，一般情況下實(shí)現(xiàn)compare()方法即可。

使用上述兩種方法即可對任意基本類型的數(shù)組進(jìn)行排序，也可以對任意的對象數(shù)組進(jìn)行排序。再提示一遍，基本類型數(shù)組無法使用Comparator進(jìn)行排序。

Java標(biāo)準(zhǔn)類庫中的排序算法針對排序的類型進(jìn)行了優(yōu)化——針對基本類型設(shè)計(jì)了“快速排序”，針對對象設(shè)計(jì)的“穩(wěn)定歸并排序”。一般不用擔(dān)心其性能。

Tracker:http://www.aygfsteel.com/flyingis/archive/2005/12/15/24089.html