数据结构作业——排序

1、数据结构作业排序数据结构作业化化排序介绍实现了冒泡排序、插入排序及其几种优化、选择排序、希尔排序、快速排序、归并排序。代码实现|includeincludeincludeincludeincludeincludeincludeincludeincludeincludeincludeincludeusingnamespacestd;Idefinefori(i,a,b)for(inti=(a);i=(b);i_)definemem(a,b)memset(a),(b),sizeof(a);defineall(x)(x).begin(),(x).end()templatevclassT,classT2

2、boolckmax(T&a,T2b)returnaboolckmin(T&a,T2b)returnab?a=b,1:0;”pedeflonglongll;constintmaxn=2e5+8;void_swap(int*a,int*b)inttemp=*a;*a=*b;*b=temp;I冒泡排序voidbubble_sort(int*_begin,int*_end)for(int*p=_begin;p!=_end;p+)for(int*p2=p+1;p2!=_end;p2+)if(*p2*p)_swap(p,p2);I插入排序voidinsertion_sort(int*_begin,int*

3、_end)for(int*p=_begin+1;p_begin;p2-)if(*(p2-1)*p2)_swap(p2-1,p2);elsebreak;I折半插入排序voidbinary_insertion_sort(int*_begin,int*_end)int*l,*r,*mid,temp;for(int*p=_begin+1;p_end;p+)temp=*p;l=_begin,r=p-1;while(l=r)mid=丨+(r-l)/2;if(*midl;p2-)*p2=*(p2-1);*l=temp;2-路插入排序voidtwo_ways_insertion_sort(int*_begin

4、,int*_end)if(_end-_begin2)return;int*arr=(int*)malloc(sizeof(int)*(_end-_begin);int*_first=arr+(_end-_begin-1),*_last=arr,Inum=1,rnum=1;*_first=min(*_begin,*(_begin+1);*_last=max(*_begin,*(_begin+1);for(int*p=_begin+2;p*_last)*(+_last)=*p,lnum+;elseif(*p*_first)*(-irst)=*p,rnum+;elseif(lnumarr;p2-)i

5、f(*p2*(p2-1)_swap(p2,p2-1);lnum+;else*(-_first)=*p;for(int*p2=irst;p2*(p2+1)_swap(p2,p2+1);rnum+;for(int*p=_begin,*p2=arr;p2=_last|_first_last)*(p+)=*(_first+);elseif(_first=arr+(_end-_begin)*(p+)=*(p2+);elseif(*p2*irst)*(p+)=*(_first+);else*(p+)=*(p2+);free(arr);I/希尔排序voidinsertion_sort2(int*_begin

6、,int*_end,intdelta)for(int*p=_begin+delta;p_begin;p2-=delta)if(*(p2-delta)*p2)_swap(p2-delta,p2);elsebreak;voidshell_sort(int*_begin,int*_end)for(intdelta=_end-_begin;delta;delta=1)for(inti=0;idelta;i+)insertion_sort2(_begin+i,_end,delta);I/选择排序voidselect_sort(int*_begin,int*_end)int*temp;for(int*p=

7、_begin;p!=_end;p+)for(int*p2=temp=p;p2_end;p2+)if(*p2=_end)return;inttemp=*_begin;int*p=_begin,*p2=_end-1;while(pp2)while(p=temp)p2-;while(p=temp)p2-Hif(Pp2)_swap(p,p2);P+；while(pp2&*ptemp)p+;if(p=_end)return;int*mid=_begin+(_end-_begin)/2;merge_sort(_begin,mid);merge_sort(mid,_end);int*arr=(int*)ma

8、lloc(sizeof(int)*(_end-_begin);intcnt=0;int*pl=_begin,*pr=mid,*p=arr;while(plmid|pr=_end)*(p+)=*(pl+);elseif(pl=mid)*(p+)=*(pr+);elseif(*pl*pr)*(p+)=*(pl+);else*(p+)=*(pr+);cnt+;for(p=_begin;p_end;p+)*p=*(arr+(p-_begin);free(arr);intamaxn;intmain(void)intn,com;puts(请输入数据个数:);scanf(%d,&n);printf(请输入d

9、个数据:n,n);fori(i,0,n)scanf(%d,&ai);puts(请选择用什么排序:);puts(1.冒泡排序);puts(2.插入排序”)；puts(3.折半插入排序”)；puts(4.2-路插入排序”)；puts(5.希尔排序”)；puts(6.选择排序);puts(7.快速排序”)；puts(8归并排序”)；scanf(%d,&com);if(com=1)bubble_sort(a,a+n);elseif(com=2)insertion_sort(a,a+n);elseif(com=3)binary_insertion_sort(a,a+n);elseif(com=4)two_ways_insertion_sort(a,a+n);elseif(com=5)shell_sort(a,a+n);