java數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)

1、1 .大。表示法：粗略的量度方法即算法的速度是如何與數(shù)據(jù)項(xiàng)的個數(shù)相關(guān)的大O表示法表示的運(yùn)行O(N)O(logN)O(1)O(N)O(N)O(N)O(1)是最優(yōu)秀的,O(logN)良好，O(N)還可以,O(N2)稍差(在冒泡法中見到)2 .排序publicclassJWzw/插入排序publicvoidinsertArray(Integerin)inttem=0;intnum=0;intupnum=0;for(inti=0;i=0;j-)num+;if(inj+1inj)tem=inj+1;inj+1=inj;inj=tem;upnum+;elsebreak;for(inti=0;iin.len

2、gth;i+)System.out.print(ini);if(iin.length-1)System.out.print(,);算法時間線性查找二分查找無序數(shù)組的插入有序數(shù)組的插入無序數(shù)組的刪除有序數(shù)組的刪除/選擇排序publicvoidchooseArray(Integerin)inttem=0;intnum=0;intupnum=0;for(inti=0;iin.length;i+)for(intj=i;jin.length-1;j+)num+;if(inj+1inj)tem=inj+1;inj+1=inj;inj=tem;upnum+;)for(inti=0;iin.length;i+

3、)System.out.print(ini);if(iin.length-1)System.out.print(,);)/冒泡排序publicvoidefferArray(Integerin)inttem=0;intnum=0;intupnum=0;)System.out .println();System.out.println(插入排序循環(huán)次數(shù)：+System.out .println(移動次數(shù)：+upnum);System.out .print(nnn);)num);System.out .println();System.out .println(選擇排序循環(huán)次數(shù)：+System.ou

4、t .println(移動次數(shù)：+upnum);)System.out .print(nnn);num);for(inti=0;iin.for(intj=i;jin.(num+;if(inj+1ini)tem=inj+1;inj+1=ini;ini=tem;upnum+;System.out.print(ini);if (iin.length-1)System.out.print(,);System.out .println();System.out .println(冒泡排序循環(huán)次數(shù):+num);System.out .println(移動次數(shù)：+upnum);System.out .pri

5、nt(nnn);/打印乘法口訣publicvoidprintMulti()for(intj=1;j10;j+)for(inti=1;i=j;i+)System.out.print(i+*+j+System.out.print(tn);System.out.print(nnn);/打印N*1+N*2+N*3=num的所有組合publicvoidprintNumAssemble(intnum)for(inti=0;inum+1;i+)for(intj=0;jnum/2+1;j+)for(intin=0;innum/3+1;in+)if(i*1+j*2+in*3=num)for(inti=0;i2)

6、;3 .優(yōu)先級隊列classPriorityQueueprivatelonga=null;privateintnItems=0;privateintmaxSize=0;publicPriorityQueue(intmaxSize)a=newlongmaxSize;this.maxSize=maxSize;nItems=0;publicvoidinsert(longl)/優(yōu)先級隊列的插入不是隊尾，而是選擇一個合適的按照某種順序插入的+in);)System.out.println(小馬+i+,t中馬+j+,t大馬*/的所有組合/當(dāng)隊列長度為0時，如下/不為0時，將所有比要插入的數(shù)小的數(shù)據(jù)后移，這

7、樣大的數(shù)就在隊列的頭部了inti=0;if(nItems=0)a0=l;elsefor(i=nItems-1;i=0;i-)if(lai)ai+1=ai;elsebreak;ai+1=l;nItems+;publiclongremove()/移出的是數(shù)組最上端的數(shù)，這樣減少數(shù)組元素的移動returna-nItems;publicbooleanisEmpty()return(nItems=0);publicbooleanisFull()return(nItems=maxSize);publicintsize()returnnItems;publicclassduilie/隊列體類privated

8、uilies;privateStringdata;duilie(Stringdata)this.data=data;publicStringgetData()returndata;)publicvoidsetData(Stringdata)this.data=data;)publicduiliegetS()returns;)publicvoidsetS(duilies)this.s=s;)publicclassduiliecz/隊列操作類/*paramargs*/privateinti=0;/隊列長privateduilietop=newduilie();/隊列頭privateduilieen

