一、Arrays.sort()數(shù)組排序

Java?Arrays中提供了對所有類型的排序。其中主要分為Primitive(8種基本類型)和Object兩大類。

　　基本類型：采用調(diào)優(yōu)的快速排序；

　　對象類型：采用改進的歸并排序。

?

1、對于基本類型源碼分析如下（以int[]為例）：

　　Java對Primitive（int，float等原型數(shù)據(jù)）數(shù)組采用快速排序，對Object對象數(shù)組采用歸并排序。對這一區(qū)別，sun在<<The?Java?Tutorial>>中做出的解釋如下：

　　The?sort?operation?uses?a?slightly?optimized?merge?sort?algorithm?that?is?fast?and?stable:

　　*?Fast:?It?is?guaranteed?to?run?in?n?log(n)?time?and?runs?substantially?faster?on?nearly?sorted?lists.?Empirical?tests?showed?it?to?be?as?fast?as?a?highly?optimized?quicksort.?A?quicksort?is?generally?considered?to?be?faster?than?a?merge?sort?but?isn't?stable?and?doesn't?guarantee?n?log(n)?performance.

　　*?Stable:?It?doesn't?reorder?equal?elements.?This?is?important?if?you?sort?the?same?list?repeatedly?on?different?attributes.?If?a?user?of?a?mail?program?sorts?the?inbox?by?mailing?date?and?then?sorts?it?by?sender,?the?user?naturally?expects?that?the?now-contiguous?list?of?messages?from?a?given?sender?will?(still)?be?sorted?by?mailing?date.?This?is?guaranteed?only?if?the?second?sort?was?stable.

　　也就是說，優(yōu)化的歸并排序既快速（nlog(n)）又穩(wěn)定。

　　對于對象的排序，穩(wěn)定性很重要。比如成績單，一開始可能是按人員的學號順序排好了的，現(xiàn)在讓我們用成績排，那么你應(yīng)該保證，本來張三在李四前面，即使他們成績相同，張三不能跑到李四的后面去。

　　而快速排序是不穩(wěn)定的，而且最壞情況下的時間復雜度是O(n^2)。

　　另外，對象數(shù)組中保存的只是對象的引用，這樣多次移位并不會造成額外的開銷，但是，對象數(shù)組對比較次數(shù)一般比較敏感，有可能對象的比較比單純數(shù)的比較開銷大很多。歸并排序在這方面比快速排序做得更好，這也是選擇它作為對象排序的一個重要原因之一。

　　排序優(yōu)化：實現(xiàn)中快排和歸并都采用遞歸方式，而在遞歸的底層，也就是待排序的數(shù)組長度小于7時，直接使用冒泡排序，而不再遞歸下去。

　　分析：長度為6的數(shù)組冒泡排序總比較次數(shù)最多也就1+2+3+4+5+6=21次，最好情況下只有6次比較。而快排或歸并涉及到遞歸調(diào)用等的開銷，其時間效率在n較小時劣勢就凸顯了，因此這里采用了冒泡排序，這也是對快速排序極重要的優(yōu)化。

?

　　源碼中的快速排序，主要做了以下幾個方面的優(yōu)化：

　　1）當待排序的數(shù)組中的元素個數(shù)較少時，源碼中的閥值為7，采用的是插入排序。盡管插入排序的時間復雜度為0(n^2)，但是當數(shù)組元素較少時，插入排序優(yōu)于快速排序，因為這時快速排序的遞歸操作影響性能。

　　2）較好的選擇了劃分元（基準元素）。能夠?qū)?shù)組分成大致兩個相等的部分，避免出現(xiàn)最壞的情況。例如當數(shù)組有序的的情況下，選擇第一個元素作為劃分元，將使得算法的時間復雜度達到O(n^2).

　　源碼中選擇劃分元的方法:

　　　　當數(shù)組大小為?size=7?時?，取數(shù)組中間元素作為劃分元。int?n=m>>1;(此方法值得借鑒)

　　　　當數(shù)組大小?7<size<=40時，取首、中、末三個元素中間大小的元素作為劃分元。

