數組是存儲多個同類型元素的基本數據結構，數組中的元素在內存連續存放，可以通過數組下標直接定位任意元素，相比我們在後續章節介紹的其他容器，效率非常高。
數組操作是計算機程序中的常見基本操作，Java中有一個類Arrays，包含一些對數組操作的靜態方法，本節主要就來討論這些方法，我們先來看怎麼用，然後再來看它們的實現原理。學習Arrays的用法，我們就可以避免重新發明輪子，直接使用，學習它的實現原理，我們就可以在需要的時候，自己實現它不具備的功能。
用法
toString
Arrays的toString方法可以方便的輸出一個數組的字符串形式，方便查看，它有九個重載的方法，包括八種基本類型數組和一個對象類型數組，這裡列舉兩個：
public static String toString(int[] a) public static String toString(Object[] a)
例如：
int[] arr = {9,8,3,4};
System.out.println(Arrays.toString(arr));
String[] strArr = {"hello", "world"};
System.out.println(Arrays.toString(strArr));
輸出為
[9, 8, 3, 4] [hello, world]
如果不使用Arrays.toString，直接輸出數組自身，即代碼改為：
int[] arr = {9,8,3,4};
System.out.println(arr);
String[] strArr = {"hello", "world"};
System.out.println(strArr);
則輸出會變為如下所示：
[I@1224b90 [Ljava.lang.String;@728edb84
這個輸出就難以閱讀了，@後面的數字表示的是內存的地址。
數組排序 - 基本類型
排序是一個非常常見的操作，同toString一樣，對每種基本類型的數組，Arrays都有sort方法(boolean除外)，如：
public static void sort(int[] a) public static void sort(double[] a)
排序按照從小到大升序排，看個例子：
int[] arr = {4, 9, 3, 6, 10};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
輸出為：
[3, 4, 6, 9, 10]
數組已經排好序了。
sort還可以接受兩個參數，對指定范圍內的元素進行排序，如：
public static void sort(int[] a, int fromIndex, int toIndex)
包括fromIndex位置的元素，不包括toIndex位置的元素，如：
int[] arr = {4, 9, 3, 6, 10};
Arrays.sort(arr,0,3);
System.out.println(Arrays.toString(arr));
輸出為：
[3, 4, 9, 6, 10]
只對前三個元素排序。
數組排序 - 對象類型
除了基本類型，sort還可以直接接受對象類型，但對象需要實現Comparable接口。
public static void sort(Object[] a) public static void sort(Object[] a, int fromIndex, int toIndex)
我們看個String數組的例子：
String[] arr = {"hello","world", "Break","abc"};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
輸出為：
[Break, abc, hello, world]
"Break"之所以排在最前面，是因為大寫字母比小寫字母都小。那如果排序的時候希望忽略大小寫呢？
數組排序 - 自定義比較器
sort還有另外兩個重載方法，可以接受一個比較器作為參數：
public static <T> void sort(T[] a, Comparator<? super T> c)
public static <T> void sort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c)
方法聲明中的T表示泛型，泛型我們在後續章節再介紹，這裡表示的是，這個方法可以支持所有對象類型，只要傳遞這個類型對應的比較器就可以了。Comparator就是比較器，它是一個接口，定義是：
public interface Comparator<T> {
int compare(T o1, T o2);
boolean equals(Object obj);
}
最主要的是compare這個方法，它比較兩個對象，返回一個表示比較結果的值，-1表示o1小於o2，0表示相等，1表示o1大於o2。
排序是通過比較來實現的，sort方法在排序的過程中，需要對對象進行比較的時候，就調用比較器的compare方法。
String類有一個public靜態成員，表示忽略大小寫的比較器：
public static final Comparator<String> CASE_INSENSITIVE_ORDER
= new CaseInsensitiveComparator();
我們通過這個比較器再來對上面的String數組排序：
String[] arr = {"hello","world", "Break","abc"};
Arrays.sort(arr, String.CASE_INSENSITIVE_ORDER);
System.out.println(Arrays.toString(arr));
這樣，大小寫就忽略了，輸出變為了：
[abc, Break, hello, world]
為進一步理解Comparator，我們來看下String的這個比較器的主要實現代碼：
private static class CaseInsensitiveComparator
implements Comparator<String> {
public int compare(String s1, String s2) {
int n1 = s1.length();
int n2 = s2.length();
int min = Math.min(n1, n2);
for (int i = 0; i < min; i++) {
char c1 = s1.charAt(i);
char c2 = s2.charAt(i);
if (c1 != c2) {
c1 = Character.toUpperCase(c1);
c2 = Character.toUpperCase(c2);
if (c1 != c2) {
c1 = Character.toLowerCase(c1);
c2 = Character.toLowerCase(c2);
if (c1 != c2) {
// No overflow because of numeric promotion
return c1 - c2;
}
}
}
}
return n1 - n2;
}
}
代碼比較直接，就不解釋了。
sort默認都是從小到大排序，如果希望按照從大到小排呢？對於對象類型，可以指定一個不同的Comparator，可以用匿名內部類來實現Comparator，比如可以這樣：
String[] arr = {"hello","world", "Break","abc"};
Arrays.sort(arr, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o2.compareToIgnoreCase(o1);
}
});
System.out.println(Arrays.toString(arr));
程序輸出為：
[world, hello, Break, abc]
以上代碼使用一個匿名內部類實現Comparator接口，返回o2與o1進行忽略大小寫比較的結果，這樣就能實現，忽略大小寫，且按從大到小排序。為什麼o2與o1比就逆序了呢？因為默認情況下，是o1與o2比。
Collections類中有兩個靜態方法，可以返回逆序的Comparator，如
public static <T> Comparator<T> reverseOrder() public static <T> Comparator<T> reverseOrder(Comparator<T> cmp)
關於Collections類，我們在後續章節再詳細介紹。
這樣，上面字符串忽略大小寫逆序排序的代碼可以改為：
String[] arr = {"hello","world", "Break","abc"};
Arrays.sort(arr, Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));
System.out.println(Arrays.toString(arr));
傳遞比較器Comparator給sort方法，體現了程序設計中一種重要的思維方式，將不變和變化相分離，排序的基本步驟和算法是不變的，但按什麼排序是變化的，sort方法將不變的算法設計為主體邏輯，而將變化的排序方式設計為參數，允許調用者動態指定，這也是一種常見的設計模式，它有一個名字，叫策略模式，不同的排序方式就是不同的策略。
二分查找
Arrays包含很多與sort對應的查找方法，可以在已排序的數組中進行二分查找，所謂二分查找就是從中間開始找，如果小於中間元素，則在前半部分找，否則在後半部分找，每比較一次，要麼找到，要麼將查找范圍縮小一半，所以查找效率非常高。
二分查找既可以針對基本類型數組，也可以針對對象數組，對對象數組，也可以傳遞Comparator，也都可以指定查找范圍，如下所示：
針對int數組
public static int binarySearch(int[] a, int key)
public static int binarySearch(int[] a, int fromIndex, int toIndex,
int key)
針對對象數組
public static int binarySearch(Object[] a, Object key)
自定義比較器
public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
如果能找到，binarySearch返回找到的元素索引，比如說：
int[] arr = {3,5,7,13,21};
System.out.println(Arrays.binarySearch(arr, 13));
輸出為3。如果沒找到，返回一個負數，這個負數等於：-(插入點+1)，插入點表示，如果在這個位置插入沒找到的元素，可以保持原數組有序，比如說：
int[] arr = {3,5,7,13,21};
System.out.println(Arrays.binarySearch(arr, 11));
輸出為-4，表示插入點為3，如果在3這個索引位置處插入11，可以保持數組有序，即數組會變為：{3,5,7,11,13,21}
需要注意的是，binarySearch針對的必須是已排序數組，如果指定了Comparator，需要和排序時指定的Comparator保持一致，另外，如果數組中有多個匹配的元素，則返回哪一個是不確定的。
數組拷貝
與toString一樣，也有多種重載形式，如：
public static long[] copyOf(long[] original, int newLength) public static <T> T[] copyOf(T[] original, int newLength)
後面那個是泛型用法，這裡表示的是，這個方法可以支持所有對象類型，參數是什麼數組類型，返回結果就是什麼數組類型。
newLength表示新數組的長度，如果大於原數組，則後面的元素值設為默認值。回顧一下默認值，對於數值類型，值為0，對於boolean，值為false，對於char，值為'\0'，對於對象，值為null。
來看個例子：
String[] arr = {"hello", "world"};
String[] newArr = Arrays.copyOf(arr, 3);
System.out.println(Arrays.toString(newArr));
輸出為：
[hello, world, null]
除了copyOf方法，Arrays中還有copyOfRange方法，以支持拷貝指定范圍的元素，如：
public static int[] copyOfRange(int[] original, int from, int to)
from表示要拷貝的第一個元素的索引，新數組的長度為to-from，to可以大於原數組的長度，如果大於，與copyOf類似，多出的位置設為默認值。
來看個例子：
int[] arr = {0,1,3,5,7,13,19};
int[] subArr1 = Arrays.copyOfRange(arr,2,5);
int[] subArr2 = Arrays.copyOfRange(arr,5,10);
System.out.println(Arrays.toString(subArr1));
System.out.println(Arrays.toString(subArr2));
輸出為：
[3, 5, 7] [13, 19, 0, 0, 0]
subArr1是正常的子數組，subArr2拷貝時to大於原數組長度，後面的值設為了0。
數組比較
支持基本類型和對象類型，如下所示：
public static boolean equals(boolean[] a, boolean[] a2) public static boolean equals(double[] a, double[] a2) public static boolean equals(Object[] a, Object[] a2)
只有數組長度相同，且每個元素都相同，才返回true，否則返回false。對於對象，相同是指equals返回true。
填充值
Arrays包含很多fill方法，可以給數組中的每個元素設置一個相同的值：
public static void fill(int[] a, int val)
也可以給數組中一個給定范圍的每個元素設置一個相同的值：
public static void fill(int[] a, int fromIndex, int toIndex, int val)
比如說：
int[] arr = {3,5,7,13,21};
Arrays.fill(arr,2,4,0);
System.out.println(Arrays.toString(arr));
將索引從2(含2)到4(不含4)的元素設置為0，輸出為：
[3, 5, 0, 0, 21]
哈希值
針對數組，計算一個數組的哈希值：
public static int hashCode(int a[])
計算hashCode的算法和String是類似的，我們看下代碼：
public static int hashCode(int a[]) {
if (a == null)
return 0;
int result = 1;
for (int element : a)
result = 31 * result + element;
return result;
}
回顧一下，String計算hashCode的算法也是類似的，數組中的每個元素都影響hash值，位置不同，影響也不同，使用31一方面產生的哈希值更分散，另一方面計算效率也比較高。
多維數組
之前我們介紹的數組都是一維的，數組還可以是多維的，先來看二維數組，比如：
int[][] arr = new int[2][3];
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr[i].length;j++){
arr[i][j] = i+j;
}
}
arr就是一個二維數組，第一維長度為2，第二維長度為3，類似於一個長方形矩陣，或者類似於一個表格，第一維表示行，第二維表示列。arr[i]表示第i行，它本身還是一個數組，arr[i][j]表示第i行中的第j個元素。
除了二維，數組還可以是三維、四維等，但一般而言，很少用到三維以上的數組，有幾維，就有幾個[]，比如說，一個三維數組的聲明為：
int[][][] arr = new int[10][10][10];
在創建數組時，除了第一維的長度需要指定外，其他維的長度不需要指定，甚至，第一維中，每個元素的第二維的長度可以不一樣，看個例子：
int[][] arr = new int[2][]; arr[0] = new int[3]; arr[1] = new int[5];
arr是一個二維數組，第一維的長度為2，第一個元素的第二維長度為3，而第二個為5。
多維數組到底是什麼呢？其實，可以認為，多維數組只是一個假象，只有一維數組，只是數組中的每個元素還可以是一個數組，這樣就形成二維數組，如果其中每個元素還都是一個數組，那就是三維數組。
多維數組的操作
Arrays中的toString，equals，hashCode都有對應的針對多維數組的方法：
public static String deepToString(Object[] a) public static boolean deepEquals(Object[] a1, Object[] a2) public static int deepHashCode(Object a[])
這些deepXXX方法，都會判斷參數中的元素是否也為數組，如果是，會遞歸進行操作。
看個例子：
int[][] arr = new int[][]{
{0,1},
{2,3,4},
{5,6,7,8}
};
System.out.println(Arrays.deepToString(arr));
輸出為：
[[0, 1], [2, 3, 4], [5, 6, 7, 8]]
實現原理
hashCode的實現我們已經介紹了，fill和equals的實現都很簡單，循環操作而已，就不贅述了。
toString
toString的實現也很簡單，利用了StringBuilder，我們列下代碼，但不做解釋了。
public static String toString(int[] a) {
if (a == null)
return "null";
int iMax = a.length - 1;
if (iMax == -1)
return "[]";
StringBuilder b = new StringBuilder();
b.append('[');
for (int i = 0; ; i++) {
b.append(a[i]);
if (i == iMax)
return b.append(']').toString();
b.append(", ");
}
}
拷貝
copyOf和copyOfRange利用了 System.arraycopy，邏輯也很簡單，我們也只是簡單列下代碼：
public static int[] copyOfRange(int[] original, int from, int to) {
int newLength = to - from;
if (newLength < 0)
throw new IllegalArgumentException(from + " > " + to);
int[] copy = new int[newLength];
System.arraycopy(original, from, copy, 0,
Math.min(original.length - from, newLength));
return copy;
}
二分查找
二分查找binarySearch的代碼也比較直接，主要代碼如下：
private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
T key, Comparator<? super T> c) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
T midVal = a[mid];
int cmp = c.compare(midVal, key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
有兩個標志low和high，表示查找范圍，在while循環中，與中間值進行對比，大於則在後半部分找(提高low)，否則在前半部分找(降低high)。
排序
最後，我們來看排序方法sort，與前面這些簡單直接的方法相比，sort要復雜的多，排序是計算機程序中一個非常重要的方面，幾十年來，計算機科學家和工程師們對此進行了大量的研究，設計實現了各種各樣的算法和實現，進行了大量的優化。一般而言，沒有一個所謂最好的算法，不同算法往往有不同的適用場合。
那Arrays的sort是如何實現的呢？
對於基本類型的數組，Java采用的算法是雙樞軸快速排序(Dual-Pivot Quicksort)，這個算法是Java 1.7引入的，在此之前，Java采用的算法是普通的快速排序，雙樞軸快速排序是對快速排序的優化，新算法的實現代碼位於類java.util.DualPivotQuicksort中。
對於對象類型，Java采用的算法是TimSort， TimSort也是在Java 1.7引入的，在此之前，Java采用的是歸並排序，TimSort實際上是對歸並排序的一系列優化，TimSort的實現代碼位於類java.util.TimSort中。
在這些排序算法中，如果數組長度比較小，它們還會采用效率更高的插入排序。
為什麼基本類型和對象類型的算法不一樣呢？排序算法有一個穩定性的概念，所謂穩定性就是對值相同的元素，如果排序前和排序後，算法可以保證它們的相對順序不變，那算法就是穩定的，否則就是不穩定的。
快速排序更快，但不穩定，而歸並排序是穩定的。對於基本類型，值相同就是完全相同，所以穩定不穩定沒有關系。但對於對象類型，相同只是比較結果一樣，它們還是不同的對象，其他實例變量也不見得一樣，穩定不穩定可能就很有關系了，所以采用歸並排序。
這些算法的實現是比較復雜的，所幸的是，Java給我們提供了很好的實現，絕大多數情況下，我們會用就可以了。
更多方法
其實，Arrays中包含的數組方法是比較少的，很多常用的操作沒有，比如，Arrays的binarySearch只能針對已排序數組進行查找，那沒有排序的數組怎麼方便查找呢？
Apache有一個開源包(http://commons.apache.org/proper/commons-lang/)，裡面有一個類ArrayUtils (位於包org.apache.commons.lang3)，裡面實現了更多的常用數組操作，這裡列舉一些，與Arrays類似，每個操作都有很多重載方法，我們只列舉一個。
翻轉數組元素
public static void reverse(final int[] array)
對於基本類型數組，Arrays的sort只能從小到大排，如果希望從大到小，可以在排序後，使用reverse進行翻轉。
查找元素
//從頭往後找 public static int indexOf(final int[] array, final int valueToFind) //從尾部往前找 public static int lastIndexOf(final int[] array, final int valueToFind) //檢查是否包含元素 public static boolean contains(final int[] array, final int valueToFind)
刪除元素
因為數組長度是固定的，刪除是通過創建新數組，然後拷貝除刪除元素外的其他元素來實現的。
//刪除指定位置的元素 public static int[] remove(final int[] array, final int index) //刪除多個指定位置的元素 public static int[] removeAll(final int[] array, final int... indices) //刪除值為element的元素，只刪除第一個 public static boolean[] removeElement(final boolean[] array, final boolean element)
添加元素
同刪除一樣，因為數組長度是固定的，添加是通過創建新數組，然後拷貝原數組內容和新元素來實現的。
//添加一個元素 public static int[] add(final int[] array, final int element) //在指定位置添加一個元素 public static int[] add(final int[] array, final int index, final int element) //合並兩個數組 public static int[] addAll(final int[] array1, final int... array2)
判斷數組是否是已排序的
public static boolean isSorted(int[] array)
小結
本節我們分析了Arrays類，介紹了其用法，以及基本實現原理，同時，我們介紹了多維數組以及Apache中的ArrayUtils類。對於帶Comparator參數的排序方法，我們提到，這是一種思維和設計模式，值得學習。
數組是計算機程序中的基本數據結構，Arrays類以及ArrayUtils類封裝了關於數組的常見操作，使用這些方法吧！
下一節，我們來看計算機程序中，另一種常見的操作，就是對日期的操作。
----------------
未完待續，查看最新文章，敬請關注微信公眾號“老馬說編程”(掃描下方二維碼)，從入門到高級，深入淺出，老馬和你一起探索Java編程及計算機技術的本質。用心寫作，原創文章，保留所有版權。
