c语言数据排序法的个人总结.doc

上传人:Wo****Z 文档编号:30796843 上传时间:2022-08-06 格式:DOC 页数:26 大小:28KB
返回 下载 相关 举报
c语言数据排序法的个人总结.doc_第1页
第1页 / 共26页
c语言数据排序法的个人总结.doc_第2页
第2页 / 共26页
点击查看更多>>
资源描述

《c语言数据排序法的个人总结.doc》由会员分享,可在线阅读,更多相关《c语言数据排序法的个人总结.doc(26页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、c语言数据排序法的个人总结C语言9种常用排序法C语言9种常用排序法1.冒泡排序2.选择排序3.插入排序4.快速排序5.希尔排序6.归并排序7.堆排序8.带哨兵的直接插入排序9.基数排序例子:乱序输入n个数输出从小到大排序后的结果1.冒泡排序#include<stdio.hintmaininti,j,n,a100,temp;while(scanf(“%d”,&;n)!=EOF)for(i=0;i<n;i+)scanf(“%d”,&;ai);for(i=0;i<n-1;i+)for(j=0;j<n-i-1;j+)if(ajaj+1)temp=aj+1;aj+1=aj;aj=

2、temp;/总共需冒泡n-1次/第i趟冒泡/比较aj与aj+1,使aj+1大于ajfor(i=0;i<n;i+)printf(“%d”,ai);printf(“n”);/打印return0;2.选择排序#include<stdio.hintmaininti,j,n,a100,t,temp;while(scanf(“%d”,&;n)!=EOF)for(i=0;i<n;i+)scanf(“%d”,&;ai);for(i=0;i<n-1;i+)t=i;for(j=i+1;j<n;j+)if(ataj)t=j;temp=ai;ai=at;at=temp;for(i=0;i

3、<n;i+)printf(“%d”,ai);printf(“n”);/第i趟从ai+1an-1中选最小的数与ai交换/总共排序n-1趟return0;3.快速排序/_1.假设数组为an;2.第一次排序过程如下:取x=0(a0为中轴);i=0(第一个元素下标),j=n-1(最后一个元素下标);重复下面过程:(直到i=j)从aj起向前找小于ax的元素同时j-找到后aj与ax交换x=j;从ai起向后找大于ax的元素同时i+找到后ai与ax交换x=i;3.注意快排函数是迭代函数必须要有结束条件(因为忽略结束条件,调试了很久.)4.再对alowax-1、ax+1ahigh分别调用快排函数_/#in

4、clude<stdio.hvoidquicksort(inta,intlow,inthigh);intmaininti,n,a100;while(scanf(“%d”,&;n)!=EOF)for(i=0;i<n;i+)scanf(“%d”,&;ai);quicksort(a,0,n-1);for(i=0;i<n;i+)printf(“%d”,ai);printf(“n”);return0;voidquicksort(inta,intlow,inthigh)if(low=high)return;inti=low,j=high,x=i,temp;while(i<j)for(

5、;aj=ax&;&;i<j;j-);if(i<j)temp=aj;aj=ai;ai=temp;x=j;i+;elsebreak;/i=j即可跳出本次while循环/坑爹的结束条件return后面不能跟数值for(;ai<=ax&;&;i<j;i+);if(i<j)temp=ai;ai=aj;aj=temp;x=i;j-;elsebreak;quicksort(a,low,x-1);quicksort(a,x+1,high);/跳出本次while循环4.插入排序法#include<stdio.hvoidshow(inta,intn)inti;for(i=0;i

6、<n;i+)printf(“%d”,ai);printf(“n”);/输出数组voidinsertsort(inta,intn);intmaininti,n,a100;while(scanf(“%d”,&;n)!=EOF)for(i=0;i<n;i+)scanf(“%d”,&;ai);insertsort(a,n);show(a,n);return0;voidinsertsort(inta,intn)inti,j,k,temp;for(i=1;i<n;i+)j=i-1;for(;ai<aj&;&;j=0;j-);/寻找插入点j+;if(j=i)/该数有序不需要前插/插入

