Java数据结构与经典算法高手必会

第页

大O表示法：粗略的量度方法即算法的速度是如何与数据项的个数相关的

2

排序 2优先级队列 6队列 8栈 9链表 10单链表 12双端链表 16有序链表 18双向链表 20实现二叉树前序遍历迭代器 24迭代器 27合并搜索算法 30希尔排序 34快速排序 35二叉树 37经典算法的Java实现 42（1）河内塔问题： 42（2）费式数列 44（3）巴斯卡（Pascal）三角形 44（4）蒙地卡罗法求PI 46（5）最大公因数、最小公倍数 47（6）阿姆斯壮数 48（7）最大访客数 48（8）洗扑克牌（乱数排列） 50（9）约瑟夫问题（JosephusProblem） 51（10）排列组合 53（11）得分排行 54（12）选择、插入、气泡排序 56（13）快速排序（一） 59（14）快速排序（二） 61（15）快速排序（三） 62（16）合并排序 63（17）基数排序 64（18）循序查找法（使用卫兵） 66（20）插补查找法 68（21）费式查找法 69（22）稀疏矩阵 72（23）多维矩阵转一维矩阵 73（24）上三角、下三角、对称矩阵 74（25）奇数魔方阵 76（26）4N魔方阵 77（27）2(2n+1)魔方阵 79大O表示法：粗略的量度方法即算法的速度是如何及数据项的个数相关的算法大O表示法表示的运行时间线性查找O(N)二分查找O(logN)无序数组的插入O(1)有序数组的插入O(N)无序数组的删除O(N)有序数组的删除O(N)O(1)是最优秀的,O(logN)良好,O(N)还可以,O(N2)稍差(在冒泡法中见到)排序publicclassJWzw{ //插入排序 publicvoidinsertArray(Integer[]in){ inttem=0; intnum=0; intupnum=0; for(inti=0;i<in.length;i++){ for(intj=i-1;j>=0;j--){ num++; if(in[j+1]<in[j]){ tem=in[j+1]; in[j+1]=in[j]; in[j]=tem; upnum++; else break; for(inti=0;i<in.length;i++){ System.out.print(in[i]); if(i<in.length-1) System.out.print(","); System.out.println(); System.out.println("插入排序循环次数:"+num); System.out.println("移动次数："+upnum); System.out.print("\n\n\n"); //选择排序 publicvoidchooseArray(Integer[]in){ inttem=0; intnum=0; intupnum=0; for(inti=0;i<in.length;i++) for(intj=i;j<in.length-1;j++){ num++; if(in[j+1]<in[j]){ tem=in[j+1]; in[j+1]=in[j]; in[j]=tem; upnum++; for(inti=0;i<in.length;i++){ System.out.print(in[i]); if(i<in.length-1) System.out.print(","); System.out.println(); System.out.println("选择排序循环次数:"+num); System.out.println("移动次数："+upnum); System.out.print("\n\n\n"); //冒泡排序 publicvoidefferArray(Integer[]in){ inttem=0; intnum=0; intupnum=0; for(inti=0;i<in.length;i++){ for(intj=i;j<in.length-1;j++) num++; if(in[j+1]<in[i]){ tem=in[j+1]; in[j+1]=in[i]; in[i]=tem; upnum++; for(inti=0;i<in.length;i++){ System.out.print(in[i]); if(i<in.length-1) System.out.print(","); System.out.println(); System.out.println("冒泡排序循环次数:"+num); System.out.println("移动次数："+upnum); System.out.print("\n\n\n"); //打印乘法口诀 publicvoidprintMulti(){ for(intj=1;j<10;j++){ for(inti=1;i<=j;i++){ System.out.print(i+"*"+j+"="+j*i+"\t"); System.out.print("\t\n"); System.out.print("\n\n\n"); //打印N*1+N*2+N*3=num的所有组合 publicvoidprintNumAssemble(intnum){ for(inti=0;i<num+1;i++){ for(intj=0;j<num/2+1;j++){ for(intin=0;in<num/3+1;in++){ if(i*1+j*2+in*3==num){ System.out.println("小马"+i+",\t中马"+j+",\t大马"+in); *@paramargs publicstaticvoidmain(String[]args){ JWzwjwzw=newJWzw(); intnum=3; jwzw.printMulti();//打印乘法口诀 jwzw.printNumAssemble(100);//打印N*1+N*2+N*3=num的所有组合 Integerin[]={8,89,5,84,3,45,12,33,77,98,456,878,654,213,897}; jwzw.efferArray(in);//冒泡排序 Integerin1[]={8,89,5,84,3,45,12,33,77,98,456,878,654,213,897}; jwzw.insertArray(in1);//插入排序 Integerin2[]={8,89,5,84,3,45,12,33,77,98,456,878,654,213,897}; jwzw.chooseArray(in2);//选择排序 //inti=num++; //System.out.println(i); System.out.println(1000>>2);优先级队列classPriorityQueue{privatelong[]a=null;privateintnItems=0;privateintmaxSize=0;publicPriorityQueue(intmaxSize){a=newlong[maxSize];this.maxSize=maxSize;nItems=0;publicvoidinsert(longl){//优先级队列的插入不是队尾,而是选择一个合适的按照某种顺序插入的//当队列长度为0时，如下//不为0时,将所有比要插入的数小的数据后移,这样大的数就在队列的头部了inti=0;if(nItems==0){a[0]=l;}else{for(i=nItems-1;i>=0;i--){if(l<a[i])a[i+1]=a[i];elsebreak;a[i+1]=l;nItems++;publiclongremove(){//移出的是数组最上端的数，这样减少数组元素的移动returna[--nItems];publicbooleanisEmpty(){return(nItems==0);publicbooleanisFull(){return(nItems==maxSize);publicintsize(){returnnItems;publicclassduilie{//队列体类privateduilies;privateStringdata;duilie(Stringdata){this.data=data;publicStringgetData(){returndata;publicvoidsetData(Stringdata){this.data=data;publicduiliegetS(){returns;publicvoidsetS(duilies){this.s=s;publicclassduiliecz{//队列操作类*@paramargsprivateinti=0;//队列长privateduilietop=newduilie("");//队列头privateduilieend=newduilie("");//队列尾publicvoidadd(Strings){//添加队列duiliem=newduilie(s);if(i!=0){m.setS(top.getS());top.setS(m);}else{top.setS(m);end.setS(m);i++;队列

publicvoiddel(){//删除队尾if(i==0){return;}elseif(i==1){top.setS(null);end.setS(null);}else{duilietop1=newduilie("");//队列底查找用缓存top1.setS(top.getS());while(!top1.getS().getS().equals(end.getS())){top1.setS(top1.getS().getS());end.setS(top1.getS());i--;publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubduilieczm=newduiliecz();m.add("1");m.add("2");m.add("3");m.add("4");for(intn=0;n<4;n++){m.del();publicintgetI(){returni;publicduiliegetEnd(){returnend;publicduiliegetTop(){returntop;栈publicclassStack{ int[]arr; intlen=0; publicStack(){ arr=newint[100]; publicStack(intn){ arr=newint[n]; publicintsize(){ returnlen+1; //扩大数组 publicvoidresize(){ int[]b=newint[arr.length*2]; System.arraycopy(arr,0,b,0,arr.length); arr=b; publicvoidshow(){ for(inti=0;i<len;i++){ System.out.print(arr[i]+""); System.out.println(); //进栈 publicvoidpush(inta){ if(len>=arr.length) resize(); arr[len]=a; len++; //出栈 publicintpop(){ if(len==0){ System.out.println(); System.out.println("stackisempty!"); return-1; inta=arr[len-1]; arr[len-1]=0; len--; returna;链表classNode{ Objectdata; Nodenext; publicNode(Objectdata){ setData(data); publicvoidsetData(Objectdata){ this.data=data; publicObjectgetData(){ returndata;classLink{ Nodehead; intsize=0; publicvoidadd(Objectdata){ Noden=newNode(data); if(head==null){ head=n; }else{ Nodecurrent=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; }else{ System.out.println("linkisempty"); publicObjectget(intindex){ publicintsize(){ returnsize;单链表classNode//节点类，单链表上的节点 Stringdata;//数据域，存放String类的数据 Nodenext;//指向下一个节点 Node(Stringdata){ this.data=data;//构造函数 Stringget(){ returndata;//返回数据classMyLinkList//链表类 Nodefirst;//头节点 intsize;//链表长度 MyLinkList(Stringarg[]){ //Nodefirst=newNode("head");//生成头节点 first=newNode("head");//J.F.这里不需要定义局部变量first //如果定义了局部变量，那成员变量first就一直没有用上 //所以，它一直为空 size=0; Nodep=first; for(inti=0;i<arg.length;i++)//将arg数组中的元素分别放入链表中 Nodeq=newNode(arg[i]); q.next=p.next;//每一个节点存放一个arg数组中的元素 p.next=q; p=p.next; size++; MyLinkList()//无参数构造函数 //Nodefirst=newNode("head"); first=newNode("head");//J.F.这里犯了和上一个构造方法同样的错误 size=0; intsize()//返回链表长度 returnsize; voidinsert(Nodea,intindex)//将节点a插入链表中的第index个位置 Nodetemp=first; for(inti=0;i<index;i++){ temp=temp.next;//找到插入节点的前一节点 a.next=temp.next;//插入节点 temp.next=a; size++; Nodedel(intindex)//删除第index个节点，并返回该值 Nodetemp=first; for(inti=0;i<index;i++){ temp=temp.next;//找到被删除节点的前一节点 Nodenode=temp.next; temp.next=node.next; size--;//删除该节点，链表长度减一 returnnode; voidprint()//在屏幕上输出该链表（这段程序总是出错，不知道错在哪里） Nodetemp=first; for(inti=1;i<size;i++)//将各个节点分别在屏幕上输出 temp=temp.next; System.out.print(temp.get()+"->"); voidreverse()//倒置该链表 for(inti=0;i<size;i++){ insert(del(size-1),0);//将最后一个节点插入到最前 //J.F.最后一个节点的index应该是size-1 //因为第一个节点的index是0 Stringget(intindex)//查找第index个节点，返回其值 if(index>=size){ returnnull; Nodetemp=first; for(inti=0;i<index;i++){ temp=temp.next;//找到被查找节点的前一节点 returntemp.next.get();classMyStack//堆栈类，用单链表实现 MyLinkListtmp; Nodetemp; MyStack(){ //MyLinkListtmp=newMyLinkList(); tmp=newMyLinkList();//J.F.和MyLinkList构造方法同样的错误 voidpush(Stringa)//压栈，即往链表首部插入一个节点 Nodetemp=newNode(a); tmp.insert(temp,0); Stringpop()//出栈，将链表第一个节点删除 Nodea=tmp.del(0); returna.get(); intsize(){ returntmp.size(); booleanempty()//判断堆栈是否为空 if(tmp.size()==0) returnfalse; else returntrue;publicclassMyLinkListTest//测试程序部分 publicstaticvoidmain(Stringarg[])//程序入口 if((arg.length==0)||(arg.length>10)) System.out.println("长度超过限制或者缺少参数"); else{ MyLinkListll=newMyLinkList(arg);//创建一个链表 ll.print();//先输出该链表（运行到这一步抛出异常） ll.reverse();//倒置该链表 ll.print();//再输出倒置后的链表 Stringdata[]=newString[10]; inti; for(i=0;i<ll.size();i++){ data[i]=ll.get(i);//将链表中的数据放入数组 //sort(data);//按升序排列data中的数据（有没有现成的排序函数？） for(i=0;i<ll.size();i++){ System.out.print(data[i]+";");//输出数组中元素 System.out.println(); MyStacks=newMyStack();//创建堆栈实例s for(i=0;i<ll.size();i++){ s.push(data[i]);//将数组元素压栈 while(!s.empty()){ System.out.print(s.pop()+";");//再将堆栈里的元素弹出双端链表classLink{ publicintiData=0; publicLinknext=null; publicLink(intiData){ this.iData=iData; publicvoiddisplay(){ System.out.print(iData+"");classFirstLastList{ privateLinkfirst=null; privateLinklast=null; publicFirstLastList(){ first=null; last=null; publicvoidinsertFirst(intkey){ LinknewLink=newLink(key); if(this.isEmpty()) last=newLink; newLink.next=first; first=newLink; publicvoidinsertLast(intkey){ LinknewLink=newLink(key); if(this.isEmpty()) first=newLink; else last.next=newLink; last=newLink; publicLinkdeleteFirst(){ Linktemp=first; if(first.next==null) last=null; first=first.next; returntemp; publicbooleanisEmpty(){ return(first==null); publicvoiddisplayList(){ System.out.print("List(first-->last):"); Linkcurrent=first; while(current!=null){ current.display(); current=current.next; System.out.println("");classFirstLastListApp{ publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub FirstLastListtheList=newFirstLastList(); theList.insertFirst(22);//insertatfront theList.insertFirst(44); theList.insertFirst(66); theList.insertLast(11);//insertatrear theList.insertLast(33); theList.insertLast(55); theList.displayList();//displaythelist theList.deleteFirst();//deletefirsttwoitems theList.deleteFirst(); theList.displayList();//displayagain有序链表packagearithmetic;classLink{ publicintiData=0; publicLinknext=null; publicLink(intiData){ this.iData=iData; publicvoiddisplay(){ System.out.print(iData+"");classSortedList{ privateLinkfirst=null; publicSortedList(){ first=null; publicvoidinsert(intkey){ LinknewLink=newLink(key); Linkprevious=null; Linkcurrent=first; //while的第一个条件是没有到达链表的尾端,第二个是按顺序找到一个合适的位置 while(current!=null&&key>current.iData){ previous=current; current=current.next; //如果是空表或者要插入的元素最小,则在表头插入key if(current==first) first=newLink; else previous.next=newLink; newLink.next=current; *删除表头的节点 *@return要删除的节点 publicLinkremove(){ Linktemp=first; first=first.next; returntemp; publicbooleanisEmpty(){ return(first==null); publicvoiddisplayList(){ System.out.print("List(first-->last):"); Linkcurrent=first;//startatbeginningoflist while(current!=null)//untilendoflist, current.display();//printdata current=current.next;//movetonextlink System.out.println("");classSortedListApp{ publicstaticvoidmain(String[]args){//createnewlist SortedListtheSortedList=newSortedList(); theSortedList.insert(20);//insert2items theSortedList.insert(40); theSortedList.displayList();//displaylist theSortedList.insert(10);//insert3moreitems theSortedList.insert(30); theSortedList.insert(50); theSortedList.displayList();//displaylist theSortedList.remove();//removeanitem theSortedList.displayList();//displaylist双向链表classLink{ //双向链表,有两个指针,一个向前,一个向后 publicintiData=0; publicLinkprevious=null; publicLinknext=null; publicLink(intiData){ this.iData=iData; publicvoiddisplay(){ System.out.print(iData+"");classDoublyLinked{ //分别指向链表的表头和表尾 privateLinkfirst=null; privateLinklast=null; publicbooleanisEmpty(){ returnfirst==null; *在表头插入数据 *@param要插入的节点的数据 publicvoidinsertFirst(intkey){ LinknewLink=newLink(key); //如果开始链表为空,则插入第一个数据后,last也指向第一个数据 if(this.isEmpty()) last=newLink; else{//表不为空的情况 first.previous=newLink; newLink.next=first; //无论怎样,插入后都的让first重新指向第一个节点 first=newLink; publicvoidinsertLast(intkey){//在尾端插入数据,同上 LinknewLink=newLink(key); if(this.isEmpty()) first=newLink; else{ last.next=newLink; newLink.previous=last; last=newLink; *在指定的节点后插入数据 *@paramkey *指定的节点的值 *@paramiData *要插入的数据 *@return是否插入成功 publicbooleaninsertAfter(intkey,intiData){ LinknewLink=newLink(key); Linkcurrent=first; //从first开始遍历,看能否找到以key为关键字的节点 while(current.iData!=key){ current=current.next; //若能找到就跳出循环,否则返回false,插入失败 if(current==null) returnfalse; //如果插入点在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; *删除表头的节点 *@return publicLinkdeleteFirst(){ Linktemp=first; //如果表中只有一个元素,删除后则为空表,所以last=null if(first.next==null) last=null; else //否则,让第二个元素的previous=null first.next.previous=null; //删除头指针,则first指向原来的second first=first.next; returntemp; publicLinkdeleteLast(){//同上 Linktemp=last; if(last.previous==null) first=null; else last.previous.next=null; last=last.previous; returntemp; publicLinkdeleteKey(intkey){ Linkcurrent=first; //遍历整个链表查找对应的key,如果查到跳出循环,否则... while(current.iData!=key){ current=current.next; //...否则遍历到表尾,说明不存在此key,返回null,删除失败 if(current==null) returnnull; if(current==first) first=first.next; else current.previous.next=current.next; if(current==last) last=last.previous; else current.next.previous=current.previous; returncurrent; publicvoiddisplayForward(){ Linkcurrent=first; while(current!=null){ current.display(); current=current.next; System.out.println(); publicvoiddisplayBackward(){ Linkcurrent=last; while(current!=null){ current.display(); current=current.previous; System.out.println();classDoublyLinkedApp{ publicstaticvoidmain(String[]args){//makeanewlist DoublyLinkedtheList=newDoublyLinked(); theList.insertFirst(22);//insertatfront theList.insertFirst(44); theList.insertFirst(66); theList.insertLast(11);//insertatrear theList.insertLast(33); theList.insertLast(55); theList.displayForward();//displaylistforward theList.displayBackward();//displaylistbackward theList.deleteFirst();//deletefirstitem theList.deleteLast();//deletelastitem theList.deleteKey(11);//deleteitemwithkey11 theList.displayForward();//displaylistforward theList.insertAfter(22,77);//insert77after22 theList.insertAfter(33,88);//insert88after33 theList.displayForward();//displaylistforward实现二叉树前序遍历迭代器classTreeNode这个类用来声明树的结点，其中有左子树、右子树和自身的内容。

classMyTree这个类用来声明一棵树，传入根结点。这里设计的比较简单

classTreeEum这个类是树的迭代器，通过MyTree类的方法获取，这里主要就是设计它了。代码如下：

//TreeNode类，使用了泛型，由于比较简单，考试.大提示不作解释

classTreeNode<E>Enode;privateTreeNode<String>left;privateTreeNode<String>right;publicTreeNode(Ee)this(e,null,null);publicTreeNode(Ee,TreeNode<String>left,TreeNode<String>right)this.node=e;this.left=left;this.right=right;publicTreeNode<String>left()returnleft;publicTreeNode<String>right()returnright;//MyTree类，没什么功能，传入根结点构造，getEnumerator()方法获取迭代器。classMyTreeTreeNode<String>root;publicMyTree(TreeNode<String>root)this.root=root;publicTreeEnumgetEnumerator()returnnewTreeEnum(root);//这个类为迭代器，有详细解释，相信各位能看懂。在栈中用了两次泛型。importjava.util.Stack;publicclassTreeEnumprivateTreeNode<String>root;privateStack<TreeNode<String>>store;/*保存遍历左子树但未遍历右子树的结点*/privateTreeNode<String>next;publicTreeEnum(TreeNode<String>root)this.root=root;store=newStack<TreeNode<String>>();next=root;publicTreeNode<String>next()TreeNode<String>current=next;if(next!=null)/*如果当前结点的左子树不为空,则遍历左子树,并标记当前结点未遍历右子树*/if(next.left()!=null)store.push(next);next=next.left();//如果当前结点的左子树为空,则遍历右子树elseif(next.right()!=null)next=next.right();/*如果当前结点为叶子,则找未遍历右子树的结点并且遍历它的右子树*/else{if(!store.empty())/*判断是否还有结点的右子树未遍历*/TreeNode<String>tmp=store.pop();/*如果有未遍历右子树的结点,但它的右子树为空,且还有结点的右子树未遍历,*//*则一直往上取,直到取到未遍历右子树且右子树不为空的结点,遍历它的右子树.*/while((tmp.right()==null)&&!store.empty())tmp=store.pop();next=tmp.right();else/*如果没有哪个结点右子树未遍历,则表示没有下一个结点了,设置next为null*/next=null;returncurrent;publicbooleanhasMoreElement()returnnext!=null;下面写个测试类，不作解释，相信大家看得懂publicclassTreeReader{publicstaticvoidmain(String[]args)TreeNode<String>n1=newTreeNode<String>("n1");TreeNode<String>n2=newTreeNode<String>("n2");TreeNode<String>n3=newTreeNode<String>("n3");TreeNode<String>n4=newTreeNode<String>("n4");TreeNode<String>n5=newTreeNode<String>("n5");TreeNode<String>n6=newTreeNode<String>("n6",null,n1);TreeNode<String>n7=newTreeNode<String>("n7",n2,null);TreeNode<String>n8=newTreeNode<String>("n8",n7,null);TreeNode<String>n9=newTreeNode<String>("n9",null,n5);TreeNode<String>n10=newTreeNode<String>("n10",n4,n9);TreeNode<String>n11=newTreeNode<String>("n11",n6,n8);TreeNode<String>n12=newTreeNode<String>("n12",n3,n10);TreeNode<String>root=newTreeNode<String>("root",n11,n12);MyTreetree=newMyTree(root);TreeEnumeum=tree.getEnumerator();while(eum.hasMoreElement())System.out.print(eum.next().node+"--");System.out.println("end");迭代器packageTreeIterator;publicinterfaceIterator{publicbooleanhasNext();publicObjectnext();这个接口我们有2个方法，hasNext()是否还有下一条数据，next返回具体的Object这里也就是树。我们先不必要忙着做他的实现类，我们现在要来做的是这个容器（不是JAVA中容器，及arraylist什么的无关），正所谓树的容器是什么，是山也！我们想想山应该具有什么呢！？首先它要有种植树的功能，这里可以看作添加树。我们可以想像山的功能是和树相互关联的，那么他们之间是什么关系呢，我们给他们一种聚合的关系，聚合的关系大家可以参考UML图，我在这里给出它的一种程序表现形式。packageTreeIterator;publicclassHall{Tree[]tree;//这里可以看作是聚合关系privateintindex;//指向Tree[]的标签publicHall(intmaxNumber){tree=newTree[maxNumber];index=0;publicvoidadd(Treetree)this.tree[index]=tree;index++;publicIteratorconnectIterator()returnnewTreeIterator(this);这里我们定义的山可以抽象出Hall类来，Tree[]tree可以看作是山和树之间的一种聚合关系。add方法就是添加树。问题来了，山和树有了关系，那么山和迭代器有什么关系呢。它们之间肯定有一种关系。我们有了这个容器（山），就要把这个容器来实现迭代的方法：hasNext()和Next().恩这里我们可以看出，山和迭代器之间也是一种关联关系。我们就把它看成是一种聚合关系（TIP：聚合关系一种特殊的关联关系）。我们可以通过一个connectIterator方法来链接山和迭代器，接下来我们要去做一个具体的迭代类，这个具体的类中间有了hasNext()和Next()的具体实现方法packageTreeIterator;publicclassTreeIteratorimplementsIterator{privateintlast=0;privateHallhall;publicTreeIterator(Hallhall){this.hall=hall;publicbooleanhasNext(){if(last<hall.tree.length)returntrue;elsereturnfalse;publicTreenext(){Treet=hall.tree[last];last++;returnt;这里Hallhall就可以看作是一种关联关系，我们要把山和迭代器联系起来就通过构造函数来实现，hasNext和next实现方法就体现出来了有了山，有了迭代器，可是树还没有定义，不过这个树的方法还很好解决！树不关联其他的事务，我们可以简单的这么写：packageTreeIterator;publicclassTree{privateStringname;publicTree(Stringname){=name;publicStringgetName(){return;好了似乎我们整个工程完工了，我们现在来模拟一下农民老大伯来种树撒肥的过程；packageTreeIterator;publicclassPren{publicPren(){publicstaticvoidmain(String[]args){Hallhall=newHall(4);hall.add(newTree("苹果树"));hall.add(newTree("梨树"));hall.add(newTree("橘子树"));hall.add(newTree("凤梨树"));for(Iteratori=hall.connectIterator();i.hasNext();){StringType=((Tree)(i.next())).getName();if(Type=="苹果树"){System.out.println("洒苹果树的农药,");if(Type=="梨树"){System.out.println("洒梨树的农药");if(Type=="橘子树"){System.out.println("洒橘子树的农药,洒了也没用,还没到成熟日,现在没结果实");if(Type=="凤梨树"){System.out.println("南风天，湿气大，让它烂在地里吧");种4个树，山小而五脏俱全，更像一个土包，再要有树才行啊，所以4个树的实例出现。好了接下来种树，几毫秒解决！山了有我们就要把山放到迭代器中间去了。遍历这个山（容器）。联想我们看看arrayList中的迭代器模式是怎么实现的！ArrayLista=newArrayList();a.add("a1");a.add("a2");a.add("a3");a.add("a4");for(Iteratori=a.iterator();i.hasNext();)System.out.println(i.next().toString());合并搜索算法publicclassMergeSortArray{ privatelong[]theArray; privateintnElems; publicMergeSortArray(intmax){ theArray=newlong[max]; nElems=0; publicvoidinsert(longvalue){ theArray[nElems]=value;//insertit nElems++;//incrementsize publicvoiddisplay(){ for(intj=0;j<nElems;j++) System.out.print(theArray[j]+""); System.out.println(""); publicvoidmergeSort(){ long[]workSpace=newlong[nElems]; recMergeSort(workSpace,0,nElems-1); privatevoidrecMergeSort(long[]workSpace,intlowerBound,intupperBound){ if(lowerBound==upperBound)//ifrangeis1, return;//nousesorting else{//findmidpoint intmid=(lowerBound+upperBound)/2; //sortlowhalf recMergeSort(workSpace,lowerBound,mid); //sorthighhalf recMergeSort(workSpace,mid+1,upperBound); //mergethem merge(workSpace,lowerBound,mid+1,upperBound); privatevoidmerge(long[]workSpace,intlowPtr,inthighPtr,intupperBound){ intj=0;//workspaceindex intlowerBound=lowPtr; intmid=highPtr-1; intn=upperBound-lowerBound+1;//#ofitems while(lowPtr<=mid&&highPtr<=upperBound) if(theArray[lowPtr]<theArray[highPtr]) workSpace[j++]=theArray[lowPtr++]; else workSpace[j++]=theArray[highPtr++]; while(lowPtr<=mid) workSpace[j++]=theArray[lowPtr++]; while(highPtr<=upperBound) workSpace[j++]=theArray[highPtr++]; for(j=0;j<n;j++) theArray[lowerBound+j]=workSpace[j]; publicstaticvoidmain(String[]args){ intmaxSize=100;//arraysize MergeSortArrayarr=newMergeSortArray(maxSize);//createthearray arr.insert(14); arr.insert(21); arr.insert(43); arr.insert(50); arr.insert(62); arr.insert(75); arr.insert(14); arr.insert(2); arr.insert(39); arr.insert(5); arr.insert(608); arr.insert(36); arr.display(); arr.mergeSort(); arr.display();递归publicclassRecursion{ *@paramargs publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub Recursionre=newRecursion(); System.out.println(re.RecursionNum(10)); publicintRecursionNum(intnum) if(num>0){ returnnum+RecursionNum(num-1); Else{ return0;归并排序*归并排序，要求待排序的数组必须实现Comparable接口publicclassMergeSortimplementsSortStrategy{ privateComparable[]bridge; *利用归并排序算法对数组obj进行排序 publicvoidsort(Comparable[]obj){ if(obj==null){ thrownewNullPointerException("Theparamcannotbenull!"); bridge=newComparable[obj.length];//初始化中间数组 mergeSort(obj,0,obj.length-1);//归并排序 bridge=null; *将下标从left到right的数组进行归并排序 *@paramobj *要排序的数组的句柄 *@paramleft *要排序的数组的第一个元素下标 *@paramright *要排序的数组的最后一个元素的下标 privatevoidmergeSort(Comparable[]obj,intleft,intright){ if(left<right){ intcenter=(left+right)/2; mergeSort(obj,left,center); mergeSort(obj,center+1,right); merge(obj,left,center,right); *将两个对象数组进行归并，并使归并后为升序。归并前两个数组分别有序 *@paramobj *对象数组的句柄 *@paramleft *左数组的第一个元素的下标 *@paramcenter *左数组的最后一个元素的下标 *@paramright *右数组的最后一个元素的下标 privatevoidmerge(Comparable[]obj,intleft,intcenter,intright){ intmid=center+1; intthird=left; inttmp=left; while(left<=center&&mid<=right){//从两个数组中取出小的放入中间数组 if(obj[left]pareTo(obj[mid])<=0){ bridge[third++]=obj[left++]; }else bridge[third++]=obj[mid++]; //剩余部分依次置入中间数组 while(mid<=right){ bridge[third++]=obj[mid++]; while(left<=center){ bridge[third++]=obj[left++]; //将中间数组的内容拷贝回原数组 copy(obj,tmp,right); *将中间数组bridge中的内容拷贝到原数组中 *@paramobj *原数组的句柄 *@paramleft *要拷贝的第一个元素的下标 *@paramright *要拷贝的最后一个元素的下标 privatevoidcopy(Comparable[]obj,intleft,intright){ while(left<=right){ obj[left]=bridge[left]; left++;希尔排序间隔序列：h=3*h+1，h=(h-1)/3publicclassShellSort{ *@paramargs publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub ShellSortss=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;i<num.length;i++){ System.out.println(num[i]); publicvoidshellArray(int[]num){ inti=1; inttem,in; for(;i<num.length/3;){ i=3*i+1; for(;i>=1;){ for(intj=i;j<num.length;j++){ tem=num[j]; in=j; while(in>i-1&&num[in-i]>=tem){ num[in]=num[in-i]; in=in-i; num[in]=tem; i=(i-1)/3;快速排序classQuickSort{ privateint[]data; QuickSort(int[]data){ this.data=data; publicvoidquickSort(){ recQuickSort(data,0,data.length-1); privatevoidrecQuickSort(int[]data,intlow,inthigh){ //设置两个滑标 intlowCursor=low+1; inthighCursor=high; //交换时的临时变量 inttemp=0; //比较枢值,设为数组的第一个值 intmedi=data[low]; while(true){ //从低端开始查找，确定大于数data[low]所在的位置 while(lowCursor<high&&data[lowCursor]<medi){ lowCursor++; //从高端开始查找，确定小于数data[low]所在的位置。这里要使用>=判断确定小于值 while(highCursor>low&&data[highCursor]>=medi){ highCursor--; //两游标位置出现越界，退出循环 if