如题java.util.Arrays.sort(int[] a)
数组形参传递为啥能修改原始数组的内容?
[public static void sort(int[] a)](http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(int[]))
Sorts the specified array into ascending numerical order.
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.
Parameters:a - the array to be sorted
迷茫2017-04-18 09:08:24
1、對於int[] a,變數a是一個物件引用,可以理解為保存陣列物件在堆中的位址(陣列中的具體元素都保存在堆中);
2、sort()中傳入變數a的引用值,也就是1中說的陣列在堆內的位址值,利用a的值,當然可以存取到在堆內的陣列,進而程式可以修改陣列內元素的值和順序了。
高洛峰2017-04-18 09:08:24
回答你的問題,你去看源碼,它用了DualPivotQuicksort.sort()的一個方法,你點進去這個方法:
static void sort(int[] a, int left, int right, int[] work, int workBase, int workLen)
其中這個int[]work臨時數組,就是在排序過程中提供資料存放的,排序完,一定會更改原數組int[]a 的內容。
此外,關於Arrays.sort()的方法,有以下說明:
1.Java Arrays中提供了所有類型的排序。其中主要分為8種基本資料型態和Object兩大類。
2.Java對Primitive(int,float等原型資料)陣列採用快速排序,對Object物件陣列採用歸併排序。對於物件的排序,穩定性很重要。例如成績單,一開始可能是按人員的學號順序排好了的,現在讓我們用成績排,那麼你應該保證,本來張三在李四前面,即使他們成績相同,張三不能跑到李四的後面去。而快速排序是不穩定的。物件陣列中保存的只是物件的引用,這樣多次移位並不會造成額外的開銷,但是,物件陣列對比較次數一般比較敏感,有可能物件的比較比單純數的比較開銷大得多。歸併排序在這方面比快速排序做得更好,這也是選擇它作為物件排序的一個重要原因之一。
3.排序最佳化:實現中快排和歸併都採用遞歸方式,而在遞歸的底層,也就是待排序的數組長度小於7時,直接使用冒泡排序,而不再遞歸下去。分析:長度為6的陣列冒泡排序總比較次數最多也就1+2+3+4+5+6=21次,最好情況下只有6次比較。而快排或歸併涉及到遞歸調用等的開銷,其時間效率在n較小時劣勢就凸顯了,因此這裡採用了冒泡排序,這也是對快速排序極重要的優化。
4.源碼中的快速排序,主要做了以下幾個方面的優化,當待排序的數組中的元素個數較少時,源碼中的閥值為7,採用的是插入排序。儘管插入排序的時間複雜度為0(n^2),但當陣列元素較少時,插入排序優於快速排序,因為這時快速排序的遞歸操作會影響效能。較好的選擇了劃分元(基準元素)。能夠將數組分成大致兩個相等的部分,避免最壞的情況。例如當陣列有序的情況下,選擇第一個元素作為劃分元,將使得演算法的時間複雜度達到O(n^2)。