7、aicontinue;elsetemp=ai;for(k=i-1;k=j;k-)/将插入点后面的数依次后移一位ak+1=ak;aj=temp;5.shell排序法#include<stdio.hvoidshow(inta,intn)inti;for(i=0;i<n;i+)printf(“%d”,ai);printf(“n”);/输出数组voidshellsort(inta,intn);intmaininti,n,a100;while(scanf(“%d”,&;n)!=EOF)for(i=0;i<n;i+)scanf(“%d”,&;ai);shellsort(a,n);show

8、(a,n);return0;voidshellsort(inta,intn)intk,i,j,l,temp;k=n/2;while(k=1)for(i=k;i<n;i+)if(ai=ai-k)continue;elsefor(j=i-k;aj=ai&;&;j=0;j=j-k);j+=k;temp=ai;for(l=i-k;l=j;l-=k)al+k=al;aj=temp;k=k/2;/插入/保存ai/依次向后移动k个位置/寻找插入点aj/已经有序不需要移动6.归并排序归并排序是一种很容易进行并行化的算法因为归并的各个数据区间都是独立的没有依赖关系。并且归并排序是一种速度比较快的排序且是一

9、种稳定的排序算法排序速度与关键词初始排列无关。串行归并排序的算法大体的可以描述为:首先将要排序的表分成两个节点个数基本相等的子表然后对每个子表进行排序最后将排好序的两个子表合并成一个子表。在对子表进行排序时可以将子表再分解成两个节点数量基本相同的子表当子表足够小时也可以采用其他排序方法对子表进行排序然后再对排好序的子表进行归并操作最后将整个表排好序算法流程图:/_伪代码:mergesort(inta,intlow,inthigh);if(high-low+12)执行如下几步:(3个及以上)mid=(0+n)/2;mergesort(a,low,mid-1);mergesort(a,mid,hi

10、gh);进行本轮二路归并;bsort(intlow,intmid,inthigh);i=low,j=mid;while(i<mid&;&;j<=high)先归并入other;将剩下的归并入数组other;将otherlowhigh,复制到alowhigh;else:(3个以下)if(alow=ahigh)交换alow,ahigh;_/#include<stdio.hintother100;voidexchange(int_a,int_b)intt=_a;_a=_b;_b=t;voidshow(inta,intn)/输出数组inti;for(i=0;i<n;i+)prin

11、tf(“%d”,ai);printf(“n”);voidmergesort(inta,intlow,inthigh);intmaininti,n,a100;while(scanf(“%d”,&;n)!=EOF)for(i=0;i<n;i+)scanf(“%d”,&;ai);mergesort(a,0,n-1);show(a,n);return0;voidmergesort(inta,intlow,inthigh)if(high-low+1)2)intmid=(high+low)/2;mergesort(a,low,mid);mergesort(a,mid+1,high);inti=low

