排序.docx
- 文档编号:13329290
- 上传时间:2023-06-13
- 格式:DOCX
- 页数:15
- 大小:16.10KB
排序.docx
《排序.docx》由会员分享,可在线阅读,更多相关《排序.docx(15页珍藏版)》请在冰点文库上搜索。
排序
#include
#include
usingnamespacestd;
intInsertSort(int*array,intsize);//
intMergeSort(int*array,intsize);//
intBubbleSort(int*array,intsize);//
intQuickSort(int*array,intsize);//
intHeepSort(int*array,intsize);//
intCountingSort(int*array,intsize);//
intRadixSort(int*array,intsize);//
intBucketSort(int*array,intsize);//
intShellSort(int*array,intsize);//
voidshowArray(int*array,intsize);//
intmain()
{
//intarray[10]={23,54,7,76,321,6,345,12,7,54};
//intarray[10]={2,5,7,6,2,6,3,1,7,5};//countingsortdata
intarray[10]={23,54,73,64,25,66,34,13,72,51};//Radixsortdataandbucketsortdata
intsize=10;
cout<<"Sortingthedatafromlowtohigh:
"< cout<<"Beforesorting: "< showArray(array,size); cout<<"InsertSorting: "< InsertSort(array,size); showArray(array,size); cout<<"BubbleSorting: "< BubbleSort(array,size); showArray(array,size); cout<<"QuickSorting: "< QuickSort(array,size); showArray(array,size); cout<<"MergeSorting: "< MergeSort(array,size); showArray(array,size); cout<<"HeepSorting: "< HeepSort(array,size); showArray(array,size); cout<<"CountingSorting: "< CountingSort(array,size); showArray(array,size); cout<<"RadixSorting: "< RadixSort(array,size); showArray(array,size); cout<<"ShellSorting: "< ShellSort(array,size); showArray(array,size); cout<<"BucketSorting: "< BucketSort(array,size); showArray(array,size); return1; } voidshowArray(int*array,intsize) { for(inti=0;i { cout< } cout< } intInsertSort(int*array,intsize) { if(size<2) return1; inttempValue; for(inti=1;i { tempValue=array[i]; intj=i-1; while(j>=0&&array[j]>tempValue)//shouldcomparewiththetempValue,notarray[i] { array[j+1]=array[j]; j--; } array[j+1]=tempValue; } return1; } #defineMAXVALUE98999 voidMerge(int*array,intstart,intmiddle,intend) { intleftLength=middle-start+1; intrightLength=end-middle; intsumLength=end-start+1; int*leftArray=newint[leftLength+1]; int*rightArray=newint[rightLength+1]; inti=0; intj=0; for(;i leftArray[i]=array[start+i]; leftArray[leftLength]=MAXVALUE; for(;j rightArray[j]=array[middle+j+1]; rightArray[rightLength]=MAXVALUE; i=0;j=0; for(intk=0;k { if(leftArray[i]<=rightArray[j]) { array[start+k]=leftArray[i]; i++; } else { array[start+k]=rightArray[j]; j++; } } } voidMergeSort1(int*array,intstart,intend) { if(start { intmiddle=(start+end)/2; MergeSort1(array,start,middle); MergeSort1(array,middle+1,end); Merge(array,start,middle,end); } } intMergeSort(int*array,intsize) { intmiddle=(size-1)/2; MergeSort1(array,0,size-1); return1; } intBubbleSort(int*array,intsize) { for(inti=0;i { for(intj=0;j { if(array[j+1] { inttemp=array[j]; array[j]=array[j+1]; array[j+1]=temp; } } } return1; } intPartition(int*array,intstart,intend) { inttempValue=array[start]; intj=start; for(inti=start+1;i<=end;i++) { if(array[i]<=tempValue) { j++; intt=array[i]; array[i]=array[j]; array[j]=t; } } intt=array[j]; array[j]=array[start]; array[start]=t; returnj; } voidQuickSort1(int*array,intstart,intend) { if(start { intmiddleIndex=Partition(array,start,end); QuickSort1(array,0,middleIndex-1); QuickSort1(array,middleIndex+1,end); } } intQuickSort(int*array,intsize) { QuickSort1(array,0,size-1); return1; } voidHeep(int*array,intstart,intsize) { intleaf=2*start+1; if(leaf leaf++; if(leaf<=size-1&&array[start] { inttemp=array[start]; array[start]=array[leaf]; array[leaf]=temp; Heep(array,leaf,size); } } voidBuildHeep(int*array,intsize) { for(inti=size/2;i>=0;i--) Heep(array,i,size); } voidHeepSort1(int*array,intsize) { BuildHeep(array,size); for(inti=0;i { inttemp=array[0]; array[0]=array[size-1-i]; array[size-1-i]=temp; Heep(array,0,size-i-1); } } intHeepSort(int*array,intsize) { HeepSort1(array,size); return1; } intCountingSort(int*array,intsize) { intmax=0; inti=0; int*mArray=newint[size]; //findthemaxvalueofthedata for(i=0;i { mArray[i]=array[i]; if(array[i]>max) max=array[i]; } int*countArray=newint[max+1];//allocthememeryaddresstothecountArray for(i=0;i countArray[i]=-1; for(i=0;i countArray[array[i]]=0; for(i=0;i countArray[array[i]]=countArray[array[i]]+1; intsign=0; intfirst=0; for(i=0;i { inttemp=countArray[i]; if(temp>=0) { first++; if(first! =1) countArray[i]+=countArray[sign]; sign=i; } } for(i=0;i { array[countArray[mArray[i]]-1]=mArray[i]; countArray[mArray[i]]--; } return1; } intRadixSort1(int*array,intsize,intweiShu) { int*mArray=newint[size];//recordthe0-9everyloop int*tempArray=newint[size];//thecopyofthearray int*yuShuArray=newint[size];//recordtheyushueveryloop int*yuShuArray2=newint[size];//thecopyoftheyuShu inti=0; for(i=0;i { yuShuArray[i]=array[i]; } for(intk=0;k { for(intj=0;j { tempArray[j]=array[j]; mArray[j]=yuShuArray[j]%10; yuShuArray[j]=yuShuArray[j]/10; yuShuArray2[j]=yuShuArray[j]; } intmax=0; for(i=0;i { if(array[i]>max) max=array[i]; } int*countArray=newint[max+1]; for(i=0;i countArray[i]=0; for(i=0;i countArray[mArray[i]]=countArray[mArray[i]]+1; for(i=1;i { countArray[i]+=countArray[i-1]; } for(i=size-1;i>=0;i--) { array[countArray[mArray[i]]-1]=tempArray[i]; yuShuArray[countArray[mArray[i]]-1]=yuShuArray2[i]; countArray[mArray[i]]--; } } return1; } intRadixSort(int*array,intsize) { RadixSort1(array,size,2); return1; } intBucketSort(int*array,intsize) { structbucketItem { intvalue; bucketItem*next; }; inti=0; bucketItem*bucket=newbucketItem[10]; for(i=0;i<10;i++) { bucket[i].value=-1; bucket[i].next=NULL; } bucketItem*largerPoint=newbucketItem(); bucketItem*lowerPoint=newbucketItem(); for(i=0;i { inttempValue=array[i]/10; largerPoint=bucket[tempValue].next; lowerPoint=largerPoint; bucketItem*item=newbucketItem(); item->value=array[i]; item->next=NULL; if(largerPoint==NULL) { bucket[tempValue].next=item; continue; }elseif(largerPoint->value>array[i]) { item->next=largerPoint; bucket[tempValue].next=item; continue; } while(largerPoint! =NULL&&largerPoint->value { lowerPoint=largerPoint; largerPoint=largerPoint->next; } item->next=lowerPoint->next; lowerPoint->next=item; } intj=0; for(i=0;i<10;i++) { largerPoint=bucket[i].next; while(largerPoint! =NULL) { array[j]=largerPoint->value; largerPoint=largerPoint->next; j++; } } return1; } voidShellSort1(int*array,intsize,intstep) { for(inti=0;i { for(intj=step;j { intk=j; inttemp=array[k]; while(k>=step&&temp { array[k]=array[k-step]; k=k-step; } array[k]=temp; } } } intShellSort(int*array,intsize) { intsteps[3]={5,3,1}; for(inti=0;i<3;i++) ShellSort1(array,size,steps[i]); return1; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排序