Arrays类及其方法分析
排序
Arrays.sort()方法，對(duì)于基本數(shù)據(jù)類型采用DualPivotQuicksort（多路快排）進(jìn)行排序，對(duì)于引用類型的數(shù)組，采用MergeSort（歸并排序）進(jìn)行排序，下面我們分別來講一下這兩類排序算法。
對(duì)基本類型數(shù)組的排序
Java中的八種基本數(shù)據(jù)類型，除了boolean，其它七種都是可以且有需求進(jìn)行排序的，如果一個(gè)數(shù)組是單一的基礎(chǔ)類型，形如int[] data, long data[]都可以直接使用Arrays.sort()進(jìn)行排序。對(duì)于所有可排序的基本類型，都是采用DualPivotQuicksort來進(jìn)行排序的。首先來看個(gè)例子：
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);
}
發(fā)現(xiàn)所有的基本排序都是直接使用DualPivotQuicksort.sort()進(jìn)行的，因此，我們有必要了解一下DualPivotQuicksort的原理。基本思想就是：
元素個(gè)數(shù)從1-47，則直接使用插入排序進(jìn)行排序。
元素個(gè)數(shù)從47-286，則使用多路快速排序。
元素個(gè)數(shù)大于286，則使用歸并排序
這里我們研究下多路快排的原理，首先我們回顧一下經(jīng)典快排是怎么實(shí)現(xiàn)的。
經(jīng)典快排實(shí)現(xiàn)思路：
找一個(gè)中軸，一般情況選取數(shù)組的第一個(gè)元素。
定義兩個(gè)指針，分別指向最左邊和最右邊，從右邊開始遍歷，如果大于中軸，則右邊指針左移一位，如果小于中軸，則互換位置；同理再從左邊開始和中軸比較，如果小于中軸，指針向右移動(dòng)，如果大于中軸，則互換位置。
4.遞歸的對(duì)子數(shù)組進(jìn)行如上操作，不穩(wěn)定，時(shí)間復(fù)雜度最優(yōu)情況O(nlogn)，最壞情況為基本有序時(shí)為O(n2)。關(guān)于快排的詳細(xì)說明，請(qǐng)參考另一篇博文。
多路快排實(shí)現(xiàn)思路：
選取兩個(gè)中軸P1, P2。
假設(shè)P1<P2，否則交換。
過程中原數(shù)組會(huì)分為四個(gè)部分：小于中軸1，大于中軸2，介于兩個(gè)中軸之間，未排序部分（剛開始除了兩個(gè)中軸，其它元素都屬于這部分）。
開始后，從未排序部分選取一個(gè)數(shù)，和兩個(gè)中軸作比較，然后放到合適的位置，一直到未排序部分無數(shù)據(jù)，結(jié)束一趟排序。
對(duì)引用類型的數(shù)組排序
我們舉個(gè)例子，對(duì)User類型的數(shù)組，根據(jù)年齡進(jìn)行排序，此處用到Comparator接口，更多關(guān)于Comparator的介紹，請(qǐng)點(diǎn)擊。
新建一個(gè)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;
}
}
再建一個(gè)排序類：
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();
}
}
測(cè)試：
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
這就是一個(gè)簡(jiǎn)單的對(duì)引用類型的數(shù)組排序的例子，在JDK1.8中，對(duì)引用類型的排序，采用的歸并排序的算法。
在JDK1.8中，對(duì)于排序方法，還引入了parallelSort()，每個(gè)sort()都有對(duì)應(yīng)的并行排序方法，當(dāng)數(shù)組元素個(gè)數(shù)大于2的13次（8196）后采用parallelSort()。
搜索
在用二分搜索對(duì)一個(gè)已經(jīng)有序的數(shù)組進(jìn)行查找，如果存在，返回key在該數(shù)組中的位置，如果不存在，返回負(fù)數(shù)，值為：-插入點(diǎn)-1，舉個(gè)例子：
假設(shè)一個(gè)排好序的數(shù)組是：1,6,8,10,12，如果key為7，則返回值為-3，因?yàn)?應(yīng)該插入到6,8之間，所以插入點(diǎn)為2（下標(biāo)從0開始），所以返回值為-2-1=-3。
ArrayToList
這方面，是將一個(gè)數(shù)組，轉(zhuǎn)換成一個(gè)list形式，注意：通常情況下，如果該數(shù)組是int型的，如int[[ data，這種情況會(huì)出現(xiàn)并不是直接將該數(shù)組中的所有元素轉(zhuǎn)成新的list的所有元素，而是將整個(gè)數(shù)組，轉(zhuǎn)成list的一個(gè)元素，這是一種特殊情況，將類型int改成Integer就可以避免了。此處感謝網(wǎng)友@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);
}
根據(jù)注釋得知，返回的新list是個(gè)定長(zhǎng)的list，而且并不可以就行添加或者刪除元素，否則報(bào)：java.lang.UnsupportedOperationException異常。這是為什么？因?yàn)榇颂幍腁rrayList并非我們常用的java.util.ArrayList類，而是Arrays類的一個(gè)內(nèi)部類，因?yàn)槔^承了AbstractList，所有可以和list相互轉(zhuǎn)換，但是不具備add和remove等操作。
CopyOf
Arrays.copyOf()用來進(jìn)行數(shù)組的復(fù)制，返回一個(gè)全新的數(shù)組，可以傳入一個(gè)參數(shù)來定義新數(shù)組的大小，如果傳入的數(shù)小于原來的數(shù)組長(zhǎng)度，則直接把原數(shù)組多余的部分剪掉，如果傳入的值大于原數(shù)組，則新數(shù)組多余的部分補(bǔ)默認(rèn)值（對(duì)于int類型的，補(bǔ)0）。
轉(zhuǎn)載于:https://blog.51cto.com/14226273/2364862
總結(jié)
以上是生活随笔為你收集整理的Arrays类及其方法分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 数据仓库之电商数仓-- 4、可视化报表S
- 下一篇： 大学的那些事