归并排序菜鸟入门
发布日期:2021-06-30 10:11:49
浏览次数:4
分类:技术文章
本文共 1771 字,大约阅读时间需要 5 分钟。
归并排序是一种稳定快速地排序方法,该算法采用分治法的一个应用。也许这个名字刚听起来不是很好听,我一直将他说成是并归排序哈哈。
为什么会叫归并排序呢?不知道大家有没有这个疑问?
归并排序的整体思路就是先归后并,归是递归,将数组分为两部分,然后将左右两部分再分别递归分配咯,并就是合并,把分开的各个数组依次合并,最终完成一个无序数组的排序啦。
来我们再看看归并排序的基本步骤:
1.首先将数组分为两两一组
2.相邻进行比较合并。
举例才是王道:
请看
{2,8,6,9,4,7,3,9,1}
首先进行分组同时进行比较:
{2,8},{6,9},{4,7},{3,9},{1} 比较 4 次{2,6,8,9},{3,4,7,9},{1} 比较6次
{2,3,4,6,7,8,9,9},{1} 比较7次
{1,2,3,4,6,7,8,9,9,} 比较一次
完毕!
代码才是王道了,下面是C++的案例:
/*实际上使用的是C,不是C++*/#include#include #include using namespace std;void Merge(int sourceArr[],int tempArr[],int startIndex,int midIndex,int endIndex){ //设置前一个数组的首元素i,后一个数组的首元素j,k为拷贝原来大小的新数组的首元素 int i = startIndex,j = midIndex+1,k = startIndex; //当两个数组元素都不未读取完成 while(i!=midIndex+1 &&j!=endIndex+1) { if(sourceArr[i] > sourceArr[j]) tempArr[k++] = sourceArr[j++]; else tempArr[k++] = sourceArr[i++]; } //当j数组元素读取完成,i数组剩余元素直接添加到后面 while(i != midIndex +1) tempArr[k++] = sourceArr[i++]; //当i数组元素读取完成,j数组剩余元素直接添加到后面 while(j != endIndex +1) tempArr[k++] = sourceArr[j++]; //将排好导入的新数组里的内容复制到原来的数组 for(i=startIndex;i<=endIndex;i++) sourceArr[i] = tempArr[i];}void MergeSort(int sourceArr[], int tempArr[], int startIndex,int endIndex){ int midIndex; //判断是否递归 if(startIndex < endIndex) { //midIndex是前后两个相邻的数组的前一个数组最后的一个元素 midIndex= (startIndex + endIndex)/2; //递归前半部分 MergeSort(sourceArr,tempArr,startIndex,midIndex); //递归后半部分 MergeSort(sourceArr,tempArr,midIndex+1,endIndex); //归并的合并阶段啦 Merge(sourceArr,tempArr,startIndex,midIndex,endIndex); }}int main(){ int a[10] = {2,3,6,5,9,10,20,3,12,6}; int i ,b[10]; MergeSort(a,b,0,9); for(i=0;i<10;i++) cout< <<" ";}
转载地址:https://islet.blog.csdn.net/article/details/75472966 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月11日 21时36分42秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
一个数据项目
2019-04-30
基于JAVA_JSP电子书下载系统
2019-04-30
基于java出租车计价器设计与实现
2019-04-30
基于java的B2C的网上拍卖系统
2019-04-30
十二时辰篇:这该死的 996
2019-04-30
2021最新 上海互联网公司排名
2019-04-30
字节vs快手!取消大小周之战
2019-04-30
送一个闲置显示器!
2019-04-30
Oracle 行转列 pivot函数基本用法
2019-04-30
Oracle字符串分隔符替换(替换奇数个或偶数个)
2019-04-30
Oracle 利用 UTL_SMTP 包发送邮件
2019-04-30
Oracle 自定义函数实现split功能,支持超长字符串和clob类型的分隔
2019-04-30
Oracle 的循环中的异常捕捉和处理
2019-04-30
Oracle通过pivot和unpivot配合实现行列转换
2019-04-30
给Oracle数据库换一个1522端口的监听
2019-04-30
Excel表格数据生成ECharts图表
2019-04-30
阿里云短信服务python版,pyinstaller打包运行时缺少文件
2019-04-30
Oracle的pfile和spfile的一点理解和笔记
2019-04-30
WebService的简单案例记录(Java)
2019-04-30