数据结构 二维码文件第5章主要算法的C++代码

第5章主要算法的C++代码1．插入排序#include<iostream>usingnamespacestd;#defineMAX100//直接插入排序算法voidprints(inta[],intn){ inti; for(i=0;i<n;i++) cout<<a[i]<<","; cout<<endl;}//直接插入排序voidSinsert_sort(inta[],intn){inti,j,x;cout<<"直接插入排序结果："<<endl;for(i=1;i<n;i++){x=a[i];//空出a[i]的位置for(j=i-1;j>=0&&x<a[j];j--)a[j+1]=a[j];a[j+1]=x;//将x插在位置j cout<<"第"<<i<<"趟排序结果为："; prints(a,n);}}//二分插入排序算法voidBinsert_sort(inta[],intn){inti,j,left,right,mid,x;cout<<"二分插入排序结果："<<endl;for(i=1;i<n;i++){//准备插入a[i]x=a[i];left=0;right=i-1;while(left<=right){mid=(left+right)/2;if(x<a[mid])right=mid-1;elseleft=mid+1;}for(j=i-1;j>=left;j--)a[j+1]=a[j];a[left]=x;//元素a[i]就位 cout<<"第"<<i<<"趟排序结果为："; prints(a,n); }}//希尔排序voidShell_sort(inta[],intd[],intn,intt){inti,j,h,k,x;cout<<"希尔排序结果："<<endl;for(h=0;h<t;h++){k=d[h];//当前增量为kfor(i=k;i<n;i++){for(x=a[i],j=i-k;j>=0&&x<a[j];){a[j+k]=a[j];j-=k;}a[j+k]=x;//x就位} cout<<"第"<<h+1<<"趟排序结果为："; prints(a,n);}}intmain(){ inti,n,t,a1[MAX],a2[MAX],a3[MAX],d[MAX]; cout<<"请输入需要排序整数的个数："; cin>>n; cout<<"请输入需要排序的具体整数："; for(i=0;i<n;i++) {cin>>a1[i];a2[i]=a1[i];a3[i]=a1[i];} cout<<"请输入希尔排序排序中增量的个数："; cin>>t; cout<<"请输入希尔排序排序中的具体增量依次是："; for(i=0;i<t;i++) cin>>d[i]; Sinsert_sort(a1,n); Binsert_sort(a2,n); Shell_sort(a3,d,n,t); return0;}【运行结果参考】插入排序运行结果2．交换排序#include<iostream>usingnamespacestd;#defineMAX100voidprints(inta[],intn){ inti; for(i=0;i<n;i++) cout<<a[i]<<","; cout<<endl;}voidbubble_sort(inta[],intn){ inti,j,x,flag=1;j=n-2;while(flag){//当数据无序时循环，flag=0时，数据已经有序，退出循环flag=0;for(i=0;i<=j;i++)if(a[i]>a[i+1]){x=a[i];a[i]=a[i+1];a[i+1]=x;flag=1;}j--;prints(a,n);}}voidpartition(inta[],ints,intt,int&k,intn){inti,j,x;x=a[s];//取划分元素i=s;j=t;//扫描指针初值do{//循环地进行划分while((a[j]>=x)&&(i<j))j--;if(i<j)a[i++]=a[j];while((a[i]<x)&&(i<j))i++;if(i<j)a[j--]=a[i];}while(i<j);//直到i等于ja[i]=x;//划分元素就位k=i;prints(a,n);}voidqksort(inta[],inti,intj,intn){intk;if(i<j){partition(a,i,j,k,n);//划分qksort(a,i,k-1,n);//递归qksort(a,k+1,j,n);//递归}}intmain(){ inti,n,a1[MAX],a2[MAX]; cout<<"请输入需要排序整数的个数："; cin>>n; cout<<"请输入需要排序的具体整数："; for(i=0;i<n;i++){ cin>>a1[i];a2[i]=a1[i];} cout<<"冒泡排序结果："<<endl; bubble_sort(a1,n); cout<<"快速排序结果："<<endl; qksort(a2,0,n-1,n);｝return0;}【运行结果】交换排序运行结果3．选择排序#include<iostream>usingnamespacestd;#defineMAX100voidprints(inta[],intn){ inti; for(i=0;i<n;i++) cout<<a[i]<<","; cout<<endl;}voidsimpl_sort(inta[],intn){//直接选择排序 inti,j,k,x; for(k=n-1;k>0;k--){i=0;for(j=1;j<=k;j++){ if(a[j]>a[i])i=j;//选最大元x=a[k];a[k]=a[i];a[i]=x;//交换a[k]与a[i]; } prints(a,n);}}//以某个节点为根节点的子树进行调整，调整为大顶堆voidmax_heapify(inta[],inti,intheapsize){intl=2*i+1;intr=2*i+2;intlargest=i;if(l<heapsize&&a[l]>a[i]){largest=l;}if(r<heapsize&&a[r]>a[largest]){largest=r;}if(largest!=i){inttemp=a[largest];a[largest]=a[i];a[i]=temp;max_heapify(a,largest,heapsize);}}//建堆的过程，通过自底向上地调用max_heapify来将一个数组data【1……n】//变成一个大顶堆，只需要对除了叶子节点以外的节点进行调整voidbulid_max_heap(inta[],intheapsize){for(inti=heapsize/2-1;i>=0;i--)max_heapify(a,i,heapsize);}//堆排序算法实现主体：先用bulid_max_heap将输入数组构造成大顶堆，//然后将data【0】和堆的最后一个元数交换，继续进行调整。voidheap_sort(inta[],intn){bulid_max_heap(a,n);for(inti=n-1;i>0;i--){intt=a[0];a[0]=a[i];a[i]=t;max_heapify(a,0,i);prints(a,n);}}intmain(){ inti,n,a1[MAX],a2[MAX]; cout<<"请输入需要排序整数的个数："; cin>>n; cout<<"请输入需要排序的具体整数："; for(i=0;i<n;i++){ cin>>a1[i];a2[i]=a1[i];} cout<<"直接选择排序结果："<<endl; simpl_sort(a1,n); cout<<"堆排序结果："<<endl; heap_sort(a2,n); return0;｝选择排序运行结果4．合并排序#include<iostream>usingnamespacestd;#defineMAX100voidprints(inta[],intn){ inti; for(i=0;i<n;i++) cout<<a[i]<<","; cout<<endl;}//有序段合并函数voidmerge(inta[],intp,intq,ints,intt){inti,j,k,b[MAX];i=p,j=s,k=p-1;while((i<=q)&&(j<=t)){if(a[i]<=a[j])b[++k]=a[i++];elseb[++k]=a[j++];}while(i<=q)b[++k]=a[i++];while(j<=t)b[++k]=a[j++];for(i=p;i<=t;i++)a[i]=b[i];}//递归的合并排序算法voidmerge_sort(inta[],inti,intj,intn){intk;if(i<j){k=(i+j)/2;merge_sort(a,i,k,n); merge_sort(a,k+1,j,n); merge(a,i,k,k+1,j); }}//非递归的合并排序算法voidmerge2(inta[],intb[],intp,ints,intt){inti,j,k;i=p,j=s+1,k=p;while((i<=s)&&(j<=t)){if(a[i]<a[j])b[k++]=a[i++];elseb[k++]=a[j++];}if(i>s) for(intz=j;z<=t;z++) b[k++]=a[z]; else for(intz=i;z<=s;z++) b[k++]=a[z];}//控制一遍合并的扫描函数voidscan(intt,inta[],intb[],intn){intp,q,r;p=0;while(p<n){q=p+t-1;r=q+t;if(q>n-1)q=n-1;//限制语句if(r>n-1)r=n-1;merge2(a,b,p,q,r);//合并两段p=r+1;}}//非递归的合并排序voidmerge_sort_2(inta[],intn){intb[MAX],t;t=1;//有序段标准长度t初值为1while(t<n){scan(t,a,b,n);//从a合并到b prints(a,n);scan(2*t,b,a,n);//从b合并到at=4*t;