《數(shù)據(jù)結(jié)構(gòu)》 (java版) 課件 8-1排序

排序是一種常用操作，其目的是將一組無序的數(shù)據(jù)調(diào)整為有序的數(shù)據(jù)。52,49,80,36,14,58,61,23,97,7514,23,36,49,52,58,61,75,80,97排序問題排序的基本概念一、內(nèi)部排序和外部排序1.內(nèi)部排序：對內(nèi)存中的數(shù)據(jù)排序。2.外部排序：對外存中的數(shù)據(jù)排序。用于串行計算機、并行計算機、量子計算機的排序算法。二、串行排序、并行排序和量子排序？？？對任意的Ri和Rj,

如果Ri=Rj,在排序之前,Ri在Rj的前面，如果在排序之后,Ri仍然排在Rj前面,則為穩(wěn)定算法，否則為不穩(wěn)定算法。三、穩(wěn)定和非穩(wěn)定算法四、排序算法的主要操作是比較和復(fù)制排序的基本概念基于比較的排序，一般的排序算法O(n2)，典型的排序算法O(nlogn)五、時間復(fù)雜度基于數(shù)據(jù)分布的，O(n)排序算法的分類插入排序交換排序選擇排序歸并排序基數(shù)排序計數(shù)排序基于比較的排序的基本思想有序序列R[0..i-1]無序序列R[i..n]有序序列R[0..i]無序序列R[i+1..n]基于插入的排序有序序列R[0..i-1]無序序列R[i..n]有序序列R[0..i]無序序列R[i+1..n]初始時，有序序列為R[0]3865977613274901234567直接插入排序(straightinsertionsort)30第1趟：3849i659776132701234567直接插入排序(straightinsertionsort)30第2趟：3849i659776132701234567直接插入排序(straightinsertionsort)30第3趟：3849i659776132701234567直接插入排序(straightinsertionsort)30第4趟：38499776i65132701234567直接插入排序(straightinsertionsort)30i第5趟：3849977613131313384965971376

public

static<T>T[]insertSort(T[]a){

for(int

i=1;i<a.length;i++){ Te=a[i];

int

j=i-1;

for(;j>=0&&((Comparable<T>)e).compareTo(a[j])<0;j--)

a[j+1]=a[j];

a[j+1]=e; }

return

a; }直接插入排序3865977613274901234567直接插入排序(straightinsertionsort)哨兵：386597761327490123456738直接插入排序使用哨兵的示意性代碼：

public

static<T>T[]insertSortSentinel(Ta[]){

for(int

i=2,j;i<a.length;i++){

a[0]=a[j=i];

while(((Comparable<T>)a[0]).compareTo(a[--j])<0)

a[j+1]=a[j];

a[j+1]=a[0]; }

return

a; }256576971327120123456730直接插入排序成對插入，大掩護小，例如，一次插入13和27直接插入排序分析直接排序的空間復(fù)雜度：O(1)直接排序的時間復(fù)雜度與數(shù)據(jù)的分布有關(guān)：正序，每趟比較1次，移動2次；n-1趟：比較：n-1移動:2(n-1)逆序，第i趟比較i次，移動i+2次；n-1趟:比較：(1+2+3+...+n-1)=移動：+2(n-1)隨機分布：O(n2)穩(wěn)定排序插入排序-希爾排序D.L.Shell在1959年提出，又稱為縮小增量排序。基本思想：“跳躍式”的插入排序，在數(shù)據(jù)基本有序時，可以減少比較和復(fù)制的次數(shù)。希爾排序的基本思想4532121354345212345112345543211235412345希爾排序：先增量3，再增量1直接插入排序：1次移動1個位置，慢慢向最終的位置靠攏54321將數(shù)據(jù)序列分成若干子序列，分別對每個子序列進行插入排序。例如：將n個數(shù)據(jù)分成d個子序列：1:R[0]，R[0+d]，R[0+2d]，…，R[0+kd]2:R[1]，R[1+d]，R[1+2d]，…，R[1+kd]…d:R[d-1]，R[d-1+d]，R[d-1+2d]，…,R[d-1+kd]其中，d稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為1。希爾排序的基本思想d=501234567896597761327495544938第1趟4955449386597761327希爾排序0123456789d=3第2趟49554493865977613274938274955659776134希爾排序01234567890123456789d=1第3趟49382749556597761342738494955659776413希爾排序01234567890123456789希爾排序

