#include<stdio.h>#include<stdlib.h>#include<time.h>#include<math.h>intk=0;intx=0;inty=0;intk1=0;intx1=0;intya=0;intPartition(intdata[],intlow,inthigh);#defineN10000//1.直接插入法voidinsert(inta[],intn){k=0;k1=0;intm=4;inti,j;for(i=2;i<=n;++i){k1++;if(a[i]<a[i-1]){a[0]=a[i];k++;for(j=i-1;a[0]<a[j];--j){a[j+1]=a[j];k++;k1++;}a[j+1]=a[0];k++;}}printf("1直接插入法%8d%8d%8d\n",k,k1,(k+k1));}//2.二分插入voidbinsert(inta[],intn){k=0;k1=0;inti,j,low,high,m;for(i=2;i<=n;++i){a[0]=a[i];k++;low=1;high=i-1;while(low<=high){m=(low+high)/2;if(a[0]<a[m]){high=m-1;k1++;}elselow=m+1;}for(j=i-1;j>=high+1;--j){a[j+1]=a[j];k++;//k1++;}a[high+1]=a[0];k++;}printf("2二分插入%8d%8d%8d\n",k,k1,(k+k1));}//3.冒泡排序voidbubblesort(inta[],intn){k=0;k1=0;inti,j;intexchange;for(i=1;i<n;i++){exchange=0;for(j=n-1;j>=i;j--){k1++;if(a[j+1]<a[j]){k+=3;a[0]=a[j+1];a[j+1]=a[j];a[j]=a[0];exchange=1;}//if}if(!exchange){printf("3冒泡排序%8d%8d%8d\n",k,k1,(k+k1));return;}//if}//for1}//void//4.希尔排序voidshellsort(inta[],intn){inti,j,d;intb;intx;d=n;k=0;k1=0;do{d=d/2;b=1;k+=2;for(i=a[1];i<=n-d;i++){j=i+d;k++;k1++;if(a[i]>a[j]){k+=4;x=a[i];a[i]=a[j];a[j]=x;b=0;}}}while(d>1);printf("4希尔排序%8d%8d%8d\n",k,k1,(k+k1));}//5.选择排序法voidselectsort(intA[],intn){inti,j,min,temp;k=0;k1=0;for(i=0;i<n;i++){min=i;for(j=i+1;j<=n;j++)/*从j往前的数据都是排好的，所以从j开始往下找剩下的元素中最小的*/{k1++;if(A[min]>A[j])/*把剩下元素中最小的那个放到A[i]中*/{k+=3;temp=A[i];A[i]=A[j];A[j]=temp;}}}printf("5选择排序%8d%8d%8d\n",k,k1,(k+k1));k=0;}//6.快速排序voidQuick_sort(inta[],intlow,inthigh){intmid;if(low<high){mid=Partition(a,low,high);Quick_sort(a,low,mid-1);/*递归调用*/Quick_sort(a,mid+1,high);}}intPartition(inta[],intlow,inthigh){intmid;a[0]=a[low];mid=a[low];while(low<high){x1++;while((low<high)&&(a[high]>=mid)){--high;}{a[low]=a[high];x++;}x1++;while((low<high)&&(a[low