12、,j=mid+1,k=low;/含3个以上while(i<=mid&;&;j<=high)if(ai<=aj)otherk+=ai+;if(aiaj)otherk+=aj+;while(i<=mid)otherk+=ai+;while(j<=high)otherk+=aj+;for(i=low;i<=high;i+)ai=otheri;elseif(alowahigh)exchange(a+low,a+high);/含2及个以下7.堆排序/堆排序/_(堆是一个完全二叉树根结点值最大(小)1.heapadjust(inta,inti,intsizea)功能:以

13、ai为根形成一个堆buildheap(inta,intsizea)heapsort(inta,intsizea)_/功能:调用heapadjust使a形成一个堆功能:do建堆输出堆顶while(堆不空)#include<stdio.hvoidshow(inta,intn)inti;for(i=0;i<n;i+)printf(“%d”,ai);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

14、_i+2;if(i<(sizea/2)if(l<=(sizea-1)&;&;alai)maxi=l;if(r<=(sizea-1)&;&;aramaxi)/右孩子最大取右孩子下标maxi=r;if(maxi!=i)exchange(&;amaxi,&;ai);heapadjust(a,maxi,sizea);/跌倒以amaxi为根向下调整为大根堆。/取比根大的孩子与根调换/左孩子比ai大的取左孩子下标/ai为叶结点则不需要调整/函数功能:从最后一个非叶结点起向上直到根结点逐步调整建立大根对堆voidbuildheap(inta,intsizea)inti;for(i=(siz

15、ea/2-1);i=0;i-)heapadjust(a,i,sizea);/ai为最后一个非叶结点voidheapsort(inta,intsizea)inti;intj=sizea;for(i=0;i<sizea;i+)buildheap(a,j);exchange(&;a0,&;a-j);/将根(最大)结点交换到后面去/每次循环都会形成一个大根堆堆顶元素a0最大/堆中元素个数减一intmaininti,n,a100;while(scanf(“%d”,&;n)!=EOF)for(i=0;i<n;i+)scanf(“%d”,&;ai);heapsort(a,n);show(a,n)

16、;return0;8.带哨兵的直接插入排序/_从小到大排序a0用作哨兵当某个数ai找插入位置时先令a0=ai再向前比较当比较到a0时说明插入位置为a1,这样可以防止数组越界._/#include<stdio.hvoidshow(inta,intn)inti;for(i=1;i<=n;i+)/输出数组printf(“%d”,ai);printf(“n”);voiddir_insert(inta,intn)inti,j;for(i=2;i<=n;i+)a0=ai;for(j=i-1;aja0;j-)/插入位置:jaj+1=aj;a+j=a0;intmaininti,n,a100;

17、while(scanf(“%d”,&;n)!=EOF)for(i=1;i<=n;i+)scanf(“%d”,&;ai);dir_insert(a,n);show(a,n);return0;9.基数排序/基数排序/_假设输入数列最多为4位且都是十进制数要做4次划分、收集_/#include<stdio.h#include<math.h#defineN4/每个数最多4位/输出数组voidshow(inta,intn)inti;for(i=1;i<=n;i+)printf(“%d”,ai);printf(“n”);voidradixsort(intc,inti,intn)/以

18、第i位为依据进行划分和收集inta1030=0,0,0,0,0,0,0,0,0,0;分基数为i的数intb10=0;intj,k,l,m;k=pow(10,i);l=k/10;for(j=1;j<=n;j+)/一次分配的过程m=(cj%k)/l;/判断cj在本次划分中被分到哪个部分/bi表示本次本次划分后基数为i的数的个数/ai中收集本次划ambm+=cj;/分配完毕后基数为m的数为bm个l=1;for(m=0;m<10;m+)/收集for(j=0;j<bm;j+)cl+=amj;voidbasesort(intc,intn)inti;for(i=1;i<=N;i+)r

19、adixsort(c,i,n);intmaininti,n,c100;while(scanf(“%d”,&;n)!=EOF)for(i=1;i<=n;i+)scanf(“%d”,&;ci);basesort(c,n);show(c,n);return0;c语言的两种排序方法c语言的两种排序方法用“冒泡排序法”对一维数组中的整数进行排序使其元素的值按从小到大的顺序排列。冒泡排序法是一种简单的排序方法排序方法如下所述。设有n个数要求从小到大排列冒泡排序法的排序过程分为如下的n-1步:第1步从下向上相邻两数比较小者调上。反复执行n-1次第1个数最小。第2步从下向上相邻两数比较小者调上。反复执行

20、n-2次前2个数排好。第k步从下向上相邻两数比较小者调上。反复执行n-k次前k个数排好。.第n-1步从下向上相邻两数比较小者调上。反复执行1次排序结束。例如“9、6、8、2、4”的排序过程动画演示参考教程指导部分程序如下:mainintn,i,j,x,a5;scanf(“%d”,&;n);for(i=0;i<n;i+)scanf(“%d”,&;ai);for(i=1;i<n;i+)for(j=0;j<n-i;j+)if(ajaj+1)x=aj;aj+1=aj;aj=x;for(i=0;i<n;i+)printf(“%3d”,ai);【例4-6】用”选择排序法“对一维数组

21、中的整数进行排序使其元素的值是按从小到大的顺序排列。选择排序法也是一种简单的排序方法排序方法如下所述。设有n个数要从小到大排列选择排序法排序过程分为n-1步:第一步在第1n个数中找出最小数然后和第一个数交换前一个数排好。第二步在第2n个数中找出最小数然后和第二个数交换前两个数排好第二步在第kn个数中找出最小数然后和第k个数交换前k个数排好第n-1步在第(n-1)n个数中找出最小数然后和第n-1个数交换排序结束例如“9、6、8、2、4”的排序过程动画演示参考教程指导部分程序如下:Voidmainintn,i,j,x,a5;scanf(“%d”,&;n);for(i=0;i<n;i+)sca

22、nf(“%d”,&;ai);for(i=0;i<n-1;i+)for(j=i+1;j<n;j+)if(aiaj)x=ai;ai=aj;aj=x;for(i=0;i<n;i+)printf(“%3d”,ai);改进的选择排序程序如下:Voidmainintn,i,j,x,p,a5;scanf(“%d”,&;n);for(i=0;i<n;i+)scanf(“%d”,&;ai);for(i=0;i<n-1;i+)p=i;for(j=i+1;j<n;j+)if(apaj)p=j;if(p!=i)x=ap;ap=aj;aj=x;for(i=0;i<n;i+)pr

23、intf(“%3d”,ai);c语言实现简单排序(8种方法)#include<stdio.h#include<stdlib.h/冒泡排序voidbubleSort(intdata,intn);/快速排序voidquickSort(intdata,intlow,inthigh);intfindPos(intdata,intlow,inthigh);/插入排序voidbInsertSort(intdata,intn);/希尔排序voidshellSort(intdata,intn);/选择排序voidselectSort(intdata,intn);/堆排序voidheapSort(i

24、ntdata,intn);voidswap(intdata,inti,intj);voidheapAdjust(intdata,inti,intn);/归并排序voidmergeSort(intdata,intfirst,intlast);voidmerge(intdata,intlow,intmid,inthigh);/基数排序voidradixSort(intdata,intn);intgetNumPos(intnum,intpos);intmainintdata10=43,65,4,23,6,98,2,65,7,79;inti;printf(“原先数组:”);for(i=0;i<1

25、0;i+)printf(“%d”,datai);printf(“n”);/_printf(“冒泡排序:”);bubleSort(data,10);for(i=0;i<10;i+)printf(“%d”,datai);printf(“n”);printf(“快速排序:”);quickSort(data,0,9);for(i=0;i<10;i+)printf(“%d”,datai);printf(“n”);printf(“插入排序:”);bInsertSort(data,10);for(i=0;i<10;i+)printf(“%d”,datai);printf(“n”);prin

26、tf(“希尔排序:”);shellSort(data,10);for(i=0;i<10;i+)printf(“%d”,datai);printf(“n”);printf(“选择排序:”);selectSort(data,10);for(i=0;i<10;i+)printf(“%d”,datai);printf(“n”);intdata11=-1,43,65,4,23,6,98,2,65,7,79;inti;printf(“原先数组:”);intdata11=-1,43,65,4,23,6,98,2,65,7,79;for(i=1;i<11;i+)printf(“%d”,dat

27、ai);printf(“n”);printf(“堆排序:”);heapSort(data,10);for(i=1;i<11;i+)printf(“%d”,datai);printf(“n”);printf(“归并排序:”);mergeSort(data,0,9);for(i=0;i<10;i+)printf(“%d”,datai);printf(“n”);_/printf(“基数排序:”);radixSort(data,10);for(i=0;i<10;i+)printf(“%d”,datai);printf(“n”);return0;/_-冒泡排序for(j=0;j<n-1;j+)/外循环一次就排好一个数并放在后面/所以比较前面n-j-1个元素即可for(i=0;i<n-j-1;i+)if(dataidatai+1)temp=datai;datai=datai+1;datai+1=temp;/_-快速排序第 26 页 共 26 页

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 应用文书 > 工作计划

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