Flyingis

         作者：Flyingis

    數(shù)組是Java語(yǔ)言內(nèi)置的類型，除此之外，Java有多種保存對(duì)象引用的方式。Java類庫(kù)提供了一套相當(dāng)完整的容器類，使用這些類的方法可以保存和操縱對(duì)象。下面分別進(jìn)行討論，在研究Java容器類之前，先了解一下Java數(shù)組的基本功能和特性。

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

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

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

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

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

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

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

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

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

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

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

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

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

3.  數(shù)組的排序

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

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

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

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

其它相關(guān)內(nèi)容：
Java容器分析--List和Set
Java容器分析--Map