![排序算法(部编)课件_第1页](http://file4.renrendoc.com/view3/M01/29/1A/wKhkFmaDjpmAbij4AAGv1h07tWY769.jpg)
![排序算法(部编)课件_第2页](http://file4.renrendoc.com/view3/M01/29/1A/wKhkFmaDjpmAbij4AAGv1h07tWY7692.jpg)
![排序算法(部编)课件_第3页](http://file4.renrendoc.com/view3/M01/29/1A/wKhkFmaDjpmAbij4AAGv1h07tWY7693.jpg)
![排序算法(部编)课件_第4页](http://file4.renrendoc.com/view3/M01/29/1A/wKhkFmaDjpmAbij4AAGv1h07tWY7694.jpg)
![排序算法(部编)课件_第5页](http://file4.renrendoc.com/view3/M01/29/1A/wKhkFmaDjpmAbij4AAGv1h07tWY7695.jpg)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
排序算法专题主要内容:一、选择排序二、插入排序三、冒泡排序四、合并排序五、快速排序七、计数排序六、桶排序其它的排序:堆排序,留在后面介绍排序就是把一组无序的关键字,通过算法变成一组有序的关键字。一、选择排序算法思想:对于一组关键字{K1,K2,…,Kn},首先从K1,K2,…,Kn中选择最小值,假如它是Ki,则将Ki与K1对换,然后从K2,K3,…,Kn中选择最小值Ki,再将Ki与K2对换.如此进行选择和调换n-2趟,第(n-1)趟,从Kn-1、Kn中选择最小值Ki将Ki与Kn-1对换,最后剩下的就是该序列中的最大值,一个由小到大的有序序列就这样形成.即:在要排序的一组数中,选出最小的一个数与第一个位置的数交换,然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。举例:对下面一组关键字,要求按照从大到小排序
a[1]a[2]a[3]a[4]a[5]a[6]a[7]13287499123748从A[1]到a[7]找最大的数9812347从A[2]到a[7]找最大的数9
871234从A[3]到a[7]找最大的数9
8
74123从A[4]到a[7]找最大的数9
8
7
4312从A[5]到a[7]找最大的数9
8
7
4
321从A[6]到a[7]找最大的数9
8
7
4
3
21排序结束for(i=1;i<n;i++){for(j=i+1;j<=n;j++)if(a[j]>a[i]){a[0]=a[i];a[i]=a[j];a[j]=a[0];}}核心代码该算法缺点就是元素交换的次数太多。改进算法:
for(i=1;i<=n;i++){
k=i;for(j=i+1;j<=n;j++)if(a[k]<a[j])k=j;if(k!=i){a[0]=a[i];a[i]=a[k];a[k]=a[0];}}二、插入排序算法思想:设有一组关键字{K1,K2,…,Kn},排序开始就认为K1是一个有序序列,让K2插入上述表长为1的有序序列,使之成为一个表长为2的有序序列,然后让K3插入上述表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得一个表长为n的有序序列。第一趟:
[55]
22
44
11
33第二趟:
[22
55]
44
11
33第三趟:
[22
44
55]
11
33第四趟:
[11
22
44
55]
33第五趟:[1122
33
44
55]解决问题关键是找插入的位置。需要写一个函数find(x,y),来确定第y个插入元素x在已经有序的序列中的位置。intfind(intx,inty)//该函数就是确定第y个元素x,在有序序列中的位置。{intk=y;//函数值通过K来返回,K初始化为y,设插入在y位置。for(inti=1;i<=y;i++)//从第1个元素开始和X比较找到第一个比X小的数if(a[i]>=x){k=i;break;}//记下第一个比X小的数的位置,退出循环returnk;//此时的k即为X要插入的位置。}程序核心代码:for(inti=1;i<=n;i++){intk;cin>>m;k=find(m,i);for(intj=i;j>=k;j--)a[j+1]=a[j];a[k]=m;
}程序采用了边读入边插入的方法。兰色部分为后面元素后移。三、冒泡排序算法思想:让j取1至n-1,将r[j]与r[j+1]比较,如果r[j]<r[j+1],则把记录r[j]与r[j+1]交换位置,否则不进行交换.最后是r[n-1]与r[n]比较,关键字较小的记录就换到r[n]的位置上,到此第一趟冒泡结束。最小关键字的记录就象最轻的气泡冒到顶部一样换到了文件的最后.(2)让j取1至n-2,重复上述的比较对换操作,最终r[n-1]之中存放的是剩余n-1个记录(r[n]除外)中关键字最小的记录.(3)让j取1至2,经过一系列对联对比交换之后,r[3]之中是剩余若干记录中关键字最小的记录.(4)让j取1至1,将r[1]与r[2]对比,把关键字较小的记录交换到r[2]之中。至此,经过n-1次冒泡,r[1]到r[n]中的数就成了有序的数。举例:对下面一组关键字,要求按照从大到小排序
a[1]a[2]a[3]a[4]a[5]a[6]a[7]13287493287491387492
1第一趟第二趟第三趟第四趟第五趟第六趟排序结束87493
2
18794
3
2
1897
4
3
2
198
7
4
3
2
19
8
7
4
3
2
1for(inti=1;i<n;i++)for(intj=1;j<=n-i;j++)if(a[j]<a[j+1]){inttmp=a[j+1];a[j+1]=a[j];a[j]=tmp;}核心代码:优化:如果待排序是下面这样的数据。很显然除了第一趟排序在最后一次比较发生了交换外,以后每一趟都不会发生交换。排序在第一趟冒泡后就已经有序了,可以结束了。54312for(inti=1;i<n;i++){boolflag=true;//引入了一个标记变量flag,循环中交换过就改变值for(intj=1;j<=n-i;j++)if(a[j]>a[j+1]){inttmp=a[j+1];a[j+1]=a[j];a[j]=tmp;flag=false;}//if(flag)break;//flag的值没改变过,说明没发生过交换。}四、合并排序算法思想:归并是指将若干个已排序的子文件合并成一个有的文件。归并排序的实现有两种方法:自底向上和自顶向下。采用分治法进行的自顶向下的算法形式更为简洁。具体实现:设归并排序的当前区间是r[low…high],分治法的三个步骤:(1)分解:将当前区间一分为二,即求分裂点。mid=(low+high)/2(2)求解:递归地对两个子区间r[low…mid]和r[mid+1…high]进行归并排序。(3)合并:将已排好的两个区间r[low…mid]和r[mid+1…high]归并为一个有序的区间r[low…high]递归的终结条件是:low=high,即子区间的长度为1。voidmerge(intl,intm,intr){intb[101];inth,t,k;k=0;h=l;t=m+1;while((h<=m)&&(t<=r)){k++;if(a[h]<a[t]){b[k]=a[h];h++;}else{b[k]=a[t];t++;}}while(h<=m){k++;b[k]=a[h];h++;}while(t<=r){k++;b[k]=a[t];t++;}for(into=1;o<=k;o++)a[l+o-1]=b[o];}voidmergesort(intx,inty){intmid;if(x>=y)return;mid=(x+y)/2;mergesort(x,mid);mergesort(mid+1,y);merge(x,mid,y);}#include<iostream>usingnamespacestd;inta[101];//定义全局数组voidmerge(intl,intm,intr);//声明合并函数voidmergesort(intx,inty);//声明归并排序函数intmain(){intn;cin>>n;for(inti=1;i<=n;i++)cin>>a[i];mergesort(1,n);for(inti=1;i<=n;i++)cout<<a[i]<<'';cout<<endl;system("pause");return0;}五、快速排序在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入最终位置后,整个数据区间被此记录分割成两个子区间。所有关键字比该记录关键字小的放置在前子区间中,所有比他大的放置在后子区间中,并把该记录排在这个两个子区间的中间,这个过程称为一趟快速排序。之后对所有的两个子区间分别重复上述过程,直至每个子区间内只有一个记录为止。一趟快排的做法:设两个指示器i和j,他们的初值分别为指向无序区中的第一个和最后一个记录。假设无序区中记录为R[s…t],则i的初值为s,j的初值为t,首先将R[mid]移至临时变量tmp中作为基准,令j自t起向左扫描直至R[j]<tmp时,将R[j]移至i所指的位置上,然后令i自i+1起向右扫描直至R[i]>tmp时,将R[i]移至j所指的位置上,依次重复直至i=j,此时所有R[k](k=s,s+1,…,j-1)的关键字都小于tmp而所有R[k](k=j+1,j+2,…,t)的关键字必大于tmp,则可将tmp中的记录移至i所指位置R[i],它将无序中记录分割成R[s…j-1]和R[j+1…t],以便分别进行排序。voidqsort(intx,inty){inttmp;inth=x,r=y;tmp=a[((h+r)/2)];while(h<r){while(a[h]<tmp)h++;while(a[r]>tmp)r--;if(h<=r){inttmp2=a[h];a[h]=a[r];a[r]=tmp2;h++;r--;}}if(x<r)qsort(x,r);if(y>h)qsort(h,y);return;}核心代码:六、桶排序基本思想:若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个桶装入一个值,顺序输出各桶的值,将得到有序的序列。注:桶排序不是基于关键字值比较的排序。例:对1、3、5、7、2、0、60、100、40、60排序思路:用上述待排序的数,作为数组下标。对于上面的数,定义一个A[101],数组开始每个元素的值为0。在读入数据的过程中,如果读入1令a[1]加1,读入3,令a[3]加1…,依此处理。得到一个数组A。然后,i从0到100进行如下处理:for(inti=0;i<=100;i++)while(a[i]>0){cout<<i<<‘‘;a[i]--;}核心代码:#include<iostream>usingnamespacestd;intmain(){inta[1001],i,n,tmp;memset(a,0,sizeof(a));//初始化为0cin>>n;for(i=1;i<=n;i++)//边读人,边把数放入桶中{cin>>tmp;a[tmp]++;}for(i=0;i<=1000;i++)//对于有数的桶进入输出while(a[i]>0)//可能有多个相同的关键字{cout<<i<<'';a[i]--;}cout<<endl;system("pause");return
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024-2030年中国精炼葡萄籽油市场营销模式及发展前景预测研究报告
- 2024-2030年中国粘度控制系统行业市场发展趋势与前景展望战略分析报告
- 车间员工安全培训考试题及完整答案【各地真题】
- 2024-2030年中国管道空调行业市场发展趋势与前景展望战略分析报告
- 2024-2030年中国笔式驱动器行业市场发展趋势与前景展望战略分析报告
- 厂里厂里安全培训考试题含完整答案(有一套)
- 2024-2030年中国空心混凝土块行业市场发展趋势与前景展望战略分析报告
- 2024-2030年中国移动式谷物干燥机行业市场发展趋势与前景展望战略分析报告
- 2024-2030年中国租船运输行业市场深度调研及竞争格局与投资前景研究报告
- 2024-2030年中国神经性疼痛药物行业市场发展趋势与前景展望战略分析报告
- 第20讲 曲线系及其应用(解析几何)(解析版)
- 电力、通信排管施工技术交底
- 大学生心理健康教育(第3版)PPT完整全套教学课件
- 污水站安全生产管理条例
- 初中政治教育的跨学科教学策略应用
- 斜拉桥的现状与展望课件
- 初升高中语文衔接课 课件
- 地下车库通风管道安装技术交底大全
- 体育科学研究方法学习通课后章节答案期末考试题库2023年
- 云计算与大数据PPT完整全套教学课件
- 干部考察材料,思想品德
评论
0/150
提交评论