public

static<T>T[]shellSort(T[]a){

int

d=a.length;

while((d>>>=1)>=1)//d=d/2 shellSort(a,d);

return

a; }

@SuppressWarnings("unchecked")

private

static<T>voidshellSort(T[]a,int

d){

for(int

i=d;i<a.length;++i){ Te=a[i];

int

j=i-d;

for(;j>=0&&((Comparable<T>)e).compareTo(a[j])<0;j-=d)

a[j+d]=a[j];

a[j+d]=e; } }1、增量序列影響算法性能。2、增量序列可以有各種取法，但最后的增量必須是1。3、常用的增量序列：a、Shell:n/2,n/4,…,1b、Hibbard:hi=2i-1c、Knuth:hi=(3i-1)/2希爾排序性能分析非穩(wěn)定算法，最好情況的復(fù)雜度是nlogn，最壞情況的復(fù)雜度與增量有關(guān)。Shell:O(n2)Hibbard:O(n3/2)用希爾排序?qū)?shù)組{98，36，47，23，1，8，10，7}進行排序，給出的增量依次是4，2，1，則排序需

趟，寫出第一趟結(jié)束后，數(shù)組中數(shù)據(jù)的排列次序課堂練習(xí)基于交換的排序初始時，有序序列為空有序序列R[0…i-1]無序序列R[i…n]min(R[i...n])有序序列R[0…i]無序序列R[i+1…n]基于交換的排序初始時，有序序列為空有序序列R[i...n]無序序列R[1...i-1]有序序列R[i-1...n]無序序列R[1...i-2]max(R[1...i-1])直接交換排序（冒泡排序）30650123456749第1趟冒泡排序過程：3897761327jj-1jj-1jj-1jj-113769713131313jj-1jj-16538jj-149冒泡排序的結(jié)束條件:沒有“交換數(shù)據(jù)”。冒泡排序

public

static<T>T[]bubbleSort1(T[]a){

for(int

i=0;i<a.length-1;++i){//每趟最小的數(shù)據(jù)的位置

boolean

flag=true;//是否是沒有數(shù)據(jù)交換

for(int

j=a.length-1;j>i;--j){//通過交換找到[0,i]最小的數(shù)據(jù)

if(((Comparable<T>)a[j]).compareTo(a[j-1])<0){ Tt=a[j];

a[j]=a[j-1];

a[j-1]=t;

flag=false; } }

if(flag)

break; }

return

a; }冒泡排序

public

static<T>T[]bubbleSort(T[]a){

int

left=0;

while(left!=a.length-1){

int

t=0;

for(int

j=a.length-1;j>left;--j){

if(((Comparable<T>)a[j]).compareTo(a[j-1])<0){ Te=a[j];

a[j]=a[j-1];

a[j-1]=e;

t=j; } }

if(t==0)//沒有變化

break;

left=t;//有序序列的右界 }

return

a; }效率更高的：快速排序快速排序是C.A.R.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。對無序的數(shù)據(jù)序列進行“劃分”，之后分別對所得的兩個子序列“遞歸”進行快速排序?；舅枷?4365258614923978075012345678952樞軸快速排序快速排序劃分p≤p>p?lrij

partIpartIIpartIIIa[l…i)a(j…r]a[i…j]a[i]≤p:i++，否則停止a[j]>p:j--，否則停止交換a[i]，a[j]，然后i++，j--重復(fù)以下步驟，直到第2部分為空，即i>j交換a[l]和a[j]劃分80361458614952972375ij80361458614952972375ij23361458614952978075ij23365258614914978075ij23361458614952978075ij80361458614952972375pivot=52lowhighhigh23lowlow80highhigh14lowlow52highhigh劃分課堂練習(xí)386597761327490123456738654976132797012345673865977649271301234567303030選下標(biāo)0的數(shù)組元素做樞軸劃分p≤p?>plrij

partIpartIIpartIIIa[l…i]a[j…r-1]a[i+1…j-1]a[j]≤p:交換a[i+1]和a[j]，然后i++,j++a[j]>p:j++重復(fù)以下操作，直到第3部分為空，即j==r劃分80361458614952972352ij80361458614952972352ijlr80361458614952972352ij80361458614952972352ij劃分80361458614952972352ij36801458614952972352ij36148058614952972352ij36148058614952972352ij劃分36148058614952972352ij36142358614952978052ij劃分樞軸三者者選一：

a0≤p≤a1a[l+1…i-1]a[j…r-2]a[i…j]a[i]≤p:i++，否則停止a[j]>p:j--，否則停止交換a[i]，a[j]，然后i++，j--重復(fù)以下步驟，直到第2部分為空，即i>j交換a[i]和a[r-1]lrijpartIpartIIIa0≤p?≥ppa1partII劃分2758751261908170897765653426154509612677503703ijb)設(shè)置哨兵、初始化2758751261908170897765653426154509612677503703ijc)移動2758715461908170897765653426512509612677503703ijd)交換5038751261908170897275653426154509612677765703a)選樞軸lr劃分2758715461908170897765653426512509612677503703ije)移動2758715461426170897765653908512509612677503703ijf)交換2758715461426170897765653908512509612677503703ijg)移動2758715461426170503765653908512509612677897703h)就位快速排序代碼

