归并排序的算法实现
归并排序的基本思想是:
将待排序元素分成大小大致相同的两个子集合,分别对两个子集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合。
算法:
1.把待排序的n个记录看作长度为1的有序序列,将相邻的子序列两两归并为长度为2或1的有序序列
2.把得到的n/2个长度为2的有序序列再归并为长度为2*2的有序序列
3.按照2的方式,重复对相邻的有序子序列进行归并操作,直到成为一个有序序列为止。
排序以一下方式进行:
一下是我的算法实现:
public void merge_sort(int[]data,int left,int right){ if(left<right){ int mid=(left+right)/2; //递归调用将数组分组,将数组分成n个记录 merge_sort(data, left, mid); merge_sort(data, mid+1, right); //将被分开的数组进行排序,合并 merge(data,left,mid,right); } } private void merge(int[] data, int left, int mid, int right) { int i=0,k=0; //用于控制合并过程时下标的处理 int begin1=left,end1=mid,begin2=mid+1,end2=right; //用于存放数据 int []temp=new int[right-left+1]; //开始比较赋值 while(begin1<=end1&&begin2<=end2){ //依次比较两个排好序的子序列,最初两个子序列中最小元素放入临时数组 if(data[begin1]<data[begin2]){ temp[k]=data[begin1]; begin1++; } else{ temp[k]=data[begin2]; begin2++; } k++; } //如果一个子序列已经完全放入临时数组,将剩余部分的数组放入临时数组 while(begin1<=end1){ temp[k++]=data[begin1++]; } while(begin2<=end2){ temp[k++]=data[begin2++]; } //将排好序的临时数组拷贝到原始数组 k=0; for(i=left;i<=right;i++){ data[i]=temp[k++]; } }
相关推荐
根据算法导论实现的归并排序算法
本人自己写的一些排序算法,这是系列1归并排序算法实现,
该源码使用Qt可以可视化展示归并排序算法实现效果,通过可视化的方式和实时显示算法比较和移动的次数,方便初学者理解归并排序算法的时间复杂度和原理
这是关于归并排序算法用C语言实现的代码,是经过测试正确的,希望能对大家的学习有所帮助。
归并排序的过程是,将数组分为许多的组,即将数组元素多的数组分为数组元素少的数组,然后再将其合并。它的优点是,同时对多个数据进行对比排序,归并排序是分治法的典型应用。 分:体现在将数组分为小数组。 治:对...
随机生成一千个数,并进行排序。四中排序算法,冒泡,简单选择,归并排序,堆排序。
C++实现希尔、快速、堆排序、归并排序算法,一些中文注释可能成乱码了,但是不影响代码执行。
C语言二路归并排序算法, 写了个二路归并的归并排序小代码,直接贴上来
完整的实现了归并排序的算法,使用C语言实现,相信看过本程序之后,会对归并排序了如指掌
斯坦福大学那本数据库系统实现的一个实验,内容是查询执行这一章中的两阶段多路归并排序算法的C实现,全手工编写,希望对大家有所帮助~
分治法实现归并排序算法算法设计与分析实验报告(word文档良心出品).docx分治法实现归并排序算法算法设计与分析实验报告(word文档良心出品).docx分治法实现归并排序算法算法设计与分析实验报告(word文档良心出品)....
C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序C语言算法之归并排序
归并排序算法,有程序和复杂性分析,还有解释,挺清楚的,很有用
易语言归并排序算法源码,归并排序算法,归并排序,子程序_有序数组合并
归并排序算法C语言版
一个 c c++写的归并排序算法,欢迎各位匹配指正。
完整的自然归并排序算法源程序,可自行输入待排元素个数以及数值,输出排好序的序列。