排序和查找程序小結(jié)

順序查找publicstaticintSequentialSearch(int[]a,intx){ inti; for(i=0;i<a.length&&a[i]!=x;i++) ; if(i==a.length) return-1; else returni;}二分查找publicstaticintbinarySearch(Comparable[]a,Comparablex){ intlow=0,high=a.length-1; while(low<=high){ intmid=(low+high)/2; if(a[mid].compareTo(x)<0) low=mid+1; elseif(a[mid].compareTo(x)>0) high=mid-1; else returnmid; } return-1; }插入排序template<classType>voidInsertionSort(datalist<Type>&list){ for(inti=1;i<list.CurrentSize;i++) Insert(list,i); } template<classType>voidInsert(datalist<Type>&list,inti){ Element<Type>temp=list.vector[i];intj=i; while(j>0&&temp.getkey()<list.vector[j-1].getkey()){ list.Vector[j]=list.Vector[j-1];j-- } list.Vector[j]=temp; } publicstaticvoidinsertionSort(Comparable[]a){ intj; for(intp=1;p<a.length;p++){ Comparabletmp=a[p]; for(j=p;j>0&&pareTo(a[j–1])<0;j--) a[j]=a[j-1]; a[j]=tmp; } }折半插入排序（二分法插入排序）選擇排序publicstaticvoidSelectionSort(int[]a,intn){ //sortthennumberina[0:n-1]. for(intsize=n;size>1;size--){ intj=Max(a,size); swap(a[j],a[size-1]); }}冒泡排序publicstaticvoidBubbleSort(int[]a,intn){ //Sorta[0:n-1]usingabubblesort for(inti=n;i>1;i--) Bubble(a,i);}publicstaticvoidBubble(int[]a,intn){ //Bubblelargestelementina[0:n-1]toright for(inti=0;i<n-1;i++){ if(a[i]>a[i+1]) swap(a[i],a[i+1]); }}秩排序publicstaticvoidRank(int[]a,intn,int[]r){ //Rankthenelementsa[0:n-1] for(inti=0;i<n;i++) r[i]=0; for(inti=1;i<n;i++){ for(intj=0;j<i;j++){ if(a[j]<=a[i]) r[i]++; else r[j]++; } } }publicstaticvoidRearrange(int[]a,intn,int[]r){ //In-placerearrangementintosortedorder for(inti=0;i<n;i++){ while(r[i]!=i){ intt=r[i]; swap(a[i],a[t]); swap(r[i],r[t]); } }}最大子序列和Algorithm1:publicstaticintmaxSubSum1(int[]a){ intmaxSum=0; for(inti=0;i<a.length;i++) for(intj=i;j<a.length;j++){ intthisSum=0; for(intk=i;k<=j;k++) thisSum+=a[k]; if(thisSum>maxSum) maxSum=thisSum; } returnmaxSum; }O(N3)Algorithm2:publicstaticintmaxSubSum2(int[]a){ intmaxSum=0; for(inti=0;i<a.length;i++){ intthisSum=0; for(intj=i;j<a.length;j++){ thisSum+=a[j]; if(thisSum>maxSum) maxSum=thisSum; } } returnmaxSum; }O(N2)Algorithm3:privatestaticintmaxSumRec(int[]a,intleft,intright){ if(left==right) if(a[left]>0) returna[left]; else return0; intcenter=(left+right)/2; intmaxLeftSum=maxSumRec(a,left,center); intmaxRightSum=maxSumRec(a,center+1,right); intmaxLeftBorderSum=0,leftBorderSum=0; for(inti=center;i>=left;i--){ leftBorderSum+=a[i]; if(leftBorderSum>maxLeftBorderSum) maxLeftBorderSum=leftBorderSum; } intmaxRightBorderSum=0,rightBorderSum=0; for(inti=center+1;i<=right;i++){ rightBorderSum+=a[i]; if(rightBorderSum>maxRightBorderSum) maxRightBorderSum=rightBorderSum; } returnmax3(maxLeftSum,maxRightSum,maxLeftBorderSum +maxRightBorderSum); } publicstaticintmaxSubSum3(int[]a){ returnmaxSumRec(a,0,a.length-1); }O(NlogN)找一個序列中第k小的元素intselectkth(inta[],intk,intn){ inti,j,mini,temp; for(i=0;i<k;i++){ mini=i; for(j=i+1;j<n;j++) if(a[j]<a[mini]) mini=j; tmp=a[i]; a[i]=a[mini]; a[mini]=tmp; } returna[k-1]; }約瑟夫環(huán)問題rear:每次指向要出隊列的前一個結(jié)點出隊列的人也用鏈表來表示：head:指向出隊列結(jié)點鏈表的開頭結(jié)點p:指向出隊列結(jié)點鏈表的尾結(jié)點以上rear,head,p都是ListNode的一個對象引用。1.w=m;2.for(inti=1;i<=n-1;i++){1)for(intj=1;j<=w-1;j++)rear=rear.link;2)if(i==1){ head=rear.link;p=head;}else{ p.link=rear.link;p=rear.link;}3)rear.link=p.link;}3.P.link=rear;rear.link=null;voidYANGHUI(intn){Queue<int>q;q.makeEmpty();q.Enqueue(1);q.Enqueue(1);ints=0;for(inti=1;i<=n;i++){cout<<endl;for(intk=1;k<=10-i;k++)cout<<??;q.Enqueue(0);for(intj=1;j<=i+2;j++){intt=q.Dequeue();q.Enqueue(s+t);s=t;if(j!=i+2)cout<<s<<??;}}}Printthecoefficientsofthebinomialexpansion用可變長度的二維數(shù)組來實現(xiàn)：publicclassYanghui{publicstaticvoidmain(Stringargs[]){intn=10;intmat[][]=newint[n][];//申請第一維的存儲空間inti,j;for(i=0;i<n;i++){mat[i]=newint[i+1];//申請第二維的存儲空間，每次長度不同mat[i][0]=1;mat[i][i]=