2.2.22三向歸并排序。假設(shè)每次我們是把數(shù)組分成三個(gè)部分而不是兩個(gè)部分并將它們分別排序，然后進(jìn)行三向歸并。這種算法的運(yùn)行時(shí)間的增長(zhǎng)數(shù)量級(jí)是多少？
運(yùn)算時(shí)間增長(zhǎng)數(shù)量級(jí)是O(Nlg3N)。
public class E2d2d22
{
??? public static void sort(Comparable[] a)
??? {
??????? Comparable[] aux=new Comparable[a.length];
??????? sort(a,aux,0,a.length-1);
?? }
???
??? private static void sort(Comparable[] a,Comparable[] aux,int lo,int hi)
??? {
???????? if (hi<=lo)??? return ;
????????? int m1=lo+(hi-lo)/3;
????????? int m2=m1+1+(hi-m1-1)/2;
????????? sort(a,aux,lo,m1);
????????? sort(a,aux,m1+1,m2);
????????? sort(a,aux,m2+1,hi);
????????? merge(a,aux,lo,m1,m2,hi);
??? }
???
??? private static void merge(Comparable[] a,Comparable[] aux,int lo,int m1,int m2,int hi)
??? {
????? for(int k=lo;k<=hi;k++)
????????? aux[k]=a[k];
????? //
????? int aIndex=lo;
????? int bIndex=m1+1;
????? int cIndex=m2+1;
?????
????? Comparable A,B,C;
????? Double maxValue=Double.MAX_VALUE;
????? for(int k=lo;k<=hi;k++)
????? {
?????????? if (aIndex<=m1) A=aux[aIndex]; else A=maxValue;
?????????? if (bIndex<=m2) B=aux[bIndex]; else B=maxValue;
?????????? if (cIndex<=hi)?? C=aux[cIndex]; else C=maxValue;
?????????? //
?????????? if(less(A,B) && less(A,C))
???????????? {a[k]=A;aIndex++;}
?????????? else if(less(B,A) && less(B,C))
???????????? {a[k]=B;bIndex++;}
?????????? else if(less(C,A) && less(C,B))
???????????? {a[k]=C;cIndex++;}
?????????? else
?????????????? {a[k]=A;aIndex++;}
????? }
??? }
?
??? private static boolean less(Comparable v,Comparable w)
??? { return v.compareTo(w)<0;}
???
??? private static void exch(Comparable[] a,int i,int j)
??? {
????? Comparable t=a[i];
????? a[i]=a[j];
????? a[j]=t;
??? }
??
?public static boolean isSorted(Comparable[] a)
??? {
????? for(int i=1;i<a.length;i++)
??????? if(less(a[i],a[i-1])) return false;
????? return true;
??? }
?
?public static void main(String[] args)
?? {
???? Integer N=Integer.parseInt(args[0]);
???? Comparable[] a=new Comparable[N];
???? for(int i=0;i<N;i++)
???????? a[i]=StdRandom.uniform();
????
???? sort(a);
???? StdOut.printf("%s",isSorted(a));
? }
}

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

總結(jié)

以上是生活随笔為你收集整理的Algs4-2.2.22三向归并排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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