排序和查找程序小结.docx

该【排序和查找程序小结 】是由【dllw1314】上传分享，文档一共【6】页，该文档可以免费在线阅读，需要了解更多关于【排序和查找程序小结 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。顺序查找publicstaticintSequentialSearch(int[]a,intx){ inti; for(i=0;i<&&a[i]!=x;i++) ; if(i==) return-1; else returni;}二分查找parable[]parablex){ intlow=0,high=-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<;i++) Insert(list,i); } template<classType>voidInsert(datalist<Type>&list,inti){ Element<Type>temp=[i];intj=i; while(j>0&&()<[j-1].getkey()){ [j]=[j-1];j-- } [j]=temp; } parable[]a){ intj; for(intp=1;p<;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<;i++) for(intj=i;j<;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<;i++){ intthisSum=0; for(intj=i;j<;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,-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]; }约瑟夫环问题rear:每次指向要出队列的前一个结点出队列的人也用链表来表示:head:指向出队列结点链表的开头结点p:指向出队列结点链表的尾结点以上rear,head,p都是ListNode的一个对象引用。=m;(inti=1;i<=n-1;i++){1)for(intj=1;j<=w-1;j++)rear=;2)if(i==1){ head=;p=head;}else{ =;p=;}3)=;}=rear;=null;voidYANGHUI(intn){Queue<int>q;();(1);(1);ints=0;for(inti=1;i<=n;i++){cout<<endl;for(intk=1;k<=10-i;k++)cout<<??;(0);for(intj=1;j<=i+2;j++){intt=();(s+t);s=t;if(j!=i+2)cout<<s<<??;}}}Printthecoefficientsofthebinomialexpansion用可变长度的二维数组来实现:lassYanghui{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]=1;for(j=1;j<i;j++)mat[i][j]=mat[i-1][j-1]+mat[i-1][j];}for(i=0;i<;i++){for(j=0;j<n-i;j++)(““);for(j=0;j<mat[i].length;j++)(““+mat[i][j]);();}}}