9、d=newduilie();/隊列尾publicvoidadd(Strings)/添加隊列duiliem=newduilie(s);if(i!=0)m.setS(top.getS();top.setS(m);elsetop.setS(m);end.setS(m);i+;4 .隊列publicvoiddel()/刪除隊尾if(i=0)return;elseif(i=1)top.setS(null);end.setS(null);elseduilietopi=newduilie();/top1.setS(top.getS();while(!top1.getS().getS().equals(end

10、.getS()top1.setS(top1.getS().getS();)end.setS(top1.getS();)i-;)publicstaticvoidmain(Stringargs)/TODOAuto-generatedmethodstubduilieczm=newduiliecz();m.add(1);m.add(2);m.add(3);m.add(4);for(intn=0;n4;n+)m.del();)publicintgetI()returni;)publicduiliegetEnd()returnend;)publicduiliegetTop()returntop;)5 .棧

11、publicclassStackintarr;intlen=0;publicStack()arrnewint100;隊列底查找用緩存publicStack(intn)arr=newintn;)publicintsize()returnlen+1;)/擴(kuò)大數(shù)組publicvoidresize()intb=newintarr.length*2;System.arraycopy(arr,0,b,0,arr.length);arr=b;)publicvoidshow()for(inti=0;i=arr.length)resize();arrlen=a;len+;)/出棧publicintpop()if

12、(len=0)System.out.println();System.out.println(return-1;)inta=arrlen-1;arrlen-1=0;len-;returna;stackisempty!);6 .鏈表classNodeObjectdata;Nodenext;publicNode(Objectdata)setData(data);publicvoidsetData(Objectdata)this.data=data;publicObjectgetData()returndata;classLinkNodehead;intsize=0;publicvoidadd(Ob

13、jectdata)Noden=newNode(data);if(head=null)head=n;elseNodecurrent=head;while(true)if(current.next=null)break;current=current.next;current.next=n;size+;publicvoidshow()Nodecurrent=head;if(current!=null)while(true)System.out.println(current);if(current=null)break;)current=current.next;)elseSystem.out.p

14、rintln(linkisemptypublicObjectget(intindex)/.publicintsize()returnsize;7 .單鏈表classNode/節(jié)點(diǎn)類，單鏈表上的節(jié)點(diǎn)Stringdata;/數(shù)據(jù)域，存放String類的數(shù)據(jù)Nodenext;/指向下一個節(jié)點(diǎn)Node(Stringdata)this.data=data;/構(gòu)造函數(shù)Stringget()returndata;/返回數(shù)據(jù)classMyLinkList/鏈表類Nodefirst;/頭節(jié)點(diǎn)intsize;/鏈表長度MyLinkList(Stringarg)/Nodefirst=newNode(head);/生

15、成頭節(jié)點(diǎn)first=newNode(head);/J.F.這里不需要定義局部變量first/如果定義了局部變量，那成員變量first就一直沒有用上/所以，它一直為空size=0;Nodep=first;for(inti=0;iarg.length;i+)/將arg數(shù)組中的元素分別放入鏈表中Nodeq=newNode(argi);q.next=p.next;/每一個節(jié)點(diǎn)存放一個arg數(shù)組中的元素p.next=q;p=p.next;size+;);MyLinkList()/無參數(shù)構(gòu)造函數(shù)/Nodefirst=newNode(head);first=newNode(head);/J.F.這里犯了和上

