基本類(lèi)型：采用調優(yōu)的快速排序；
對象類(lèi)型：采用改進(jìn)的歸并排序。
一、對于基本類(lèi)型源碼分析如下（以int[]為例）：
Java對Primitive（int，float等原型數據）數組采用快速排序，對Object對象數組采用歸并排序。對這一區別，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.
也就是說(shuō)，優(yōu)化的歸并排序既快速（nlog(n)）又穩定。
對于對象的排序，穩定性很重要。比如成績(jì)單，一開(kāi)始可能是按人員的學(xué)號順序排好了的，現在讓我們用成績(jì)排，那么你應該保證，本來(lái)張三在李四前面，即使他們成績(jì)相同，張三不能跑到李四的后面去。
而快速排序是不穩定的，而且最壞情況下的時(shí)間復雜度是O(n^2)。
另外，對象數組中保存的只是對象的引用，這樣多次移位并不會(huì )造成額外的開(kāi)銷(xiāo)，但是，對象數組對比較次數一般比較敏感，有可能對象的比較比單純數的比較開(kāi)銷(xiāo)大很多。歸并排序在這方面比快速排序做得更好，這也是選擇它作為對象排序的一個(gè)重要原因之一。
排序優(yōu)化：實(shí)現中快排和歸并都采用遞歸方式，而在遞歸的底層，也就是待排序的數組長(cháng)度小于7時(shí)，直接使用冒泡排序，而不再遞歸下去。
分析：長(cháng)度為6的數組冒泡排序總比較次數最多也就1+2+3+4+5+6=21次，最好情況下只有6次比較。而快排或歸并涉及到遞歸調用等的開(kāi)銷(xiāo)，其時(shí)間效率在n較小時(shí)劣勢就凸顯了，因此這里采用了冒泡排序，這也是對快速排序極重要的優(yōu)化。
源碼中的快速排序，主要做了以下幾個(gè)方面的優(yōu)化：
1）當待排序的數組中的元素個(gè)數較少時(shí)，源碼中的閥值為7，采用的是插入排序。盡管插入排序的時(shí)間復雜度為0(n^2)，但是當數組元素較少時(shí)，插入排序優(yōu)于快速排序，因為這時(shí)快速排序的遞歸操作影響性能。
2）較好的選擇了劃分元（基準元素）。能夠將數組分成大致兩個(gè)相等的部分，避免出現最壞的情況。例如當數組有序的的情況下，選擇第一個(gè)元素作為劃分元，將使得算法的時(shí)間復雜度達到O(n^2).
源碼中選擇劃分元的方法:
當數組大小為 size=7 時(shí) ，取數組中間元素作為劃分元。int n=m>>1;(此方法值得借鑒)
當數組大小 7<size<=40時(shí)，取首、中、末三個(gè)元素中間大小的元素作為劃分元。
當數組大小 size>40 時(shí) ，從待排數組中較均勻的選擇9個(gè)元素，選出一個(gè)偽中數做為劃分元。
3）根據劃分元 v ，形成不變式 v* (<v)* (>v)* v*
普通的快速排序算法，經(jīng)過(guò)一次劃分后，將劃分元排到素組較中間的位置，左邊的元素小于劃分元，右邊的元素大于劃分元，而沒(méi)有將與劃分元相等的元素放在其附近，這一點(diǎn)，在A(yíng)rrays.sort()中得到了較大的優(yōu)化。
舉例：15、93、15、41、6、15、22、7、15、20
因 7<size<=40,所以在15、6、和20 中選擇v = 15 作為劃分元。
經(jīng)過(guò)一次換分后： 15、15、7、6、41、20、22、93、15、15. 與劃分元相等的元素都移到了素組的兩邊。
接下來(lái)將與劃分元相等的元素移到數組中間來(lái)，形成：7、6、15、15、15、15、41、20、22、93.
最后遞歸對兩個(gè)區間進(jìn)行排序[7、6]和[41、20、22、93].
部分源代碼（一）如下：
1 package com.util; 2 3 public class ArraysPrimitive { 4 private ArraysPrimitive() {} 5 6 /** 7 * 對指定的 int 型數組按數字升序進(jìn)行排序。 8 */ 9 public static void sort(int[] a) { 10 sort1(a, 0, a.length); 11 } 12 13 /** 14 * 對指定 int 型數組的指定范圍按數字升序進(jìn)行排序。 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 * 當待排序的數組中的元素個(gè)數小于 7 時(shí)，采用插入排序 。 24 * 25 * 盡管插入排序的時(shí)間復雜度為O(n^2),但是當數組元素較少時(shí)， 插入排序優(yōu)于快速排序，因為這時(shí)快速排序的遞歸操作影響性能。 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 * 當待排序的數組中的元素個(gè)數大于 或等于7 時(shí)，采用快速排序 。 35 * 36 * Choose a partition element, v 37 * 選取一個(gè)劃分元，V 38 * 39 * 較好的選擇了劃分元(基準元素)。能夠將數組分成大致兩個(gè)相等的部分，避免出現最壞的情況。例如當數組有序的的情況下， 40 * 選擇第一個(gè)元素作為劃分元，將使得算法的時(shí)間復雜度達到O(n^2). 41 */ 42 // 當數組大小為size=7時(shí) ，取數組中間元素作為劃分元。 43 int m = off + (len >> 1); 44 // 當數組大小 7<size<=40時(shí)，取首、中、末 三個(gè)元素中間大小的元素作為劃分元。 45 if (len > 7) { 46 int l = off; 47 int n = off + len - 1; 48 /* 49 * 當數組大小 size>40 時(shí) ，從待排數組中較均勻的選擇9個(gè)元素， 50 * 選出一個(gè)偽中數做為劃分元。 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 3 60 } 61 62 //得到劃分元V 63 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 middle 83 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-elements 89 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 an122 * 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(" + fromIndex127 + ") > 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 //結果：6,7,15,15,15,15,20,22,41,93,13 }14 }
二、對于Object類(lèi)型源碼分析如下：
部分源代碼（二）如下：
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 src 28 */ 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 arrays 34 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 src 43 int destLow = low; 44 int destHigh = high; 45 low += off; 46 high += off; 47 /* 48 * >>>：無(wú)符號右移運算符 49 * expression1 >>> expresion2：expression1的各個(gè)位向右移expression2 50 * 指定的位數。右移后左邊空出的位數用0來(lái)填充。移出右邊的位被丟棄。 51 * 例如：-14>>>2； 結果為：1073741820 52 */ 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 an 58 // 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 dest 65 for (int i = destLow, p = low, q = mid; i < destHigh; i++) { 66 if (q >= high || p < mid 67 && ((Comparable) src[p]).compareTo(src[q]) <= 0) 68 dest[i] = src[p++]; 69 else 70 dest[i] = src[q++]; 71 } 72 } 73 74 /** 75 * Check that fromIndex and toIndex are in range, and throw an appropriate 76 * 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(" + fromIndex 81 + ") > 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.018 * 1003 : 90.019 * 1004 : 95.020 * 1001 : 100.021 */22 }23 }24 class Student implements Comparable<Student>{25 private int id; //學(xué)號26 private float score; //成績(jì)27 public Student(){}28 public Student(int id,float score){29 this.id=id;30 this.score=score;31 }32 @Override33 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 類(lèi)不能被實(shí)例化。 5 private System() {} 6 //在 System 類(lèi)提供的設施中，有標準輸入、標準輸出和錯誤輸出流；對外部定義的屬性 7 //和環(huán)境變量的訪(fǎng)問(wèn)；加載文件和庫的方法；還有快速復制數組的一部分的實(shí)用方法。 8 /** 9 * src and dest都必須是同類(lèi)型或者可以進(jìn)行轉換類(lèi)型的數組．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 )建一個(gè)具有指定的組件類(lèi)型和維度的新數組。 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 }聯(lián)系客服
