#include<stdio.h>#include<time.h>#include <stdlib.h>const int maxx=1e2+1;int a[maxx];void swap(int *x,int *y){int z=*x;*x=*y;*y=z;}void init()//生成100个随机数,范围是0-99 {for(int i=0;i<100;i++) a[i]=rand()%100;}void zjcrsort()//直接插入排序{int b[maxx];for(int i=0;i<100;i++) b[i]=a[i];//按照a数组去初始化b数组int cnt1=0,cnt2=0;//比较次数和移动次数for(int i=1;i<100;i++){int j=i;int temp=b[i];while(j>0&&temp<b[j-1])//依次移动数组顺序 {cnt1++,cnt2++;b[j]=b[j-1];j--;}b[j]=temp;}printf("直接插入排序后数组的顺序为:\n");for(int i=0;i<100;i++) printf("%d ",b[i]);printf("\n");printf("排序的比较次数为：%d\n排序的移动次数为：%d\n",cnt1,cnt2);}void zbcrsort()//折半插入排序{int b[maxx];for(int i=0;i<100;i++) b[i]=a[i];//按照a数组去初始化b数组int cnt1=0,cnt2=0;//比较次数和移动次数for(int i=1;i<100;i++){int temp=b[i];int l=0,r=i-1;int j;while(l<=r)//由于前面的数字已经是排好序的，所以我们可以用折半法去查找该元素的插入位置 {int mid=(l+r)>>1;if(temp>=b[mid]) l=mid+1;else r=mid-1;cnt1++;//比较次数加一 }for(j=i-1;j>r;j--)//找到插入的位置，就将这个位置这个位置之后的数字往后移动 {b[j+1]=b[j];cnt2++;//移动次数加一 }b[j+1]=temp;}printf("折半插入排序后数组的顺序为:\n");for(int i=0;i<100;i++) printf("%d ",b[i]);printf("\n");printf("排序的比较次数为：%d\n排序的移动次数为：%d\n",cnt1,cnt2);}inline void shellsort()//希尔排序{int b[maxx];for(int i=0;i<100;i++) b[i]=a[i];//按照a数组去初始化b数组int cnt1=0,cnt2=0;//比较次数和移动次数int gap;for(gap=100/2;gap>0;gap/=2)//每次的增量，递减趋势{for(int i=gap;i<100;i++)//每次增量下，进行几组插入排序{for(int j=i;j-gap>=0&&b[j-gap]>b[j];j-=gap)//每个元素组中进行直接插入排序{swap(&b[j-gap], &b[j]);cnt1++,cnt2++;//移动和比较次数加一 }}}printf("希尔排序后数组的顺序为:\n");for(int i=0;i<100;i++) printf("%d ",b[i]);printf("\n");printf("排序的比较次数为：%d\n排序的移动次数为：%d\n",cnt1,cnt2);}void chocsort()//简单选择排序 {int b[maxx];for(int i=0;i<100;i++) b[i]=a[i];//按照a数组去初始化b数组int cnt1=0,cnt2=0;//比较次数和移动次数for(int i=0;i<100-1;i++){int _min=i;//记录最小元素位置 for(int j=i+1;j<100;j++){if(b[j]<b[_min]){cnt1++;_min=j;//更换最小元素位置 }}if(_min!=i){cnt2++;swap(&b[i],&b[_min]);//交换位置 }}printf("简单选择排序后数组的顺序为:\n");for(int i=0;i<100;i++) printf("%d ",b[i]);printf("\n");printf("排序的比较次数为：%d\n排序的移动次数为：%d\n",cnt1,cnt2);}void mpsort()//冒泡排序 {int b[maxx];for(int i=0;i<100;i++) b[i]=a[i];//按照a数组去初始化b数组int cnt1=0,cnt2=0;//比较次数和移动次数for(int i=0;i<100-1;i++)//排序的总轮数 {for(int j=0;j<100-1-i;j++)//每轮排序的个数{if(b[j]>b[j+1]){cnt1++;cnt2++;swap(&b[j],&b[j+1]);}}}printf("冒泡排序后数组的顺序为:\n");for(int i=0;i<100;i++) printf("%d ",b[i]);printf("\n");printf("排序的比较次数为：%d\n排序的移动次数为：%d\n",cnt1,cnt2);}void quicksort(int l,int r,int *cnt1,int *cnt2)//快速排序函数 {int i,j,t,temp;if(l>r) return ;//不符合排序条件，直接返回temp=a[l];//temp中存的是基准数i=l;j=r;while(i!=j){//先找右边的数字while(a[j]>=temp&&i<j){j--;int x=*cnt1+1;*cnt1=x;}//再找左边的数字while(a[i]<=temp&&i<j){i++;int x=*cnt1+1;*cnt1=x;}if(i<j){swap(&a[i],&a[j]);int x=*cnt2+1;*cnt2=x;}}a[l]=a[i];a[i]=temp;//最终将基准数归位quicksort(l,i-1,cnt1,cnt2);//继续处理左边的，这里是一个递归的过程quicksort(i+1,r,cnt1,cnt2);//继续处理右边的 ，这里是一个递归的过程}inline void Qsort()//快速排序{int b[maxx];for(int i=0;i<100;i++) b[i]=a[i];//按照a数组去初始化b数组int cnt1=0,cnt2=0;//比较次数和移动次数quicksort(0,99,&cnt1,&cnt2);printf("快速排序后数组的顺序为:\n");for(int i=0;i<100;i++) printf("%d ",a[i]);printf("\n");printf("排序的比较次数为：%d\n排序的移动次数为：%d\n",cnt1,cnt2);}int main(){init();//初始化原始数组，生成100个随机数据 printf("初始数组为：\n");for(int i=0;i<100;i++) printf("%d ",a[i]);printf("\n"); printf("***直接插入排序***\n");zjcrsort();printf("***折半插入排序***\n");zbcrsort();printf("***希尔排序***\n");shellsort();printf("***简单选择排序***\n");chocsort();printf("***冒泡排序***\n");mpsort();printf("***快速排序***\n");Qsort();printf("折半查找算法\n");printf("请输入您要查找的数字位置(输入-1的时候退出)\n");int x;while(scanf("%d",&x)&&x!=-1){int l=0;int r=99;while(l<=r){int mid=(l+r)>>1;if(a[mid]>=x) r=mid-1;//如果当前位置的数字大于要选择的数字，就去左半边查找。 else l=mid+1;//否则就去右半边 }if(a[l]!=x) printf("未找到该数字\n");else printf("该数字的位置为:%d\n",l); }}
努力加油a啊，(o)/~
直接插入排序 折半插入排序 希尔排序 简单选择排序 冒泡排序 快速排序模板以及比较次数与移动次数的分析 折半搜索算法模板
如果觉得《直接插入排序 折半插入排序 希尔排序 简单选择排序 冒泡排序 快速排序模板以及比》对你有帮助，请点赞、收藏，并留下你的观点哦！