public

static<T>T[]quickSort(T[]a){ quickSort(a,0,a.length-1);

return

a; }

@SuppressWarnings("unchecked")

private

static<T>voidquickSort(T[]a,int

l,int

r){

if(r-l+1<3){

if(((Comparable<T>)a[l]).compareTo(a[r])>0){ swapElement(a,l,r); }

return; }

int

m=partition(a,l,r); quickSort(a,l,m-1); quickSort(a,m+1,r); }快速排序代碼

private

static<T>intpartition(T[]a,int

l,int

r){

int

m=selectMiddle(a,l,r); swapElement(a,m,r-1); Tpivot=a[r-1];

int

i=l;

int

j=r-1;

for(;;){

while(((Comparable<T>)a[++i]).compareTo(pivot)<0) ;

while(((Comparable<T>)pivot).compareTo(a[--j])<0) ;

if(i>=j)

break; swapElement(a,i,j); } swapElement(a,i,r-1);

return

i; }快速排序-性能分析最壞時間復(fù)雜度O(n2)，最好和平均時間復(fù)雜度O(nlogn)。快速排序需要的輔助存儲空間為：pivot棧，如果每次先對短的區(qū)間進行快速排序，則2log2n快速排序是一種不穩(wěn)定的排序方法。雙樞軸劃分/wp-content/uploads/2009/09/DualPivotQuicksort.pdflrijpartIpartIIIp1<p1p1≤&≤p2?>p2p2partIIpartIVka[l+1…i-1]是第一區(qū)域，a[i…k-1]是第二區(qū)域，a[j+1…r-1]是第三區(qū)域，a[k…j]是第四區(qū)域雙樞軸劃分雙樞軸快速排序選擇兩個樞軸p1、p2，并且p1≤p2。雙樞軸快速排序的劃分過程將數(shù)組a分為4個區(qū)域：第一個區(qū)域的數(shù)據(jù)小于樞軸p1第二個區(qū)域的數(shù)據(jù)處于p1和p2之間第三個區(qū)域的數(shù)據(jù)待定第四個區(qū)域的數(shù)據(jù)大于樞軸p2雙樞軸劃分(1)

若a[k]<p1，交換a[k]和a[i]，i=i+1，轉(zhuǎn)(3)(2)

若a[k]>p2，則a)

j=j-1，直至不滿足條件k<j&&a[j]>p2b)

交換a[k]和a[j]，

j=j-1c)

若a[k]<p1，交換a[k]和a[i]，i=i+1(3)

k=k+1，若k≤j，則轉(zhuǎn)(1)(4)

