C语言9种常用排序法讲解.docx
- 文档编号:1935068
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:20
- 大小:39.23KB
C语言9种常用排序法讲解.docx
《C语言9种常用排序法讲解.docx》由会员分享,可在线阅读,更多相关《C语言9种常用排序法讲解.docx(20页珍藏版)》请在冰点文库上搜索。
C语言9种常用排序法讲解
C语言9种常用排序法
1.冒泡排序
2.选择排序
3.插入排序
4.快速排序
5.希尔排序
6.归并排序
7.堆排序
8.带哨兵的直接插入排序
9.基数排序
例子:
乱序输入n个数,输出从小到大排序后的结果
1.冒泡排序
#include
intmain()
{
inti,j,n,a[100],temp;
while(scanf("%d",&n)!
=EOF)
{
for(i=0;i scanf("%d",&a[i]); for(i=0;i { for(j=0;j { if(a[j]>a[j+1])//比较a[j]与a[j+1],使a[j+1]大于a[j] { temp=a[j+1]; a[j+1]=a[j]; a[j]=temp; } } } for(i=0;i printf("%d",a[i]); printf("\n"); } return0; } 2.选择排序 #include intmain() { inti,j,n,a[100],t,temp; while(scanf("%d",&n)! =EOF) { for(i=0;i scanf("%d",&a[i]); for(i=0;i { t=i; for(j=i+1;j { if(a[t]>a[j]) t=j; } temp=a[i]; a[i]=a[t]; a[t]=temp; } for(i=0;i printf("%d",a[i]); printf("\n"); } return0; } 3.快速排序 /* 1.假设数组为a[n]; 2.第一次排序过程如下: 取x=0(a[0]为中轴); i=0(第一个元素下标),j=n-1(最后一个元素下标); 重复下面过程: (直到i>=j) { 从a[j]起,向前找小于a[x]的元素,同时j--,找到后,a[j]与a[x]交换,x=j; 从a[i]起,向后找大于a[x]的元素,同时i++,找到后,a[i]与a[x]交换,x=i; } 3.注意快排函数是迭代函数,必须要有结束条件(因为忽略结束条件,调试了很久......) 4.再对a[low]~a[x-1]、a[x+1]~a[high]分别调用快排函数 */ #include voidquicksort(inta[],intlow,inthigh); intmain() { inti,n,a[100]; while(scanf("%d",&n)! =EOF) { for(i=0;i scanf("%d",&a[i]); quicksort(a,0,n-1); for(i=0;i printf("%d",a[i]); printf("\n"); } return0; } voidquicksort(inta[],intlow,inthigh) { if(low>=high)return;//坑爹的结束条件,return后面不能跟数值 inti=low,j=high,x=i,temp; while(i { for(;a[j]>=a[x]&&i if(i { temp=a[j]; a[j]=a[i]; a[i]=temp; x=j; i++; } else break;//i>=j即可跳出本次while循环 for(;a[i]<=a[x]&&i if(i { temp=a[i]; a[i]=a[j]; a[j]=temp; x=i; j--; } else break;//跳出本次while循环 } quicksort(a,low,x-1); quicksort(a,x+1,high); } 4.插入排序法 #include voidshow(inta[],intn)//输出数组 { inti; for(i=0;i printf("%d",a[i]); printf("\n"); } voidinsertsort(inta[],intn); intmain() { inti,n,a[100]; while(scanf("%d",&n)! =EOF) { for(i=0;i scanf("%d",&a[i]); insertsort(a,n); show(a,n); } return0; } voidinsertsort(inta[],intn) { inti,j,k,temp; for(i=1;i { j=i-1; for(;a[i]=0;j--);//寻找插入点 j++; if(j==i)//该数有序,不需要前插 continue; else { temp=a[i]; for(k=i-1;k>=j;k--)//将插入点后面的数依次后移一位 { a[k+1]=a[k]; } a[j]=temp; } } } 5.shell排序法 #include voidshow(inta[],intn)//输出数组 { inti; for(i=0;i printf("%d",a[i]); printf("\n"); } voidshellsort(inta[],intn); intmain() { inti,n,a[100]; while(scanf("%d",&n)! =EOF) { for(i=0;i scanf("%d",&a[i]); shellsort(a,n); show(a,n); } return0; } voidshellsort(inta[],intn) { intk,i,j,l,temp; k=n/2; while(k>=1) { for(i=k;i { if(a[i]>=a[i-k])//已经有序,不需要移动 continue; else { for(j=i-k;a[j]>=a[i]&&j>=0;j=j-k);j+=k;//寻找插入点a[j] temp=a[i];//保存a[i] for(l=i-k;l>=j;l-=k)//依次向后移动k个位置 { a[l+k]=a[l]; } a[j]=temp;//插入 } } k=k/2; } } 6.归并排序 归并排序是一种很容易进行并行化的算法,因为归并的各个数据区间都是独立的,没有依赖关系。 并且归并排序是一种速度比较快的排序,且是一种稳定的排序算法,排序速度与关键词初始排列无关。 串行归并排序的算法大体的可以描述为: 首先将要排序的表分成两个节点个数基本相等的子表,然后对每个子表进行排序,最后将排好序的两个子表合并成一个子表。 在对子表进行排序时可以将子表再分解成两个节点数量基本相同的子表,当子表足够小时,也可以采用其他排序方法对子表进行排序,然后再对排好序的子表进行归并操作,最后将整个表排好序 算法流程图: /*伪代码: mergesort(inta[],intlow,inthigh); if(high-low+1>2)执行如下几步: (3个及以上) mid=(0+n)/2; mergesort(a,low,mid-1); mergesort(a,mid,high); 进行本轮二路归并;bsort(intlow,intmid,inthigh); i=low,j=mid; while(i { 先归并入other[]; } 将剩下的归并入数组other[]; 将other[low~high],复制到a[low~high]; else: (3个以下) if(a[low]>=a[high])交换a[low],a[high]; */ #include intother[100]; voidexchange(int*a,int*b) { intt=*a; *a=*b; *b=t; } voidshow(inta[],intn)//输出数组 { inti; for(i=0;i printf("%d",a[i]); printf("\n"); } voidmergesort(inta[],intlow,inthigh); intmain() { inti,n,a[100]; while(scanf("%d",&n)! =EOF) { for(i=0;i scanf("%d",&a[i]); mergesort(a,0,n-1); show(a,n); } return0; } voidmergesort(inta[],intlow,inthigh) { if((high-low+1)>2)//含3个以上 { intmid=(high+low)/2; mergesort(a,low,mid); mergesort(a,mid+1,high); inti=low,j=mid+1,k=low; while(i<=mid&&j<=high) { if(a[i]<=a[j]) { other[k++]=a[i++]; } if(a[i]>a[j]) { other[k++]=a[j++]; } } while(i<=mid) { other[k++]=a[i++]; } while(j<=high) { other[k++]=a[j++]; } for(i=low;i<=high;i++) a[i]=other[i]; } else//含2及个以下 { if(a[low]>a[high]) { exchange(a+low,a+high); } } } 7.堆排序 //堆排序 /*(堆是一个完全二叉树,根结点值最大(小)) 1.heapadjust(inta[],inti,intsizea)功能: 以a[i]为根,形成一个堆 buildheap(inta[],intsizea)功能: 调用heapadjust(),使a[]形成一个堆 heapsort(inta[],intsizea)功能: do{建堆,输出堆顶}while(堆不空) */ #include voidshow(inta[],intn)//输出数组 { inti; for(i=0;i printf("%d",a[i]); printf("\n"); } voidexchange(int*a,int*b) { intt=*a; *a=*b; *b=t; } voidheapadjust(inta[],inti,intsizea) { intmaxi=i; intl=2*i+1; intr=2*i+2; if(i<(sizea/2))//a[i]为叶结点,则不需要调整 { if(l<=(sizea-1)&&a[l]>a[i])//左孩子比a[i]大的,取左孩子下标 { maxi=l; } if(r<=(sizea-1)&&a[r]>a[maxi])//右孩子最大,取右孩子下标 { maxi=r; } if(maxi! =i)//取比根大的孩子,与根调换 { exchange(&a[maxi],&a[i]); heapadjust(a,maxi,sizea);//跌倒,以a[maxi]为根,向下调整为大根堆。 } } } //函数功能: 从最后一个非叶结点起,向上直到根结点,逐步调整,建立大根对堆 voidbuildheap(inta[],intsizea) { inti; for(i=(sizea/2-1);i>=0;i--)//a[i]为最后一个非叶结点 { heapadjust(a,i,sizea); } } voidheapsort(inta[],intsizea) { inti; intj=sizea; for(i=0;i { buildheap(a,j); exchange(&a[0],&a[--j]);//将根(最大)结点交换到后面去 //堆中元素个数减一 } } intmain() { inti,n,a[100]; while(scanf("%d",&n)! =EOF) { for(i=0;i scanf("%d",&a[i]); heapsort(a,n); show(a,n); } return0; } 8.带哨兵的直接插入排序 /*从小到大排序 a[0]用作哨兵,当某个数a[i],找插入位置时,先令a[0]=a[i],再向前比较,当比较到a[0]时,说明插入位置为a[1],这样可以防止数组越界. */ #include voidshow(inta[],intn)//输出数组 { inti; for(i=1;i<=n;i++) printf("%d",a[i]); printf("\n"); } voiddir_insert(inta[],intn) { inti,j; for(i=2;i<=n;i++) { a[0]=a[i]; for(j=i-1;a[j]>a[0];j--)//插入位置: j a[j+1]=a[j]; a[++j]=a[0]; } } intmain() { inti,n,a[100]; while(scanf("%d",&n)! =EOF) { for(i=1;i<=n;i++) scanf("%d",&a[i]); dir_insert(a,n); show(a,n); } return0; } 9.基数排序 //基数排序 /*假设输入数列最多为4位,且都是十进制数 要做4次划分、收集 */ #include #include #defineN4//每个数最多4位 voidshow(inta[],intn)//输出数组 { inti; for(i=1;i<=n;i++) printf("%d",a[i]); printf("\n"); } voidradixsort(intc[],inti,intn)//以第i位为依据进行划分和收集 { inta[10][30]={{0},{0},{0},{0},{0},{0},{0},{0},{0},{0}};//a[i][]中收集本次划分基数为i的数 intb[10]={0};//b[i]表示本次本次划分后,基数为i的数的个数 intj,k,l,m; k=pow(10,i); l=k/10; for(j=1;j<=n;j++)//一次分配的过程 { m=(c[j]%k)/l;//判断c[j]在本次划分中被分到哪个部分 a[m][b[m]++]=c[j];//分配完毕后,基数为m的数为b[m]个 } l=1; for(m=0;m<10;m++)//收集 { for(j=0;j { c[l++]=a[m][j]; } } } voidbasesort(intc[],intn) { inti; for(i=1;i<=N;i++) { radixsort(c,i,n); } } intmain() { inti,n,c[100]; while(scanf("%d",&n)! =EOF) { for(i=1;i<=n;i++) scanf("%d",&c[i]); basesort(c,n); show(c,n); } return0; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 常用 排序 讲解