　　　　當數(shù)組大小?size>40?時?，從待排數(shù)組中較均勻的選擇9個元素，選出一個偽中數(shù)做為劃分元。

　　3）根據(jù)劃分元?v?，形成不變式?v*?(<v)*?(>v)*?v*

　　普通的快速排序算法，經(jīng)過一次劃分后，將劃分元排到素組較中間的位置，左邊的元素小于劃分元，右邊的元素大于劃分元，而沒有將與劃分元相等的元素放在其附近，這一點，在Arrays.sort()中得到了較大的優(yōu)化。

　　舉例：15、93、15、41、6、15、22、7、15、20

　　因??7<size<=40,所以在15、6、和20?中選擇v?=?15?作為劃分元。

　　經(jīng)過一次換分后：?15、15、7、6、41、20、22、93、15、15.?與劃分元相等的元素都移到了素組的兩邊。

　　接下來將與劃分元相等的元素移到數(shù)組中間來，形成：7、6、15、15、15、15、41、20、22、93.

　　最后遞歸對兩個區(qū)間進行排序[7、6]和[41、20、22、93].

?

　　部分源代碼（一）如下：

1 package com.util;2 3 public class ArraysPrimitive {4 private ArraysPrimitive() {}5 6 /**7 * 對指定的 int 型數(shù)組按數(shù)字升序進行排序。8 */9 public static void sort(int[] a) {10 sort1(a, 0, a.length);11 }12 13 /**14 * 對指定 int 型數(shù)組的指定范圍按數(shù)字升序進行排序。15 */16 public static void sort(int[] a, int fromIndex, int toIndex) {17 rangeCheck(a.length, fromIndex, toIndex);18 sort1(a, fromIndex, toIndex - fromIndex);19 }20 21 private static void sort1(int x[], int off, int len) {22 /*23 * 當待排序的數(shù)組中的元素個數(shù)小于 7 時，采用插入排序 。24 * 25 * 盡管插入排序的時間復雜度為O(n^2),但是當數(shù)組元素較少時， 插入排序優(yōu)于快速排序，因為這時快速排序的遞歸操作影響性能。26 */27 if (len < 7) {28 for (int i = off; i < len + off; i++)29 for (int j = i; j > off && x[j - 1] > x[j]; j--)30 swap(x, j, j - 1);31 return;32 }33 /*34 * 當待排序的數(shù)組中的元素個數(shù)大于 或等于7 時，采用快速排序 。35 * 36 * Choose a partition element, v37 * 選取一個劃分元，V38 * 39 * 較好的選擇了劃分元(基準元素)。能夠?qū)?shù)組分成大致兩個相等的部分，避免出現(xiàn)最壞的情況。例如當數(shù)組有序的的情況下，40 * 選擇第一個元素作為劃分元，將使得算法的時間復雜度達到O(n^2).41 */42 // 當數(shù)組大小為size=7時 ，取數(shù)組中間元素作為劃分元。43 int m = off + (len >> 1);44 // 當數(shù)組大小 7<size<=40時，取首、中、末 三個元素中間大小的元素作為劃分元。45 if (len > 7) {46 int l = off;47 int n = off + len - 1;48 /*49 * 當數(shù)組大小 size>40 時 ，從待排數(shù)組中較均勻的選擇9個元素，50 * 選出一個偽中數(shù)做為劃分元。51 */52 if (len > 40) {53 int s = len / 8;54 l = med3(x, l, l + s, l + 2 * s);55 m = med3(x, m - s, m, m + s);56 n = med3(x, n - 2 * s, n - s, n);57 }58 // 取出中間大小的元素的位置。59 m = med3(x, l, m, n); // Mid-size, med of 360 }61 62 //得到劃分元V63 int v = x[m];64 65 // Establish Invariant: v* (<v)* (>v)* v*66 int a = off, b = a, c = off + len - 1, d = c;67 while (true) {68 while (b <= c && x[b] <= v) {69 if (x[b] == v)70 swap(x, a++, b);71 b++;72 }73 while (c >= b && x[c] >= v) {74 if (x[c] == v)75 swap(x, c, d--);76 c--;77 }78 if (b > c)79 break;80 swap(x, b++, c--);81 }82 // Swap partition elements back to middle83 int s, n = off + len;84 s = Math.min(a - off, b - a);85 vecswap(x, off, b - s, s);86 s = Math.min(d - c, n - d - 1);87 vecswap(x, b, n - s, s);88 // Recursively sort non-partition-elements89 if ((s = b - a) > 1)90 sort1(x, off, s);91 if ((s = d - c) > 1)92 sort1(x, n - s, s);93 }94 95 /**96 * Swaps x[a] with x[b].97 */98 private static void swap(int x[], int a, int b) {99 int t = x[a]; 100 x[a] = x[b]; 101 x[b] = t; 102 } 103 104 /** 105 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. 106 */ 107 private static void vecswap(int x[], int a, int b, int n) { 108 for (int i=0; i<n; i++, a++, b++) 109 swap(x, a, b); 110 } 111 112 /** 113 * Returns the index of the median of the three indexed integers. 114 */ 115 private static int med3(int x[], int a, int b, int c) { 116 return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a) 117 : (x[b] > x[c] ? b : x[a] > x[c] ? c : a)); 118 } 119 120 /** 121 * Check that fromIndex and toIndex are in range, and throw an 122 * appropriate exception if they aren't. 123 */ 124 private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) { 125 if (fromIndex > toIndex) 126 throw new IllegalArgumentException("fromIndex(" + fromIndex 127 + ") > toIndex(" + toIndex + ")"); 128 if (fromIndex < 0) 129 throw new ArrayIndexOutOfBoundsException(fromIndex); 130 if (toIndex > arrayLen) 131 throw new ArrayIndexOutOfBoundsException(toIndex); 132 } 133 }

測試代碼如下：

1 package com.test;2 3 import com.util.ArraysPrimitive;4 5 public class ArraysTest {6 public static void main(String[] args) {7 int [] a={15,93,15,41,6,15,22,7,15,20};8 ArraysPrimitive.sort(a);9 for(int i=0;i<a.length;i++){ 10 System.out.print(a[i]+","); 11 } 12 //結(jié)果：6,7,15,15,15,15,20,22,41,93, 13 } 14 }

2、對于Object類型源碼分析如下：

　　部分源代碼（二）如下：

1 package com.util;2 3 import java.lang.reflect.Array;4 5 public class ArraysObject {6 private static final int INSERTIONSORT_THRESHOLD = 7;7 8 private ArraysObject() {}9 10 public static void sort(Object[] a) {11 //java.lang.Object.clone()，理解深表復制和淺表復制12 Object[] aux = (Object[]) a.clone();13 mergeSort(aux, a, 0, a.length, 0);14 }15 16 public static void sort(Object[] a, int fromIndex, int toIndex) {17 rangeCheck(a.length, fromIndex, toIndex);18 Object[] aux = copyOfRange(a, fromIndex, toIndex);19 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);20 }21 22 /**23 * Src is the source array that starts at index 0 24 * Dest is the (possibly larger) array destination with a possible offset 25 * low is the index in dest to start sorting 26 * high is the end index in dest to end sorting 27 * off is the offset to generate corresponding low, high in src28 */29 private static void mergeSort(Object[] src, Object[] dest, int low,30 int high, int off) {31 int length = high - low;32 33 // Insertion sort on smallest arrays34 if (length < INSERTIONSORT_THRESHOLD) {35 for (int i = low; i < high; i++)36 for (int j = i; j > low && 37 ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--)38 swap(dest, j, j - 1);39 return;40 }41 42 // Recursively sort halves of dest into src43 int destLow = low;44 int destHigh = high;45 low += off;46 high += off;47 /*48 * >>>：無符號右移運算符49 * expression1 >>> expresion2：expression1的各個位向右移expression250 * 指定的位數(shù)。右移后左邊空出的位數(shù)用0來填充。移出右邊的位被丟棄。51 * 例如：-14>>>2； 結(jié)果為：107374182052 */53 int mid = (low + high) >>> 1;54 mergeSort(dest, src, low, mid, -off);55 mergeSort(dest, src, mid, high, -off);56 57 // If list is already sorted, just copy from src to dest. This is an58 // optimization that results in faster sorts for nearly ordered lists.59 if (((Comparable) src[mid - 1]).compareTo(src[mid]) <= 0) {60 System.arraycopy(src, low, dest, destLow, length);61 return;62 }63 64 // Merge sorted halves (now in src) into dest65 for (int i = destLow, p = low, q = mid; i < destHigh; i++) {66 if (q >= high || p < mid67 && ((Comparable) src[p]).compareTo(src[q]) <= 0)68 dest[i] = src[p++];69 else70 dest[i] = src[q++];71 }72 }73 74 /**75 * Check that fromIndex and toIndex are in range, and throw an appropriate76 * exception if they aren't.77 */78 private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {79 if (fromIndex > toIndex)80 throw new IllegalArgumentException("fromIndex(" + fromIndex81 + ") > toIndex(" + toIndex + ")");82 if (fromIndex < 0)83 throw new ArrayIndexOutOfBoundsException(fromIndex);84 if (toIndex > arrayLen)85 throw new ArrayIndexOutOfBoundsException(toIndex);86 }87 88 public static <T> T[] copyOfRange(T[] original, int from, int to) {89 return copyOfRange(original, from, to, (Class<T[]>) original.getClass());90 }91 92 public static <T, U> T[] copyOfRange(U[] original, int from, int to,93 Class<? extends T[]> newType) {94 int newLength = to - from;95 if (newLength < 0)96 throw new IllegalArgumentException(from + " > " + to);97 T[] copy = ((Object) newType == (Object) Object[].class)98 ? (T[]) new Object[newLength]99 : (T[]) Array.newInstance(newType.getComponentType(), newLength); 100 System.arraycopy(original, from, copy, 0, 101 Math.min(original.length - from, newLength)); 102 return copy; 103 } 104 105 /** 106 * Swaps x[a] with x[b]. 107 */ 108 private static void swap(Object[] x, int a, int b) { 109 Object t = x[a]; 110 x[a] = x[b]; 111 x[b] = t; 112 } 113 }

測試代碼如下：

1 package com.test;2 3 import com.util.ArraysObject;4 5 public class ArraysObjectSortTest {6 public static void main(String[] args) {7 Student stu1=new Student(1001,100.0F);8 Student stu2=new Student(1002,90.0F);9 Student stu3=new Student(1003,90.0F); 10 Student stu4=new Student(1004,95.0F); 11 Student[] stus={stu1,stu2,stu3,stu4}; 12 //Arrays.sort(stus); 13 ArraysObject.sort(stus); 14 for(int i=0;i<stus.length;i++){ 15 System.out.println(stus[i].getId()+" : "+stus[i].getScore()); 16 } 17 /* 1002 : 90.0 18 * 1003 : 90.0 19 * 1004 : 95.0 20 * 1001 : 100.0 21 */ 22 } 23 } 24 class Student implements Comparable<Student>{ 25 private int id; //學號 26 private float score; //成績 27 public Student(){} 28 public Student(int id,float score){ 29 this.id=id; 30 this.score=score; 31 } 32 @Override 33 public int compareTo(Student s) { 34 return (int)(this.score-s.getScore()); 35 } 36 public int getId() { 37 return id; 38 } 39 public void setId(int id) { 40 this.id = id; 41 } 42 public float getScore() { 43 return score; 44 } 45 public void setScore(float score) { 46 this.score = score; 47 } 48 }

輔助理解代碼：

1 package com.lang;2 3 public final class System {4 //System 類不能被實例化。 5 private System() {}6 //在 System 類提供的設(shè)施中，有標準輸入、標準輸出和錯誤輸出流；對外部定義的屬性7 //和環(huán)境變量的訪問；加載文件和庫的方法；還有快速復制數(shù)組的一部分的實用方法。8 /**9 * src and dest都必須是同類型或者可以進行轉(zhuǎn)換類型的數(shù)組． 10 * @param src the source array. 11 * @param srcPos starting position in the source array. 12 * @param dest the destination array. 13 * @param destPos starting position in the destination data. 14 * @param length the number of array elements to be copied. 15 */ 16 public static native void arraycopy(Object src, int srcPos, Object dest, 17 int destPos, int length); 18 }1 package com.lang.reflect;2 3 public final class Array {4 private Array() {}5 6 //創(chuàng)建一個具有指定的組件類型和維度的新數(shù)組。7 public static Object newInstance(Class<?> componentType, int length)8 throws NegativeArraySizeException {9 return newArray(componentType, length); 10 } 11 12 private static native Object newArray(Class componentType, int length) 13 throws NegativeArraySizeException; 14 }

二、Arrays.asList

慎用ArrayList的contains方法，使用HashSet的contains方法代替

在啟動一個應(yīng)用的時候，發(fā)現(xiàn)其中有一處數(shù)據(jù)加載要數(shù)分鐘，剛開始以為是需要load的數(shù)據(jù)比較多的緣故，查了一下數(shù)據(jù)庫有6條左右，但是單獨寫了一個數(shù)據(jù)讀取的方法，將這6萬多條全部讀過來，卻只需要不到10秒鐘，就覺得這里面肯定有問題，于是仔細看其中的邏輯，其中有一段數(shù)據(jù)去重的邏輯，就是記錄中存在某幾個字段相同的，就認為是重復數(shù)據(jù)，就需要將重復數(shù)據(jù)給過濾掉。這里就用到了一個List來存放這幾個字段所組成的主鍵，如果發(fā)現(xiàn)相同的就不處理，代碼無非就是下面這樣：

?

1 List<string> uniqueKeyList = new ArrayList<string>(); 2 //...... 3 if (uniqueKeyList.contains(uniqueKey)) { 4 continue; }

?

根據(jù)鍵去查找是不是已經(jīng)存在了，來判斷是否重復數(shù)據(jù)。經(jīng)過分析，這一塊耗費了非常多的時候，于是就去查看ArrayList的contains方法的源碼，發(fā)現(xiàn)其最終會調(diào)用他本身的indexOf方法：

?

7public int indexOf(Object elem) { 8 if (elem == null) { 9 for (int i = 0; i < size; i++) 10 if (elementData[i]==null) 11 return i; 12 } else { 13 for (int i = 0; i < size; i++) 14 if (elem.equals(elementData[i])) 15 return i; 16 } 17 return -1; 18 }

?

原來在這里他做的是遍歷整個list進行查找，最多可能對一個鍵的查找會達到6萬多次，也就是會掃描整個List，驗怪會這么慢了。

于是將原來的List替換為Set：

?

Set<string> uniqueKeySet = new HashSet<string>(); //...... if (uniqueKeySet.contains(uniqueKey)) { continue; }

?

速度一下就上去了，在去重這一塊最多花費了一秒鐘，為什么HashSet的速度一下就上去了，那是因為其內(nèi)部使用的是Hashtable，這是HashSet的contains的源碼：

?

public boolean contains(Object o) { return map.containsKey(o); }

?

關(guān)于UnsupportedOperationException異常

?????在使用Arrays.asList()后調(diào)用add，remove這些method時出現(xiàn)java.lang.UnsupportedOperationException異常。這是由于Arrays.asList()?返回java.util.Arrays$ArrayList，?而不是ArrayList。Arrays$ArrayList和ArrayList都是繼承AbstractList，remove，add等method在AbstractList中是默認throw?UnsupportedOperationException而且不作任何操作。ArrayList?override這些method來對list進行操作，但是Arrays$ArrayList沒有override?remove()，add()等，所以throw?UnsupportedOperationException。

?

轉(zhuǎn)載于:https://www.cnblogs.com/ITtangtang/p/3948765.html

總結(jié)

以上是生活随笔為你收集整理的Java集合---Arrays类源码解析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。