16、一個構(gòu)造方法同樣的錯誤size=0;intsize()/返回鏈表長度returnsize;voidinsert(Nodea,intindex)/將節(jié)點(diǎn)a插入鏈表中的第index個位置Nodetemp=first;for(inti=0;iindex;i+)temp=temp.next;/找到插入節(jié)點(diǎn)的前一節(jié)點(diǎn)a.next=temp.next;/插入節(jié)點(diǎn)temp.next=a;size+;Nodedel(intindex)/刪除第index個節(jié)點(diǎn)，并返回該值Nodetemp=first;for(inti=0;iindex;i+)temp=temp.next;/找到被刪除節(jié)點(diǎn)的前一節(jié)點(diǎn))Nodeno

17、de=temp.next;temp.next=node.next;size-;/刪除該節(jié)點(diǎn)，鏈表長度減一returnnode;)voidprint()/在屏幕上輸出該鏈表(這段程序總是出錯，不知道錯在哪里)(Nodetemp=first;for(inti=1;i);)voidreverse()/倒置該鏈表(for(inti=0;i=size)returnnull;)Nodetemp=first;for(inti=0;i10)System.out.println(長度超過限制或者缺少參數(shù));elseMyLinkListll=newMyLinkList(arg);/創(chuàng)建一個鏈表ll.print()

18、;/先輸出該鏈表(運(yùn)行到這一步拋出異常)ll.reverse();/倒置該鏈表ll.print();/再輸出倒置后的鏈表Stringdata=newString10;inti;for(i=0;ill.size();i+)datai=ll.get(i);/將鏈表中的數(shù)據(jù)放入數(shù)組)/sort(data);/按升序排列data中的數(shù)據(jù)(有沒有現(xiàn)成的排序函數(shù)？)for(i=0;ill.size();i+)System.out.print(datai+;);/輸出數(shù)組中元素)System.out.println();MyStacks=newMyStack();/創(chuàng)建堆棧實(shí)例sfor(i=0;ilast)

19、:);Linkcurrent=first;while(current!=null)current.display();current=current.next;)System.out.println();classFirstLastListAppstaticvoidmain(Stringargs)TODOAuto-generatedmethodstubnewFirstLastList();/insertatfront/displaythelist/deletefirsttwoitems/displayagain9 .有序鏈表packagearithmetic;classLinkpublicin

20、tiData=0;publicLinknext=nullpublicLink(intiData)this.iData=iData;publicvoiddisplay()System.out.print(iData+);classSortedListprivateLinkfirst=nullpublicSortedList()first=null;publicvoidinsert(intkey)public/FirstLastListtheList=theList.insertFirst(22);theList.insertFirst(44);theList.insertFirst(66);th

21、eList.insertLast(11);theList.insertLast(33);theList.insertLast(55);theList.displayList();theList.deleteFirst();theList.deleteFirst();theList.displayList();/insertatrearLinknewLink=newLink(key);Linkprevious=null;Linkcurrent=first;/while的第一個條件是沒有到達(dá)鏈表的尾端，第二個是按順序找到一個合適的位置while(current!=null&keycurre

22、nt.iData)previous=current;current=current.next;/如果是空表或者要插入的元素最小，則在表頭插入keyif(current=first)first=newLink;elseprevious.next=newLink;newLink.next=current;/*刪除表頭的節(jié)點(diǎn)*return要刪除的節(jié)點(diǎn)*/publicLinkremove()Linktemp=first;first=first.next;returntemp;publicbooleanisEmpty()return(first=null);publicvoiddisplayList()

