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

1.大O表示法：粗略的量度方法即算法的速度是如何与数据项的个数相关的算法大O表示法表示的运行时间线性查找O(N)二分查找O(logN)无序数组的插入O(1)有序数组的插入O(N)无序数组的删除O(N)有序数组的删除O(N)O(1)是最优秀的,O(logN)良好,O(N)还可以,O(N2)稍差(在冒泡法中见到)2.排序publicclassJWzw{//插入排序publicvoidinsertArray(Integer[]in){inttem=0;intnum=0;intupnum=0;for(inti=0;iin.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;iin.length;i++){System.out.print(in[i]);if(iin.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;iin.length;i++){for(intj=i;jin.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;iin.length;i++){System.out.print(in[i]);if(iin.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;iin.length;i++){for(intj=i;jin.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;iin.length;i++){System.out.print(in[i]);if(iin.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;j10;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;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){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(10002);}}3.优先级队列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(la[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{//队列操作类/***@paramargs*/privateinti=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++;}4.队列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;n4;n++){m.del();}}publicintgetI(){returni;}publicduiliegetEnd(){returnend;}publicduiliegetTop(){returntop;}}5.栈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;ilen;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;}}6.链表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;}}7.单链表classNode//节点类，单链表上的节点{Stringdata;//数据域，存放String类的数据Nodenext;//