交換a[l]和a[i-1]，交換a[r]和a[j+1]，結(jié)束雙樞軸劃分5038751261908170897275653426154509612677765703lra)lrikj2758751261908170897503653426154509612703765677b)lrikj2758751261908170897503653426154509612703765677d)lrikj2758761512908170897503653426154509612703765677e)lrikj2758761512908170897503653426154509612703765677f)lrikj2758751261908170897503653426154509612703765677c)lrikj1548761170275512509503653426612677908703765897l)雙樞軸劃分lrikj2758761512612170897503653426154509908703765677g)lrikj2758761170612512897503653426154509908703765677h)lrikj2758761170612512509503653426154897908703765677i)lrikj2758761170612512509503653426154897908703765677j)lrikj2758761170154512509503653426612897908703765677k)lrikj1548761170275512509503653426612677908703765897l)雙樞軸劃分999999999999999lrija)999999999999999lrijb)無序序列R[i+1...n]初始時，有序序列為空有序序列R[0…i-1]無序序列R[i...n]有序序列R[0…i]基于選擇的排序min(R[i...n])49136597761327380123456kjkjjjjkj49第1趟：選擇最小的，放在位置0i直接選擇排序13659776492738kjjjjjk2738i第2趟：選擇最小的，放在位置1直接選擇排序0123456136597764938第3趟：j2765kjjj38k136597764965第4趟：27389749iik直接選擇排序012345601234561397769765第5趟：27384976651397769776第6趟：27384976659713977697排序結(jié)果：2738497665ii直接選擇排序97012345601234560123456直接選擇排序代碼

public

static<T>T[]selectMinSort(T[]a){

for(int

i=0;i<a.length-1;++i){//找到最小的，交換到位置i

int

k=i;//最小數(shù)據(jù)的下標(biāo)

for(int

j=i+1;j<=a.length-1;++j){//在[i,n]區(qū)間找最小的數(shù)據(jù)

if(((Comparable<T>)a[k]).compareTo(a[j])>0)

k=j; } Tt=a[i];

a[i]=a[k];

a[k]=t; }

return

a; }直接選擇排序與數(shù)據(jù)分布無關(guān)：每次選擇最小值，必須與范圍內(nèi)的所有數(shù)據(jù)進行比較；每趟選擇一個最小值，必須n-1趟。12345678910最好、最壞、平均時間復(fù)雜度都是O(n2)如果通過交換，將最小值放入最終的位置，則直接選擇排序是不穩(wěn)定的算法。樹形選擇排序-競賽樹直接選擇排序選取一個最小值后，再選擇下一個最小值就可以利用上次的比較結(jié)果：49386597761327選13時，38與65、97、76比較過，最后輸給了13；選出13后，再選下一個最小值時，38只需要和49比較，再和27比較勝者樹-擴展的完全二叉樹5565491214560123結(jié)點記錄了獲勝者的編號。第一輪的失敗者(49,97,76)換人后，只需要重賽參與的比賽，就可以得到新冠軍。386597761327敗者樹結(jié)點中記錄失敗者的編號。0號元素存放冠軍012344433019160112冠軍被替換成別的選手，重新組織比賽比勝者樹簡單。替換者和比賽的失敗者重賽。樹形選擇排序-二叉堆競賽樹中，葉子結(jié)點存儲待排序的數(shù)據(jù)，非葉子結(jié)點是為了使用樹結(jié)構(gòu)，而增加的存儲空間。二叉堆對此進行了改進：非葉子結(jié)點不再保存獲勝者的編號，而是保存數(shù)據(jù)（49，38，65，97，76，13，27）13382797766549上半?yún)^(qū)下半?yún)^(qū)例如，2-路歸并排序：有序序列S有

序

序

列T歸并m路歸并：將m個有序序列(run)，合并為一個有序序列。有序序列R歸并38496513277697132738kji比較i和j所指的數(shù)據(jù)，將小的數(shù)據(jù)復(fù)制到位置k。歸并代碼

private