23、System.out.print(List(first-last):)Linkcurrent=first;/startatbeginningoflistclassSortedListAppwhile(current!=current.display();current=current.System.out.println(null)/untilendoflist,/printdatanext;/movetonextlinknSortedListtheSortedList=theSortedList.insert(20);theSortedList.insert(40);theSortedLis

24、t.displayList();theSortedList.insert(10);theSortedList.insert(30);theSortedList.insert(50);theSortedList.displayList();theSortedList.remove();theSortedList.displayList();newSortedList();/insert2items/displaylist/insert3moreitems/displaylist/removeanitem/displaylist10 .雙向鏈表classLink/雙向鏈表，有兩個指針，一個向前pu

25、blicvoiddisplay()System.out.print(iData+);classDoublyLinked/分別指向鏈表的表頭和表尾privateLinkfirst=nullprivateLinklast=nullpublicbooleanisEmpty()returnfirst=null/*在表頭插入數(shù)據(jù)param要插入的節(jié)點(diǎn)的數(shù)據(jù)*/publicvoidinsertFirst(intkey)LinknewLink=newLink(key);/如果開始鏈表為空，則插入第一個數(shù)據(jù)后,last也指向第一個數(shù)據(jù)if(this.isEmpty()last=newLink;else/表不為

26、空的情況first.previous=newLink;newLink.next=first;/無論怎publicstaticvoidmain(Stringargs)/createnewlistpublicpublicLinkpublicLinkpublicLink(thisintiData=0;previous=nullnext=null;intiData).iData=iData;樣，插入后都的讓first重新指向第一個節(jié)點(diǎn)first=newLink;publicvoidinsertLast(intkey)/在尾端插入數(shù)據(jù)，同上LinknewLink=newLink(key);if(this

27、.isEmpty()first=newLink;elselast.next=newLink;newLink.previous=last;last=newLink;/一二在指定的節(jié)點(diǎn)后插入數(shù)據(jù)/如果插入點(diǎn)在last的位置if(current=last)last=newLink;else/非last位置，交換各個next和previous的指針newLink.next=current.next;current.next.previous=newLink;current.next=newLink;newLink.previous=current;returntrue;/*刪除表頭的節(jié)點(diǎn)return*

28、/publicLinkdeleteFirst()Linktemp=first;/如果表中只有一個元素，刪除后則為空表，所以last=nullparamkey指定的節(jié)點(diǎn)的值paramiData要插入的數(shù)據(jù)return是否插入成功*/publicbooleaninsertAfter(intkey,intiData)LinknewLink=newLink(key);Linkcurrent=first;/從first開始遍歷，看能否找到以key為關(guān)鍵字的節(jié)點(diǎn)while(current.iData!=key)current=current.next;/若能找到就跳出循環(huán)，否則返回false,插入失敗if

29、(current=null)returnfalseif(first.next=null)last=null;else/否則，讓第二個元素的previous=nullfirst.next.previous=null;/刪除頭指針，則first指向原來的secondfirst=first.next;returntemp;publicLinkdeleteLast()/同上Linktemp=last;if(last.previous=null)first=null;elselast.previous.next=null;last=last.previous;returntemp;publicLinkd

30、eleteKey(intkey)Linkcurrent=first;/遍歷整個鏈表查找對應(yīng)的key,如果查到跳出循環(huán)，否則while(current.iData!=key)current=current.next;/.否則遍歷到表尾，說明不存在此key,返回null,刪除失敗if(current=null)returnnull;)if(current=first)first=first.next;elsecurrent.previous.next=current.next;if(current=last)last=last.previous;elsecurrent.next.previous=

31、current.previous;returncurrent;)publicvoiddisplayForward()Linkcurrent=while(current!=current.display();System.out.println();)publicvoiddisplayBackward()DoublyLinkedtheList=theList.insertFirst(22);theList.insertFirst(44);newDoublyLinked();/insertatfronttheList.insertFirst(66);theList.insertLast(11);t

32、heList.insertLast(33);theList.insertLast(55);Linkcurrent=last;classwhile(current!=current.display();current=current.System.out.println();nullprevious;DoublyLinkedApppublicstaticvoidmain(Stringargs)/makeanewlistfirstnullcurrent=current.next;/insertatreartheList.displayForward();theList.displayBackwar

33、d();theList.deleteFirst();theList.deleteLast();theList.deleteKey(11);theList.displayForward();theList.insertAfter(22,77);theList.insertAfter(33,88);theList.displayForward();)11 .實(shí)現(xiàn)二叉樹前序遍歷迭代器classTreeNode這個類用來聲明樹的結(jié)點(diǎn)，其中有左子樹、右子樹和自身的內(nèi)容。classMyTree這個類用來聲明一棵樹，傳入根結(jié)點(diǎn)。這里設(shè)計的比較簡單classTreeEum這個類是樹的迭代器，通過MyTree類

34、的方法獲取，這里主要就是設(shè)計它了。代碼如下：/TreeNode類，使用了泛型，由于比較簡單，考試.大提示不作解釋classTreeNode(Enode;privateTreeNodeleft;privateTreeNoderight;publicTreeNode(Ee)(this(e,null,null);)publicTreeNode(Ee,TreeNodeleft,TreeNoderight)(this.node=e;this.left=left;this.right=right;)publicTreeNodeleft()(returnleft;)publicTreeNoderight()

35、(returnright;)/MyTree類，沒什么功能，傳入根結(jié)點(diǎn)構(gòu)造，getEnumerator()方法獲取迭代器。classMyTree(TreeNoderoot;publicMyTree(TreeNoderoot)(this.root=root;publicTreeEnumgetEnumerator()(returnnewTreeEnum(root);/這個類為迭代器，有詳細(xì)解釋，相信各位能看懂。在棧中用了兩次泛型。importjava.util.Stack;publicclassTreeEnum(privateTreeNoderoot;privateStackTreeNodestor

36、e;/*保存遍歷左子樹但未遍歷右子樹的結(jié)點(diǎn)*/privateTreeNodenext;publicTreeEnum(TreeNoderoot)(this.root=root;store=newStackTreeNode();next=root;publicTreeNodenext()(TreeNodecurrent=next;if(next!=null)(/*如果當(dāng)前結(jié)點(diǎn)的左子樹不為空，則遍歷左子樹，并標(biāo)記當(dāng)前結(jié)點(diǎn)未遍歷右子樹*/if(next.left()!=null)(store.push(next);next=next.left();/如果當(dāng)前結(jié)點(diǎn)的左子樹為空，則遍歷右子樹elseif(

37、next.right()!=null)(next=next.right();/displaylistforward/displaylistbackward/deletefirstitem/deletelastitem/deleteitemwithkey11/displaylistforward/insert77after22/insert88after33/displaylistforward/*如果當(dāng)前結(jié)點(diǎn)為葉子，則找未遍歷右子樹的結(jié)點(diǎn)并且遍歷它的右子樹*/else(if(!store.empty()/*判斷是否還有結(jié)點(diǎn)的右子樹未遍歷*/(TreeNodetmp=store.pop();/*

38、如果有未遍歷右子樹的結(jié)點(diǎn)，但它的右子樹為空，且還有結(jié)點(diǎn)的右子樹未遍歷，*/*則一直往上取，直到取到未遍歷右子樹且右子樹不為空的結(jié)點(diǎn)，遍歷它的右子樹.*/while(tmp.right()=null)&!store.empty()(tmp=store.pop();next=tmp.right();else(/*如果沒有哪個結(jié)點(diǎn)右子樹未遍歷，則表示沒有下一個結(jié)點(diǎn)了，設(shè)置next為null*/next=null;returncurrent;publicbooleanhasMoreElement()(returnnext!=null;下面寫個測試類，不作解釋，相信大家看得懂publicclas

39、sTreeReaderpublicstaticvoidmain(Stringargs)TreeNoden1=newTreeNode(n1)TreeNoden2=newTreeNode(n2)TreeNoden3=newTreeNode(n3)TreeNoden4=newTreeNode(n4)TreeNoden5=newTreeNode(n5)TreeNoden6=newTreeNode(n6,null,n1);TreeNoden7=newTreeNode(n7,n2,null);TreeNoden8=newTreeNode(n8,n7,null);TreeNoden9=newTreeNode

40、(n9,null,n5);TreeNoden10=newTreeNode(n10,n4,n9);TreeNoden11=newTreeNode(n11,n6,n8);TreeNoden12=newTreeNode(n12,n3,n10);TreeNoderoot=newTreeNode(MyTreetree=newMyTree(root);root,n11,n12);TreeEnumeum=tree.getEnumerator();while(eum.hasMoreElement()(System.out.print(eum.next().node+)System.out.println(en

41、d);)12 .迭代器packageTreeIterator;publicinterfaceIteratorpublicbooleanhasNext();publicObjectnext();)這個接口我們有2個方法，hasNext()是否還有下一條數(shù)據(jù)，next返回具體的Object這里也就是樹。我們先不必要忙著做他的實(shí)現(xiàn)類，我們現(xiàn)在要來做的是這個容器(不是JAVA中容器，與arraylist什么的無關(guān))，正所謂樹的容器是什么，是山也！我們想想山應(yīng)該具有什么呢！？首先它要有種植樹的功能，這里可以看作添加樹。我們可以想像山的功能是和樹相互關(guān)聯(lián)的，那么他們之間是什么關(guān)系呢，我們給他們一種聚合的關(guān)

42、系，聚合的關(guān)系大家可以參考UML圖，我在這里給出它的一種程序表現(xiàn)形式。packageTreeIterator;publicclassHallTreetree;/這里可以看作是聚合關(guān)系privateintindex;/指向Tree口的標(biāo)簽publicHall(intmaxNumber)tree=newTreemaxNumber;index=0;)publicvoidadd(Treetree)this.treeindex=tree;index+;)publicIteratorconnectIterator();)這里我們定義的山可以抽象出Hall類來，Treetree可以看作是山和樹之間的一種聚合

43、關(guān)系。add方法就是添加樹。問題來了，山和樹有了關(guān)系，那么山和迭代器有什么關(guān)系呢。它們之間肯定有一種關(guān)系。我們有了這個容器(山)，就要把這個容器來實(shí)現(xiàn)迭代的方法：hasNext()和Next().恩這里我們可以看出，山和迭代器之間也是一種關(guān)聯(lián)關(guān)系。我們就把它看成是一種聚合關(guān)系(TIP:聚合關(guān)系一種特殊的關(guān)聯(lián)關(guān)系)。我們可以通過一個connectIterator方法來鏈接山和迭代器，接下來我們要去做一個具體的迭代類，這個具體的類中間有了hasNext()和Next()的具體實(shí)現(xiàn)方法packageTreeIterator;publicclassTreeIteratorimplementsItera

44、torprivateintlast=0;privateHallhall;publicTreeIterator(Hallhall)this.hall=hall;)publicbooleanhasNext()if(lasthall.tree.length)returntrue;elsereturnfalse;)publicTreenext()Treet=hall.treelast;last+;returnt;)這里Hallhall就可以看作是一種關(guān)聯(lián)關(guān)系，我們要把山和迭代器聯(lián)系起來就通過構(gòu)造函數(shù)來實(shí)現(xiàn),hasNext和next實(shí)現(xiàn)方法就體現(xiàn)出來了有了山，有了迭代器，可是樹還沒有定義，不過這個樹的方

45、法還很好解決！樹不關(guān)聯(lián)其他的事務(wù)，我們returnnewTreeIterator(this);可以簡單的這么寫:packageTreeiterator;publicclassTreeprivateStringname;publicTree(Stringname)=name;)publicStringgetName();)好了似乎我們整個工程完工了，我們現(xiàn)在來模擬一下農(nóng)民老大伯來種樹撒肥的過程;packageTreeiterator;publicclassPrenpublicPren()voidmain(Stringargs)newHall(4);

46、newTree(蘋果樹);newTree(梨樹)；newTree(橘子樹);newTree(鳳梨樹);for(Iteratori=hall.connectiterator();i.hasNext();)StringType=(Tree)(i.next().getName();publicstaticHallhall=hall.add(hall.add(hall.add(hall.add(if(Type=蘋果樹)System.out.println()if(Type=梨樹)System.out.println()if(Type=橘子樹)System.out.println(灑蘋果樹的農(nóng)藥,);“

47、灑梨樹的農(nóng)藥);灑橘子樹的農(nóng)藥，灑了也沒用，還沒到成熟日，現(xiàn)在沒結(jié)果實(shí));)if(Type=鳳梨樹)System.out.println(南風(fēng)天，濕氣大，讓它爛在地里吧);)種4個樹，山小而五臟俱全，更像一個土包，再要有樹才行啊，所以4個樹的實(shí)例出現(xiàn)。好了接下來種樹，幾毫秒解決！山了有我們就要把山放到迭代器中間去了。遍歷這個山(容器)。聯(lián)想我們看看arrayList中的迭代器模式是怎么實(shí)現(xiàn)的！ArrayLista=newArrayList();a.add(a1);a.add(a2);a.add(a3);a.add(a4);for(Iteratori=a.iterator();i.hasNext

48、();)System.out.println(i.next().toString();)13 .合并搜索算法publicclassMergeSortArrayprivatelongtheArray;privateintnElems;publicMergeSortArray(intmax)theArray=newlongmax;nElems=0;)publicvoidinsert(longvalue)theArraynElems=value;/insertitnElems+;/incrementsize)publicvoiddisplay()publicvoidmergeSort()for(in

49、tj=0;jSystem.out.print(System.out.println()nElems;j+)theArrayj+););longworkSpace=recMergeSort(workSpace,0,if(lowerBound=upperBound)return;/nousesortingelse/findmidpointintmid=(lowerBound+upperBound)/2;/sortlowhalfrecMergeSort(workSpace,lowerBound,mid);/sorthighhalfrecMergeSort(workSpace,mid+1,upperB

50、ound);/mergethemmerge(workSpace,lowerBound,mid+1,upperBound);while(lowPtr=mid&highPtr=upperBound)if(theArraylowPtrworkSpacej+=elsewhile(lowPtr=mid)workSpacej+=while(highPtr=upperBound)privatevoidrecMergeSort(longworkSpace,intlowerBound,intupperBound)privatevoidmerge(longworkSpace,intlowPtr,inthi

51、ghPtr,intupperBound)intj=0;/workspaceindexintintintlowerBound=lowPtr;mid=highPtr-1;n=upperBound-lowerBound+1;/#ofitemsworkSpacej+=theArrayhighPtr+;forworkSpacej+=theArrayhighPtr+;(j=0;j0)returnnum+RecursionNum(num-1);ElseMergeSortArrayarr=newMergeSortArray(maxSize);/createthearrayreturn0;Recursionre

52、=newRecursion();15.歸并排序/*歸并排序，要求待排序的數(shù)組必須實(shí)現(xiàn)Comparable接口*/publicclassMergeSortimplementsSortstrategyprivateComparablebridge;/*利用歸并排序算法對數(shù)組obj進(jìn)行排序*/publicvoidsort(Comparableobj)if(obj=null)thrownewNullPointerException(Theparamcannotbenull!)bridge=newComparableobj.length;/初始化中間數(shù)組mergeSort(obj,0,obj.lengt

53、h-1);/歸并排序bridge=null;)/*paramobj*要排序的數(shù)組的句柄*paramleft*要排序的數(shù)組的第一個元素下標(biāo)*paramright*要排序的數(shù)組的最后一個元素的下標(biāo)*/privatevoidmergeSort(Comparableobj,if(leftright)intcenter=(left+right)/2;mergeSort(obj,left,center);mergeSort(obj,center+1,right);merge(obj,left,center,right);)/*將兩個對象數(shù)組進(jìn)行歸并，并使歸并后為升序。歸并前兩個數(shù)組分別有序?qū)⑾聵?biāo)從left

54、到right的數(shù)組進(jìn)行歸并排序);intleft,intright)*paramobj*對象數(shù)組的句柄*paramleft*左數(shù)組的第一個元素的下標(biāo)*paramcenter*左數(shù)組的最后一個元素的下標(biāo)*paramright*右數(shù)組的最后一個元素的下標(biāo)*/privatevoidmerge(Comparableobj,intmid=center+1;intthird=left;inttmp=left;while(left=center&mid=right)組if(pareTo(objmid)=0)bridgethird+=objleft+;elsebridgethird+=objmid+;

55、/剩余部分依次置入中間數(shù)組while(mid=right)bridgethird+=objmid+;while(left=center)bridgethird+=objleft+;/將中間數(shù)組的內(nèi)容拷貝回原數(shù)組copy(obj,tmp,right);intleft,intcenter,intright)/從兩個數(shù)組中取出小的放入中間數(shù)/*將中間數(shù)組bridge中的內(nèi)容拷貝到原數(shù)組中*paramobj*原數(shù)組的句柄*paramleft*要拷貝的第一個元素的下標(biāo)*paramright*要拷貝的最后一個元素的下標(biāo)*/privatevoidcopy(Comparableobj,while(left=r

56、ight)objleft=bridgeleft;intleft,intright)left+;16.希爾排序間隔序列：h=3*h+1,h=(h-1)/3publicclassShellSort/*paramargs*/publicstaticvoidmain(String口args)/TODOAuto-generatedmethodstubShellSortss=newShellSort();intnum口=546,87,21,3124,65,2,9,3,213,54,98,23,6,4,7,8,123,872,61,5,8954);ss.shellArray(num);for(inti=0;

57、inum.length;i+)System.out.println(numi);)publicvoidshellArray(int口num)inti=1;inttem,in;for(;i=1;)for(intj=i;ji-1&numin-i=tem)numin=numin-i;in=in-i;)numin=tem;)i=(i-1)/3;17.快速排序classQuicksortprivateintdata;QuickSort(intdata)this.data=data;publicvoidquickSort()recQuickSort(data,0,data.length-1);pr

58、ivatevoidrecQuickSort(intdata,intlow,inthigh)/設(shè)置兩個滑標(biāo)intlowCursor=low+1;inthighCursor=high;/交換時的臨時變量inttemp=0;/比較樞值，設(shè)為數(shù)組的第一個值intmedi=datalow;while(true)/從低端開始查找，確定大于數(shù)datalow所在的位置while(lowCursorhigh&datalowCursor=判斷確定小于值while(highCursorlow&datahighCursor=medi)highCursor-;/兩游標(biāo)位置出現(xiàn)越界，退出循環(huán)if(lowC

59、ursor=highCursor)break;/交換datahighCursor和datalowCursor位置數(shù)據(jù)temp=datahighCursor;datahighCursor=datalowCursor;datalowCursor=temp;/由while循環(huán)退出條件可知：lowCursorhighCursor/當(dāng)前l(fā)owCursor指向右側(cè)大于datalow的第一個位置；/而highCursor指向左側(cè)小于datalow的第一個位置，所以需要交換和datalow/datahighCursor的值datalow=datahighCursor;datahighCursor=medi;/

60、遞歸運(yùn)算左半部分if(lowhighCursor)recQuickSort(data,low,highCursor);)/遞歸運(yùn)算右半部分if(lowCursorhigh)recQuickSort(data,lowCursor,high);)publicvoiddisplay()for(inti=0;idata.length;i+)System.out.print(datai+);)System.out.println();)publicstaticvoidmain(Stringargs)intdata=newint43,12,32,55,33,67,54,65,43,22,66,98,74);Quicksortsort=newQuickSort(data)