數組是程式的基本數據結構,數組操作是常用操作,Arrays類封裝了數組的一些常見操作,它有哪些方法?是怎麼實現的?多維數組是怎麼回事?排序方法的介面體現了怎樣的設計思維?Java是如何實現排序的?Arrays中的方法不夠用怎麼辦?... ...
數組是存儲多個同類型元素的基本數據結構,數組中的元素在記憶體連續存放,可以通過數組下標直接定位任意元素,相比我們在後續章節介紹的其他容器,效率非常高。
數組操作是電腦程式中的常見基本操作,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編程及電腦技術的本質。用心寫作,原創文章,保留所有版權。