static<T>voidtwoWayMerge(T[]a,T[]b,int

lo,int

m,int

hi,int

t){

int

q=m+1;

while(lo<=m&&q<=hi){

if(((Comparable<T>)a[lo]).compareTo(a[q])<0)

b[t++]=a[lo++];

else

b[t++]=a[q++]; }

if(lo<=m) System.arraycopy(a,lo,b,t,m-lo+1);

if(q<=hi) System.arraycopy(a,q,b,t,hi-q+1); }歸并排序?qū)⒋判虻臄?shù)據(jù)劃分成若干個有序的序列，再進行歸并。直接插入排序是歸并排序的特例某種意義上，直接交換排序和直接選擇排序也是歸并排序的特例如何劃分？[52][23][80][36][68][14][19][41][2352][3680][1468][1941]初始有序長度=1有序長度=2有序長度=4[23365280][14194168][1419233641526880]直接歸并排序直接歸并排序代碼

public

static<T>T[]mergeSort(T[]a){

@SuppressWarnings("unchecked") T[]b=(T[])Array.newInstance(a.getClass().getComponentType(),a.length);

//合并的長度從1開始，逐次加倍

for(int

length=1;length<a.length;length<<=1){

int

t=0;

int

lo=0;//待合并的第1部分的開始位置

while(lo<a.length){

int

m=lo+length-1;//待合并的第1部分的結(jié)束位置

if(m>=a.length){//需要合并的只有1部分 System.arraycopy(a,lo,b,t,a.length-lo);

break; }

int

hi=m+length;//待合并的第2部分的結(jié)束位置

if(hi>=a.length)

hi=a.length-1;//需要合并的第2部分比length短 twoWayMerge(a,b,lo,m,hi,t);

t+=hi-lo+1;

lo=hi+1; }

//交換2個數(shù)組 T[]tmp=a;

a=b;

b=tmp; }

return

a; }自然歸并排序[52][2380][3668][141941]利用數(shù)據(jù)中已經(jīng)存在的次序，可以減少初始的run數(shù)；數(shù)據(jù)隨機分布時，初始的run數(shù)為n/2。5223803668141941自然歸并排序如果數(shù)據(jù)正序，自然歸并排序初始時就只有1個run。[1419233641526880]如果數(shù)據(jù)逆序，采用前后交替產(chǎn)生run的方法，自然歸并排序初始時就只有2個run。[80][68524136231914]自然歸并排序需要付出檢測run的開銷自然歸并排序[52][2380][3668][141941]前后交替產(chǎn)生run，交替存放歸并結(jié)果5223803668141941[14194152][23366880][1419233641526880]遞歸的歸并排序52,23,80,36,68,14[52,23,80][36,68,14][52,23][80][52][23,52][

23,52,80][36,68][14][36][68][36,68][14,36,68][14,23,36,52,68,80][23]遞歸的歸并排序代碼

public

static<T>T[]rMergeSort(T[]a){

@SuppressWarnings("unchecked") T[]b=(T[])Array.newInstance(a.getClass().getComponentType(),a.length); rMergeSort(a,b,0,a.length-1);

return

a; }

private

static<T>voidrMergeSort(T[]a,T[]b,int

lo,int

hi){

if(lo==hi)

return;

int

m=(lo+hi)>>>1; rMergeSort(a,b,lo,m); rMergeSort(a,b,m+1,hi); twoWayMerge(a,b,lo,m,hi,lo); System.arraycopy(b,lo,a,lo,hi-lo+1); }效率比較低歸并排序算法性能分析對n

個數(shù)據(jù)進行2-路歸并排序的時間復(fù)雜度為Ο(nlogn)。每一趟歸并的時間復(fù)雜度為O(n)，總共需進行?log2n?

趟。需要的輔助存儲空間為O(n)穩(wěn)定的排序sortingbydistribution§?<¨?<??<a?撲克牌排序規(guī)則：2<3<4<5<6<7<8<9<10<J<Q<K<A撲克牌排序結(jié)果：2§?<...<A§?<2¨?<...A¨?<2??<?A??<2a?<?<Aa?如何排序？如果已知待排序數(shù)據(jù)的某些分布特征，可以采用與前面不同的排序方法計數(shù)制十六進制數(shù)符：0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F基數(shù)：16位權(quán)：從右往左，第0位，第1位，...，第n位，第i位的權(quán)重為16i

A121?10×163+1×162+2×161+1×160=323169計數(shù)制abcd=?如果建立以下的數(shù)制：基數(shù)：26位權(quán):26i

