Arrays類及其方法分析
排序
Arrays.sort()方法，對於基本資料型別採用DualPivotQuicksort（多路快排）進行排序，對於引用型別的陣列，採用MergeSort（歸併排序）進行排序，下面我們分別來講一下這兩類排序演算法。
對基本型別陣列的排序
Java中的八種基本資料型別，除了boolean，其它七種都是可以且有需求進行排序的，如果一個數組是單一的基礎型別，形如int[] data, long data[]都可以直接使用Arrays.sort()進行排序。對於所有可排序的基本型別，都是採用DualPivotQuicksort來進行排序的。首先來看個例子：
package com.adam.java.algo.arrays;
import java.util.Arrays;
import org.junit.Test;
public class ArraysBasicTest {
@Test
public void testSortInteger() {
int data[] = { 10, 8, 9, 1, 2, 5, 98, 3, 7, 66 };
Arrays.sort(data);
for (int i : data) {
System.out.print(i + " ");
}
}
@Test
public void testSortChar() {
char data[] = { 'D', 'B', 'E', 'C', 'H', 'A', 'Y', 'G', 'I', 'O' };
Arrays.sort(data);
for (char i : data) {
System.out.print(i + " ");
}
}
}
輸出：
1 2 3 5 7 8 9 10 66 98
A B C D E G H I O Y
這裡我們要看一下Arrays.sort()採用的演算法了，我們檢視下JDK原始碼。
/**
* Sorts the specified array into ascending numerical order.
*
* <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
發現所有的基本排序都是直接使用DualPivotQuicksort.sort()進行的，因此，我們有必要了解一下DualPivotQuicksort的原理。基本思想就是：
元素個數從1-47，則直接使用插入排序進行排序。
元素個數從47-286，則使用多路快速排序。
元素個數大於286，則使用歸併排序
這裡我們研究下多路快排的原理，首先我們回顧一下經典快排是怎麼實現的。
經典快排實現思路：
1. 找一箇中軸，一般情況選取陣列的第一個元素。
2. 定義兩個指標，分別指向最左邊和最右邊，從右邊開始遍歷，如果大於中軸，則右邊指標左移一位，如果小於中軸，則互換位置；同理再從左邊開始和中軸比較，如果小於中軸，指標向右移動，如果大於中軸，則互換位置。
3. 一趟排序下來，中軸左邊的都小於中軸，右邊的都大於中軸。
4.遞迴的對子陣列進行如上操作，不穩定，時間複雜度最優情況O(nlogn)，最壞情況為基本有序時為O(n2)。關於快排的詳細說明，請參考另一篇博文。
多路快排實現思路：
1. 選取兩個中軸P1, P2。
2. 假設P1<P2，否則交換。
3. 過程中原陣列會分為四個部分：小於中軸1，大於中軸2，介於兩個中軸之間，未排序部分（剛開始除了兩個中軸，其它元素都屬於這部分）。
4. 開始後，從未排序部分選取一個數，和兩個中軸作比較，然後放到合適的位置，一直到未排序部分無資料，結束一趟排序。
5. 遞迴地處理子陣列，穩定排序，時間複雜度穩定為O(nlogn)。
對引用型別的陣列排序
我們舉個例子，對User型別的陣列，根據年齡進行排序，此處用到Comparator介面，更多關於Comparator的介紹，請點選。
新建一個User類：
package com.adam.java.algo.arrays;
public class User {
private String name;
private String gender;
private int age;
public User(String name, String gender, int age) {
this.name = name;
this.gender = gender;
this.age = age;
}
/**
* @return the name
*/
public String getName() {
return name;
}
/**
* @param name
* the name to set
*/
public void setName(String name) {
this.name = name;
}
/**
* @return the gender
*/
public String getGender() {
return gender;
}
/**
* @param gender
* the gender to set
*/
public void setGender(String gender) {
this.gender = gender;
}
/**
* @return the age
*/
public int getAge() {
return age;
}
/**
* @param age
* the age to set
*/
public void setAge(int age) {
this.age = age;
}
}
再建一個排序類：
package com.adam.java.algo.arrays;
import java.util.Comparator;
public class UserComparator implements Comparator<User> {
@Override
public int compare(User o1, User o2) {
return o1.getAge() - o2.getAge();
}
}
測試：
package com.adam.java.algo.arrays;
import java.util.Arrays;
public class ArraysTest {
public static void main(String[] args) {
User[] users = new User[]{new User("egg", "male", 26), new User("Kity", "Female", 25), new User("Pole", "male", 23), new User("Jack", "male", 28)};
Arrays.sort(users, new UserComparator());
for (User user : users) {
System.out.println("name: " + user.getName() + " ,age: "+user.getAge());
}
}
}
輸出：
name: Pole ,age: 23 name: Kity ,age: 25 name: egg ,age: 26 name: Jack ,age: 28
這就是一個簡單的對引用型別的陣列排序的例子，在JDK1.8中，對引用型別的排序，採用的歸併排序的演算法。
在JDK1.8中，對於排序方法，還引入了parallelSort()，每個sort()都有對應的並行排序方法，當陣列元素個數大於2的13次（8196）後採用parallelSort()。
搜尋
在用二分搜尋對一個已經有序的陣列進行查詢，如果存在，返回key在該陣列中的位置，如果不存在，返回負數，值為：-插入點-1，舉個例子：
假設一個排好序的陣列是：1,6,8,10,12，如果key為7，則返回值為-3，因為7應該插入到6,8之間，所以插入點為2（下標從0開始），所以返回值為-2-1=-3。
ArrayToList
這方面，是將一個數組，轉換成一個list形式，注意：通常情況下，如果該陣列是int型的，如int[[ data，這種情況會出現並不是直接將該陣列中的所有元素轉成新的list的所有元素，而是將整個陣列，轉成list的一個元素，這是一種特殊情況，將型別int改成Integer就可以避免了。此處感謝網友@Java我人生指正！
/**
* Returns a fixed-size list backed by the specified array. (Changes to
* the returned list "write through" to the array.) This method acts
* as bridge between array-based and collection-based APIs, in
* combination with {@link Collection#toArray}. The returned list is
* serializable and implements {@link RandomAccess}.
*
* <p>This method also provides a convenient way to create a fixed-size
* list initialized to contain several elements:
* <pre>
* List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
* </pre>
*
* @param <T> the class of the objects in the array
* @param a the array by which the list will be backed
* @return a list view of the specified array
*/
@SafeVarargs
@SuppressWarnings("varargs")
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
根據註釋得知，返回的新list是個定長的list，而且並不可以就行新增或者刪除元素，否則報：java.lang.UnsupportedOperationException異常。這是為什麼？因為此處的ArrayList並非我們常用的java.util.ArrayList類，而是Arrays類的一個內部類，因為繼承了AbstractList，所有可以和list相互轉換，但是不具備add和remove等操作。
CopyOf
Arrays.copyOf()用來進行陣列的複製，返回一個全新的陣列，可以傳入一個引數來定義新陣列的大小，如果傳入的數小於原來的陣列長度，則直接把原陣列多餘的部分剪掉，如果傳入的值大於原陣列，則新陣列多餘的部分補預設值（對於int型別的，補0）。