第Java使用Arrays.sort()方法實現(xiàn)給對象排序Integer[]a1={34,57,46,89,98,12,55,84,29};

//對數(shù)組中的第四位到第7位（不包含第七位）（左閉右開原則）進行排序

Arrays.sort(a1,3,6);

System.out.println("Arrays.sort()升序:");

for(inti=0;ia1.length;i++){

System.out.print(a1[i]+"");

運行結果如下：

結合文檔以及源代碼，我們發(fā)現(xiàn)，jdk中的Arrays.sort(）的實現(xiàn)是通過所謂的雙軸快排的算法

雙軸快排

快速排序使用的是分治思想，將原問題分成若干個子問題進行遞歸解決。選擇一個元素作為軸(pivot)，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比軸元素小，另外一部分的所有數(shù)據(jù)都比軸元素大，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。

雙軸快排(DualPivotQuicksort)，顧名思義有兩個軸元素pivot1，pivot2，且pivot≤pivot2，將序列分成三段：xpivot1、pivot1≤x≤pivot2、xpivot2，然后分別對三段進行遞歸。這個算法通常會比傳統(tǒng)的快排效率更高，也因此被作為Arrays.java中給基本類型的數(shù)據(jù)排序的具體實現(xiàn)。

下面我們以JDK1.8中Arrays對int型數(shù)組的排序為例來介紹其中使用的雙軸快排：

1.判斷數(shù)組的長度是否大于286，大于則使用歸并排序(mergesort)，否則執(zhí)行2。

//UseQuicksortonsmallarrays

if(right-leftQUICKSORT_THRESHOLD){

sort(a,left,right,true);

return;

//Mergesort

......

2.判斷數(shù)組長度是否小于47，小于則直接采用插入排序(insertionsort)，否則執(zhí)行3。

//Useinsertionsortontinyarrays

if(lengthINSERTION_SORT_THRESHOLD){

//Insertionsort

......

}

3.用公式length/8+length/64+1近似計算出數(shù)組長度的1/7。

//Inexpensiveapproximationoflength/7

intseventh=(length3)+(length6)+1;

4.取5個根據(jù)經(jīng)驗得出的等距點。

*Sortfiveevenlyspacedelementsaround(andincluding)the

*centerelementintherange.Theseelementswillbeusedfor

*pivotselectionasdescribedbelow.Thechoiceforspacing

*theseelementswasempiricallydeterminedtoworkwellon

*awidevarietyofinputs.

inte3=(left+right)//Themidpoint

inte2=e3-seventh;

inte1=e2-seventh;

inte4=e3+seventh;

inte5=e4+seventh;

5.將這5個元素進行插入排序

//Sorttheseelementsusinginsertionsort

if(a[e2]a[e1]){intt=a[e2];a[e2]=a[e1];a[e1]=t;}

if(a[e3]a[e2]){intt=a[e3];a[e3]=a[e2];a[e2]=t;

if(ta[e1]){a[e2]=a[e1];a[e1]=t;}

if(a[e4]a[e3]){intt=a[e4];a[e4]=a[e3];a[e3]=t;

if(ta[e2]){a[e3]=a[e2];a[e2]=t;

if(ta[e1]){a[e2]=a[e1];a[e1]=t;}

if(a[e5]a[e4]){intt=a[e5];a[e5]=a[e4];a[e4]=t;

if(ta[e3]){a[e4]=a[e3];a[e3]=t;

if(ta[e2]){a[e3]=a[e2];a[e2]=t;

if(ta[e1]){a[e2]=a[e1];a[e1]=t;}

}

6.選取a[e2]，a[e4]分別作為pivot1，pivot2。由于步驟5進行了排序，所以必有pivot1=pivot2。定義兩個指針less和great，less從最左邊開始向右遍歷，一直找到第一個不小于pivot1的元素，great從右邊開始向左遍歷，一直找到第一個不大于pivot2的元素。

*Usethesecondandfourthofthefivesortedelementsaspivots.

*Thesevaluesareinexpensiveapproximationsofthefirstand

*secondtercilesofthearray.Notethatpivot1=pivot2.

intpivot1=a[e2];

intpivot2=a[e4];

*Thefirstandthelastelementstobesortedaremovedtothe

*locationsformerlyoccupiedbythepivots.Whenpartitioning

*iscomplete,thepivotsareswappedbackintotheirfinal

*positions,andexcludedfromsubsequentsorting.

a[e2]=a[left];

a[e4]=a[right];

*Skipelements,whicharelessorgreaterthanpivotvalues.

while(a[++less]pivot1);

while(a[--great]pivot2);

7.接著定義指針k從less-1開始向右遍歷至great，把小于pivot1的元素移動到less左邊，大于pivot2的元素移動到great右邊。這里要注意，我們已知great處的元素小于pivot2，但是它于pivot1的大小關系，還需要進行判斷，如果比pivot1還小，需要移動到到less左邊，否則只需要交換到k處。

*Partitioning:

*leftpartcenterpartrightpart

*+--------------------------------------------------------------+

*|pivot1|pivot1==pivot2||pivot2|

*+--------------------------------------------------------------+

*^^^

*|||

*lesskgreat

*Invariants:

*allin(left,less)pivot1

*pivot1=allin[less,k)=pivot2

*allin(great,right)pivot2

*Pointerkisthefirstindexof-part.

outer:

for(intk=less-1;++k=great;){

intak=a[k];

if(akpivot1){//Movea[k]toleftpart

a[k]=a[less];

*Hereandbelowweuse"a[i]=b;i++;"instead

*of"a[i++]=b;"duetoperformanceissue.

a[less]=ak;

++less;

}elseif(akpivot2){//Movea[k]torightpart

while(a[great]pivot2){

if(great--==k){

breakouter;

if(a[great]pivot1){//a[great]=pivot2

a[k]=a[less];

a[less]=a[great];

++less;

}else{//pivot1=a[great]=pivot2

a[k]=a[great];

*Hereandbelowweuse"a[i]=b;i--;"instead

*of"a[i--]=b;"duetoperformanceissue.

a[great]=ak;

--great;

}

8.將less-1處的元素移動到隊頭，great+1處的元素移動到隊尾，并把pivot1和pivot2分別放到less-1和great+1處。

//Swappivotsintotheirfinalpositions

a[left]=a[less-1];a[less-1]=pivot1;

a[right]=a[great+1];a[great+1]=pivot2;

9.至此，less左邊的元素都小于pivot1，great右邊的元素都大于pivot2，分別對兩部分進行同樣的遞歸排序。

//Sortleftandrightpartsrecursively,excludingknownpivots

sort(a,left,less-2,leftmost);

sort(a,great+2,right,false);

10.對于中間的部分，如果大于4/7的數(shù)組長度，很可能是因為重復元素的存在，所以把less向右移動到第一個不等于pivot1的地方，把great向左移動到第一個不等于pivot2的地方，然后再對less和great之間的部分進行遞歸排序。

*Ifcenterpartistoolarge(comprises4/7ofthearray),

*swapinternalpivotvaluestoends.

if(lesse1e5great){

*Skipelements,whichareequaltopivotvalues.

while(a[less]==pivot1){

++less;

while(a[great]==pivot2){

--great;

......

//Sortcenterpartrecursively

sort(a,less,great,false);

另外參考了其他博文，算法思路如下

算法步驟

1.對于很小的數(shù)組（長度小于47），會使用插入排序。

2.選擇兩個點P1,P2作為軸心，比如我們可以使用第一個元素和最后一個元素。