數(shù)符:a、b、c、...、z0、1、2、...、25abcd=0×263+1×262+2×261+3×260=731字符串即數(shù)，數(shù)即字符串。字符串比較大小，就是對應(yīng)的數(shù)比較大?。簭牡臀粩?shù)字(LeastSignificantDigit)到高位數(shù)字(MostSignificantDigit)逐位比較?；鶖?shù)排序-radixsort如果數(shù)據(jù)可以視為M進制數(shù)，即數(shù)據(jù)表示為p-元組：<a1，a2，...，ap>，0≤ai<M基數(shù)排序算法：分配收集對下列這組十進制數(shù)據(jù)排序:209,386,768,185,247,606,230,834,5391、按個位數(shù)的取值，分配成10組，然后按從0至9的順序?qū)⑺鼈兪占谝黄穑夯鶖?shù)排序初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008t[0]t[1]t[2]t[3]t[4]t[5]t[6]t[7]t[8]t[9]h[0]h[1]h[2]h[3]h[4]h[5]h[6]h[7]h[8]h[9]930063083184505278008109589269一趟收集基數(shù)排序一趟分配基數(shù)排序2、按十位數(shù)的取值，分配成10組，然后按從0至9的順序?qū)⑺鼈兪占谝黄穑?30063083184505278008109589269083184589063505269930t[0]t[1]t[2]t[3]t[4]t[5]t[6]t[7]t[8]t[9]h[0]h[1]h[2]h[3]h[4]h[5]h[6]h[7]h[8]h[9]008109278505008109930063269278083184589二趟收集基數(shù)排序二趟分配3、按百位數(shù)的取值，分配成10組，然后按從0至9的順序?qū)⑺鼈兪占谝黄穑夯鶖?shù)排序008063083109184269278505589930三趟收集109008184930t[0]t[1]t[2]t[3]t[4]t[5]t[6]t[7]t[8]t[9]h[0]h[1]h[2]h[3]h[4]h[5]h[6]h[7]h[8]h[9]063083269278505589505008109930063269278083184589基數(shù)排序三趟分配基數(shù)排序的時間復(fù)雜度為O(p(n+m))n：數(shù)據(jù)個數(shù)；m：基數(shù)；p：位數(shù)基數(shù)排序是穩(wěn)定的排序方法基數(shù)排序的基數(shù)可以任意選定，對十進制的數(shù)排序未必選10為基數(shù)基數(shù)排序如果n個十進制數(shù)，最大的數(shù)為1060，則取p=?m=?如果取“個位”、“十位”、“百位”、...?計數(shù)排序-countingsort試卷的分數(shù)值為0、1、2、3、...、99、100，如何對n份試卷按分值從小到大排序？在Knuth教授的著作中稱為Distributioncounting計數(shù)排序-countingsort假設(shè)數(shù)據(jù)R0、R1、...、Rn的數(shù)據(jù)有m個不同值[0,m)，設(shè)置輔助數(shù)組count[M]1、初始化count[i]=0;0≤i<m2、遍歷數(shù)據(jù)，對每個Ri，令count[Ki]++3、count[i]=count[i]+count[i-1]1≤i<m4、設(shè)置輸出區(qū)S5、遍歷數(shù)據(jù)，對每個Ri，將其復(fù)制到S[count[Ki]]，令count[Ki]--計數(shù)排序-countingsort3412203214053223321count012345對數(shù)據(jù)排序：247101213count012345第2步后的結(jié)果第3步后的結(jié)果計數(shù)排序-countingsort341220321405313591113count0123450122340123456789101112247101213count0123453、4、1、2、2、0輸出后：外部排序-externalsorting數(shù)據(jù)一般存儲在文件中，排序算法的步驟：劃分：將數(shù)據(jù)劃分成若干部分，每部分能容納于內(nèi)存，使用內(nèi)部排序算法排序，形成若干個run，寫到文件中。歸并：采用多趟多路歸并，形成最終的有序文件。外部排序-劃分5674031runrun2efghabcdfile......0m00000000外部排序-歸并輸出最小值后，讀入冠軍所在run的下一條數(shù)據(jù)，代替冠軍，重新比賽。5674031runrunrunrunrunrunrunrun2efghabcd總結(jié)每個算法都有其適用的條件直接交換排序、直接選擇排序和直接插入排序相比，沒有優(yōu)勢算法采用的數(shù)據(jù)結(jié)構(gòu)有：數(shù)組、鏈表和二叉樹(數(shù)組)。采用二叉樹適用于不斷變化的數(shù)據(jù)集。工程上使用的排序算法經(jīng)過了精心的優(yōu)化。java類庫的Arrays.sort調(diào)用了DualPivotQuicksort.sort，該算法是雙樞軸快速排序、歸并排序、插入(simple、pin和pair)排序的組合體。DualPivotQuicksort的比較操作的次數(shù)多于Quicksort，但復(fù)制操作的次數(shù)小于Quicksort。因為內(nèi)存的速度低于CPU，所以，DualPivotQuicksort更快。

