c++常见排序算法.docx
- 文档编号:4096299
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:18
- 大小:17.26KB
c++常见排序算法.docx
《c++常见排序算法.docx》由会员分享,可在线阅读,更多相关《c++常见排序算法.docx(18页珍藏版)》请在冰点文库上搜索。
c++常见排序算法
/**<气泡排序,快速排序,插入排序,希尔排序,
选择排序,堆排序,归并排序,基数排序*/
#include
#include
#defineMax100000000
usingnamespacestd;
template
classSortR
{
public:
SortR()
{
arr=newT[Max];
}
~SortR(){
delete[]arr;
}
voidInputValue();
voidBubbleSort();//冒泡排序
voidQuickSort();//快速排序
voidInsertSort();//插入排序
voidHillSort();//希尔排序
voidSelectSort();//选择排序
voidHeapSort();//堆排序
voidMergeSort();//归并排序
voidBaseSort();//基数排序
voidDisplay(T*);//输出排序结果
private:
voidSwap(T*,T*)const;
intfindPivot(int,int,T*)const;
intPartition(int,int,T,T*)const;
voidQuickSortRev(int,int,T*);//快排递归
voidPushDown(int,int,T*)const;//堆排序,整理堆
voidMerge_array(T*,int,int,int,T*);//合并两个数组
voidmerge_sort(T*,int,int,T*);//归并排序,递归实现
TGetDigit(Tx,intd);
voidmsdradix_sort(T*,int,int,int);
T*arr;
intn;
};
template
voidSortR
:
InputValue()
{
cout<<"输入数组大小:
";
//cin>>n;
n=10000;
cout<<"输入数组元素:
";
srand((T)time(NULL));
for(inti=0;i //cin>>arr[i]; arr[i]=rand()%100000; } template voidSortR : Swap(T*t1,T*t2)const//交换 { Ttemp; temp=*t1; *t1=*t2; *t2=temp; } /**<--------冒泡排序-------*/ template voidSortR : BubbleSort() { //---时间测试 clock_tstart,finish; doubletotaltime; start=clock(); //---------------------------------------------------- T*bubble_arr=newT[n]; for(inti=0;i bubble_arr[i]=arr[i]; for(inti=0;i { for(intj=n-1;j>i;j--) { if(bubble_arr[j] Swap(&bubble_arr[j],&bubble_arr[j-1]); } } finish=clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC; cout<<"运行时间: "< //Display(bubble_arr); //Display(arr); } /**<-------快速排序--------*/ template intSortR : findPivot(inti,intj,T*quick_arr)const { Tfirstkey; intk; firstkey=quick_arr[i]; for(k=i+1;k<=j;k++) { if(quick_arr[k]>firstkey)returnk; elseif(quick_arr[k] elsereturn-1;//没有不同关键字 } return0; } template intSortR : Partition(inti,intj,Tpiovt,T*quick_arr)const { intl=i,r=j; do{ Swap(&quick_arr[l],&quick_arr[r]); while(quick_arr[l] while(quick_arr[r]>=piovt)r--; }while(l<=r); returnl; } template voidSortR : QuickSortRev(inti,intj,T*quick_arr) { Tpiovt; intpiovtindex; intk; piovtindex=findPivot(i,j,quick_arr); if(piovtindex>=0) { piovt=quick_arr[piovtindex]; k=Partition(i,j,piovt,quick_arr); //Display(quick_arr);//输出 return; QuickSortRev(i,k-1,quick_arr); QuickSortRev(k,j,quick_arr); } } template voidSortR : QuickSort() { //---时间测试 clock_tstart,finish; doubletotaltime; start=clock(); T*quick_arr=newT[n]; for(inti=0;i quick_arr[i]=arr[i]; QuickSortRev(0,n-1,quick_arr); //----------- finish=clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC; cout<<"运行时间: "< //Display(arr); } /*------插入排序------*/ template voidSortR : InsertSort()//插入排序 { //---时间测试 clock_tstart,finish; doubletotaltime; start=clock(); T*insert_arr=newT[n]; for(inti=0;i insert_arr[i+1]=arr[i]; insert_arr[0]=-1; for(inti=1;i { intj=i; while(insert_arr[j] { Swap(&insert_arr[j],&insert_arr[j-1]); j--; } } //----------- finish=clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC; cout<<"运行时间: "< //for(inti=1;i<=20;i++) //cout< //cout< //Display(arr); } /*-------希尔排序-----------*/ template voidSortR : HillSort() { //---时间测试 clock_tstart,finish; doubletotaltime; start=clock(); T*hill_arr=newT[n]; for(inti=0;i hill_arr[i]=arr[i]; intj,gap; for(gap=n/2;gap>0;gap/=2) for(j=gap;j { if(hill_arr[j] { Ttemp=hill_arr[j]; intk=j-gap; while(k>=0&&hill_arr[k]>temp) { hill_arr[k+gap]=hill_arr[k]; k-=gap; } hill_arr[k+gap]=temp; } } //Display(hill_arr); //----------- finish=clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC; cout<<"运行时间: "< } /*--------选择排序--------*/ template voidSortR : SelectSort() { //---时间测试 clock_tstart,finish; doubletotaltime; start=clock(); T*select_arr=newT[n]; for(inti=0;i select_arr[i]=arr[i]; Tminindex;//存储最小的元素 for(inti=0;i { minindex=select_arr[i]; for(intj=i+1;j { if(select_arr[j] { minindex=select_arr[j]; } } Swap(&select_arr[i],&minindex); } //Display(select_arr); //----------- finish=clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC; cout<<"运行时间: "< } /*--------堆排序---------*/ template voidSortR : PushDown(intfirst,intlast,T*heap_arr)const { intr; r=first; while(r<=last/2) if((r==last/2)&&(last%2==0))//r有一个儿子,在2*r { if(heap_arr[r]>heap_arr[2*r]) Swap(&heap_arr[2*r],&heap_arr[r]); r=last; } elseif((heap_arr[r]>heap_arr[2*r])&&(heap_arr[2*r]<=heap_arr[2*r+1])) {//r与左儿子交换 Swap(&heap_arr[2*r],&heap_arr[r]); r=2*r; } elseif((heap_arr[r]>heap_arr[2*r+1])&&(heap_arr[2*r+1]<=heap_arr[2*r])) {//r与右儿子交换 Swap(&heap_arr[2*r+1],&heap_arr[r]); r=r*2+1; } elser=last; } template voidSortR : HeapSort() { //---时间测试 clock_tstart,finish; doubletotaltime; start=clock(); T*heap_arr=newT[n]; for(inti=0;i heap_arr[i+1]=arr[i]; inti; for(i=n/2;i>=1;i--) PushDown(i,n,heap_arr); for(i=n;i>1;i--) { Swap(&heap_arr[1],&heap_arr[i]); PushDown(1,i-1,heap_arr); } //----------- finish=clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC; cout<<"运行时间: "< /*for(inti=n;i>0;i--) cout< cout< } /*----------归并排序-----------*/ template voidSortR : Merge_array(T*merge_arr,intfirst,intmidle,intlast,T*temp) { inti=first,j=midle+1; intm=midle,l=last,k=0; while(i<=m&&j<=l) { if(merge_arr[i]<=merge_arr[j]) temp[k++]=merge_arr[i++]; else temp[k++]=merge_arr[j++]; } while(i<=m) temp[k++]=merge_arr[i++]; while(j<=l) temp[k++]=merge_arr[j++]; for(i=0;i merge_arr[first+i]=temp[i]; } template voidSortR : merge_sort(T*merge_arr,intfirst,intlast,T*temp) { if(first { intmid=(first+last)/2; merge_sort(merge_arr,first,mid,temp); merge_sort(merge_arr,mid+1,last,temp); Merge_array(merge_arr,first,mid,last,temp); } } template voidSortR : MergeSort() { //---时间测试 clock_tstart,finish; doubletotaltime; start=clock(); T*merge_arr=newT[n]; for(inti=0;i merge_arr[i+1]=arr[i]; T*p=newT[n]; merge_sort(merge_arr,1,n,p); //----------- finish=clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC; cout<<"运行时间: "< /*for(inti=1;i<=n;i++) cout< cout< } /*---------基数排序------------*/ template TSortR : GetDigit(Tx,intd) { inta[]={1,1,10};//排的是100以内的 return(x/a[d])%10; } template voidSortR : msdradix_sort(T*base_arr,intfirst,intlast,intd) { intradix=10; intcount[10],i,j; for(i=0;i count[i]=0; T*bucker=newT[n]; for(i=first;i<=last;i++) count[GetDigit(base_arr[i],d)]++; for(i=1;i count[i]+=count[i-1]; for(i=last;i>=first;--i) { j=GetDigit(base_arr[i],d); bucker[count[j]-1]=base_arr[i]; --count[j]; } for(i=first,j=0;i<=last;i++,j++) base_arr[i]=bucker[j]; for(i=0;i { intp1=first+count[i]; intp2=first+count[i+1]-1; if(p1 msdradix_sort(base_arr,p1,p2,d-1); } } template voidSortR : BaseSort() { /*cout<<"输入所要排的数(先默认0-99的,n值还是最开始的): "< T*base_arr=newT[n]; for(inti=0;i cin>>base_arr[i];*/ //---时间测试 clock_tstart,finish; doubletotaltime; start=clock(); T*base_arr=newT[n]; for(inti=0;i base_arr[i]=arr[i]; msdradix_sort(base_arr,0,n-1,2); //----------- finish=clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC; cout<<"运行时间: "< cout<<"排序结果: "< //Display(base_arr); } /*----------输出函数---------*/ template voidSortR : Display(T*newarray) { for(inti=0;i<20;i++) cout< cout< } /*--------主函数-----------*/ intmain() { cout<<"排序方法(从小到大): "< SortR mysort.InputValue(); cout<<"气泡排序: "< mysort.BubbleSort(); cout<<"快速排序: "< mysort.QuickSort(); cout<<"插入排序: "< mysort.InsertSort(); cout<<"希尔排序: "< mysort.HillSort(); cout<<"选择排序: "< mysort.SelectSort(); cout<<"堆排序: "< mysort.HeapSort(); cout<<"归并排序: "< mysort.MergeSort(); cout<<"基数排序: "< mysort.BaseSort(); system("pause"); return0; } /*
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- c+ 常见 排序 算法