static

voidsort(int[]a,int

left,int

right,

int[]work,int

workBase,int

workLen){

//UseQuicksortonsmallarrays

if(right-left<QUICKSORT_THRESHOLD){//286sort(a,left,right,true);//直接插入和快速排序，見下頁

return;}.....//歸并排序

public

static

voidsort(int[]a){//Arrays.sortDualPivotQuicksort.sort(a,0,a.length-1,null,0,0);}DualPivotQuicksort.sort

private

static

voidsort(int[]a,int

left,int

right,boolean

leftmost){

int

length=right-left+1;

//Useinsertionsortontinyarrays

if(length<INSERTION_SORT_THRESHOLD){//47

if(leftmost){

/**Traditional(withoutsentinel)insertionsort,*optimizedforserverVM,isusedincaseof*theleftmostpart.*/

for(int

i=left,j=i;i<right;j=++i){

int

ai=a[i+1];

while(ai<a[j]){

a[j+1]=a[j];

if(j--==left){

break;}}

a[j+1]=ai;}}else{DualPivotQuicksort.sort}else{

/**Skipthelongestascendingsequence.*/

do{

if(left>=right){

return;}}while(a[++left]>=a[left-1]);

/**Everyelementfromadjoiningpartplaystherole*ofsentinel,thereforethisallowsustoavoidthe*leftrangecheckoneachiteration.Moreover,weuse*themoreoptimizedalgorithm,socalledpairinsertion*sort,whichisfaster(inthecontextofQuicksort)*thantraditionalimplementationofinsertionsort.*/DualPivotQuicksort.sort直接插入排序

for(int

k=left;++left<=right;k=++left){

int

a1=a[k],a2=a[left];

if(a1<a2){

a2=a1;a1=a[left];}

while(a1<a[--k]){

a[k+2]=a[k];}

a[++k+1]=a1;

while(a2<a[--k]){

a[k+1]=a[k];}

a[k+1]=a2;}

int

last=a[right];

while(last<a[--right]){

a[right+1]=a[right];}

a[right+1]=last;}

return;}作業(yè)實現(xiàn)鏈?zhǔn)交鶖?shù)排序，可以對任意的一組javaint類型的整數(shù)(正、負、零)進行排序。要求：給出類代碼和運行結(jié)果的截圖。提示：1、不需要功能完備的鏈表，只需要鏈表有2個引用變量，引用第1個結(jié)點和最后1個結(jié)點，具有向尾插入結(jié)點以及將2個鏈表首尾相連，合并成1個鏈表的功能。2、如果使用%，被除數(shù)為正數(shù)的余數(shù)為正數(shù)被除數(shù)為負數(shù)的余數(shù)為負數(shù)基于插入的排序有序序列R[0..i-1]無序序列R[i..n]有序序列R[0..i]無序序列R[i+1..n]初始時，有序序列為R[0]38659776132749012345673865977613274901234567初始:i=1:49384965977613273801234567i=2:493865直接插入排序(straightinsertionsort)49659776132738012345674965977613273801234567i=3:493865974965977613273801234567i=4:7697直接插入排序4965769713273801234567496576971327380123456713i=5:493865769713384965769727130123456