MergeSort Algorithm 归并排序 例子_Java_ThinkSAAS
MergeSort Algorithm 归并排序 例子
MergeSort Algorithm 归并排序 例子
内容来源： 网络
这个对本人实在是很有难度。。
起初是在java的Collections.sort()的api里面看到， 说是java所使用的排序是修改了的mergesort .- The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist).
网上查了一下就看到这个。
拿着纸和比在debug模式里研究了半天，大概明白了那么一点点。
实现代码：
public class Mergesort
private int[]
* int[] helper在算法中起到存放数据并和numbers里进行大小比较的作用。
private int[]
* number是要排序的数组的大小
public void sort(int[] values){
this.numbers=
number=values.
this.helper=new int[number];
mergesort(0,number-1);
private void mergesort(int low, int high){
//check if low is smaller than high, if not
//then the array is sorted.
if(low&high){
//get the index of the element which is in the middle
int middle=low+(high-low)/2;
//sort the left side of the array
mergesort(low,middle);
//sort the right side of the array
mergesort(middle+1, high);
//combine them both
merge(low,middle,high);
private void merge(int low, int middle, int high){
//copy both parts into the helper array
for(int i= i&= i++){
helper[i]=numbers[i];
int j=middle+1;
//copy the smallest values from either the left or the right
//side back to the original array
while(i&=middle&&j&=high){
//这里进行排序，如果helper[i]和helper[j]根据大小进行位置调整
//比如helper[0]==3和helper[1]==1，则进入if里面
//number[1]=helper[0]
if(helper[i]&=helper[j]){
numbers[k]=helper[i];
numbers[k]=helper[j];
//k代表numbers的索引，是一定会加1的。因为这里就是要将helper[i]
//和helper[j]做比较。最终将小的那个值放入numbers[k]
//copy the rest of the left side of the array into the target array
while(i&=middle){
//完成刚才排序的位置调整
numbers[k]=helper[i];
测试代码：
public class Test01
public static void main(String[] args)
int[] numbers={3,1,2,6,7,3,4};
Mergesort sorter=new Mergesort();
sorter.sort(numbers);
for(int i:numbers){
System.out.println(i);
//1 2 3 3 4 6 7
jdk的各种算法包括binary search,mergesort都在Arrays类里面。
都是加入了泛型的。
都是sun公司的高手写的。 想提高的话可以去研究研究。。
PHP开发框架
开发工具/编程工具
服务器环境
ThinkSAAS商业授权：
ThinkSAAS为用户提供有偿个性定制开发服务
ThinkSAAS将为商业授权用户提供二次开发指导和技术支持
让ThinkSAAS更好，把建议拿来。
开发客服微信博客访问： 168769
博文数量： 42
博客积分： 3010
博客等级： 中校
技术积分： 500
注册时间：
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
　归并排序(Merge Sort)是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。两路归并算法1、算法基本思路&&& 　设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。（1）合并过程&&& 　合并过程中，设置i，j和p三个指针，其初值分别指向这三个记录区的起始位置。合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1[p]中，然后将被复制记录的指针i或j加1，以及指向复制位置的指针p加1。&&& 　重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空)，此时将另一非空的子文件中剩余记录依次复制到R1中即可。（2）动态申请R1&&& 　实现时，R1是动态申请的，因为申请的空间可能很大，故须加入申请空间是否成功的处理。2、归并算法& void Merge(SeqList R，int low，int m，int high)&&& {//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的&&&& //子文件R[low..high]&&&& int i=low，j=m+1，p=0； //置初始值&&&& RecType *R1； //R1是局部向量，若p定义为此类型指针速度更快&&&& R1=(ReeType *)malloc((high-low+1)*sizeof(RecType))；&&&& if(! R1) //申请空间失败&&&&&& Error("Insufficient memory available!")；&&&& while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上&&&&&& R1[p++]=(R[i].key<=R[j].key)?R[i++]：R[j++]；&&&& while(i<=m) //若第1个子文件非空，则复制剩余记录到R1中&&&&&& R1[p++]=R[i++]；&&&& while(j<=high) //若第2个子文件非空，则复制剩余记录到R1中&&&&&& R1[p++]=R[j++]；&&&& for(p=0，i=low；i<=high；p++，i++)&&&&&& R[i]=R1[p]；//归并完成后将结果复制回R[low..high]&&& } //Merge
归并排序&&&& 归并排序有两种实现方法：自底向上和自顶向下。1、 自底向上的方法（1） 自底向上的基本思想&&&& 自底向上的基本思想是：第1趟归并排序时，将待排序的文件R[1..n]看作是n个长度为1的有序子文件，将这些子文件两两归并，若n为偶数，则得到 个长度为2的有序子文件；若n为奇数，则最后一个子文件轮空(不参与归并)。故本趟归并完成后，前 个有序子文件长度为2，但最后一个子文件长度仍为1；第2趟归并则是将第1趟归并所得到的 个有序的子文件两两归并，如此反复，直到最后得到一个长度为n的有序文件为止。&&&& 上述的每次归并操作，均是将两个有序的子文件合并成一个有序的子文件，故称其为"二路归并排序"。类似地有k(k>2)路归并排序。（2） 二路归并排序的全过程& 【&】（3） 一趟归并算法&分析：&&&&& 在某趟归并中，设各子文件长度为length(最后一个子文件的长度可能小于length)，则归并前R[1..n]中共有 个有序的子文件：R[1..length]，R[length+1..2length]，…， 。注意：&&&& 调用归并操作将相邻的一对子文件进行归并时，必须对子文件的个数可能是奇数、以及最后一个子文件的长度小于length这两种特殊情况进行特殊处理：　　① 若子文件个数为奇数，则最后一个子文件无须和其它子文件归并(即本趟轮空)；　　② 若子文件个数为偶数，则要注意最后一对子文件中后一子文件的区间上界是n。& 具体算法如下：&&& void MergePass(SeqList R，int length)&&&& { //对R[1..n]做一趟归并排序&&&&& int i；&&&&& for(i=1;i+2*length-1<=n;i=i+2*length)&&&&& Merge(R，i，i+length-1，i+2*length-1)；&&&&&&&&&& //归并长度为length的两个相邻子文件&&&&& if(i+length-1<n) //尚有两个子文件，其中后一个长度小于length&&&&&&&& Merge(R，i，i+length-1，n)； //归并最后两个子文件&&&&& //注意：若i≤n且i+length-1≥n时，则剩余一个子文件轮空，无须归并&&&& } //MergePass（4）二路归并排序算法& void MergeSort(SeqList R)&& {//采用自底向上的方法，对R[1..n]进行二路归并排序&&&& int length；&&&& for(1ength=1；length<n；length*=2) //做趟归并&&&&&&& MergePass(R，length)； //有序段长度≥n时终止&& }注意：&&&& 自底向上的归并排序算法虽然效率较高，但可读性较差。
2、自顶向下的方法&&&& 采用分治法进行自顶向下的算法设计，形式更为简洁。（1）分治法的三个步骤&&&& 设归并排序的当前区间是R[low..high]，分治法的三个步骤是：①分解：将当前区间一分为二，即求分裂点 ②求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序；③组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。& 递归的终结条件：子区间长度为1（一个记录自然有序）。（2）具体算法&&& void MergeSortDC(SeqList R，int low，int high)&&&& {//用分治法对R[low..high]进行二路归并排序&&&&&& int mid；&&&&&& if(low<high){//区间长度大于1&&&&&&&&& mid=(low+high)/2； //分解&&&&&&&&& MergeSortDC(R，low，mid); //递归地对R[low..mid]排序&&&&&&&&& MergeSortDC(R，mid+1，high)； //递归地对R[mid+1..high]排序&&&&&&&&& Merge(R，low，mid，high)； //组合，将两个有序区归并为一个有序区&&&&&&& }&&&& }//MergeSortDC（3）算法MergeSortDC的执行过程&&&& 算法MergeSortDC的执行过程如下图所示的递归树。二、算法分析1、稳定性&&&& 　归并排序是一种稳定的排序。2、存储结构要求&&& 　可用顺序存储结构。也易于在链表上实现。3、时间复杂度&&& 　对长度为n的文件，需进行 趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。4、空间复杂度&&&　 需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。& 注意：&&& 　若用单链表做存储结构，很容易给出就地的归并排序。
阅读(3621) | 评论(1) | 转发(0) |
相关热门文章
给主人留下些什么吧！~~
void MergePass(SeqList R，int length)
{ //对R[1..n]做一趟归并排序
for(i=1;i+2*length-1<=n;i=i+2*length)
//第一个元素呢
Merge(R，i，i+length-1，i+2*length-1)；
//归并长度为length的两个相邻子文件
if(i+length-1<n) //尚有两个子文件，其中后一个长度小于length
Merge(R，i，i+length-1，n)； //归并最后两个子文件
//注意：若i≤n且i+length-1≥n时，则剩余一个子文件轮空，无须归并
} //MergePass
请登录后评论。&&国之画&&&& &&
版权所有 京ICP备号-2
迷上了代码！2016年11月 VB大版内专家分月排行榜第二2016年1月 MS-SQL Server大版内专家分月排行榜第二2015年12月 MS-SQL Server大版内专家分月排行榜第二2015年11月 MS-SQL Server大版内专家分月排行榜第二2015年5月 MS-SQL Server大版内专家分月排行榜第二2015年4月 MS-SQL Server大版内专家分月排行榜第二2015年1月 VB大版内专家分月排行榜第二2015年1月 MS-SQL Server大版内专家分月排行榜第二2014年12月 VB大版内专家分月排行榜第二2014年11月 MS-SQL Server大版内专家分月排行榜第二2014年9月 MS-SQL Server大版内专家分月排行榜第二2013年8月 VB大版内专家分月排行榜第二2013年6月 VB大版内专家分月排行榜第二2013年5月 VB大版内专家分月排行榜第二2010年4月 VB大版内专家分月排行榜第二2010年3月 VB大版内专家分月排行榜第二2008年12月 VB大版内专家分月排行榜第二2008年8月 VB大版内专家分月排行榜第二2008年7月 VB大版内专家分月排行榜第二2007年11月 VB大版内专家分月排行榜第二
2017年1月 MS-SQL Server大版内专家分月排行榜第三2015年6月 MS-SQL Server大版内专家分月排行榜第三2015年3月 MS-SQL Server大版内专家分月排行榜第三2015年2月 MS-SQL Server大版内专家分月排行榜第三2014年12月 MS-SQL Server大版内专家分月排行榜第三2014年10月 VB大版内专家分月排行榜第三2014年10月 MS-SQL Server大版内专家分月排行榜第三2014年8月 MS-SQL Server大版内专家分月排行榜第三2013年9月 VB大版内专家分月排行榜第三2013年3月 VB大版内专家分月排行榜第三2012年5月 VB大版内专家分月排行榜第三2012年4月 VB大版内专家分月排行榜第三2010年10月 VB大版内专家分月排行榜第三2010年8月 VB大版内专家分月排行榜第三2010年7月 VB大版内专家分月排行榜第三2009年5月 VB大版内专家分月排行榜第三2008年9月 VB大版内专家分月排行榜第三2008年4月 VB大版内专家分月排行榜第三2008年2月 VB大版内专家分月排行榜第三
2016年11月 VB大版内专家分月排行榜第二2016年1月 MS-SQL Server大版内专家分月排行榜第二2015年12月 MS-SQL Server大版内专家分月排行榜第二2015年11月 MS-SQL Server大版内专家分月排行榜第二2015年5月 MS-SQL Server大版内专家分月排行榜第二2015年4月 MS-SQL Server大版内专家分月排行榜第二2015年1月 VB大版内专家分月排行榜第二2015年1月 MS-SQL Server大版内专家分月排行榜第二2014年12月 VB大版内专家分月排行榜第二2014年11月 MS-SQL Server大版内专家分月排行榜第二2014年9月 MS-SQL Server大版内专家分月排行榜第二2013年8月 VB大版内专家分月排行榜第二2013年6月 VB大版内专家分月排行榜第二2013年5月 VB大版内专家分月排行榜第二2010年4月 VB大版内专家分月排行榜第二2010年3月 VB大版内专家分月排行榜第二2008年12月 VB大版内专家分月排行榜第二2008年8月 VB大版内专家分月排行榜第二2008年7月 VB大版内专家分月排行榜第二2007年11月 VB大版内专家分月排行榜第二
2017年1月 MS-SQL Server大版内专家分月排行榜第三2015年6月 MS-SQL Server大版内专家分月排行榜第三2015年3月 MS-SQL Server大版内专家分月排行榜第三2015年2月 MS-SQL Server大版内专家分月排行榜第三2014年12月 MS-SQL Server大版内专家分月排行榜第三2014年10月 VB大版内专家分月排行榜第三2014年10月 MS-SQL Server大版内专家分月排行榜第三2014年8月 MS-SQL Server大版内专家分月排行榜第三2013年9月 VB大版内专家分月排行榜第三2013年3月 VB大版内专家分月排行榜第三2012年5月 VB大版内专家分月排行榜第三2012年4月 VB大版内专家分月排行榜第三2010年10月 VB大版内专家分月排行榜第三2010年8月 VB大版内专家分月排行榜第三2010年7月 VB大版内专家分月排行榜第三2009年5月 VB大版内专家分月排行榜第三2008年9月 VB大版内专家分月排行榜第三2008年4月 VB大版内专家分月排行榜第三2008年2月 VB大版内专家分月排行榜第三
2016年11月 VB大版内专家分月排行榜第二2016年1月 MS-SQL Server大版内专家分月排行榜第二2015年12月 MS-SQL Server大版内专家分月排行榜第二2015年11月 MS-SQL Server大版内专家分月排行榜第二2015年5月 MS-SQL Server大版内专家分月排行榜第二2015年4月 MS-SQL Server大版内专家分月排行榜第二2015年1月 VB大版内专家分月排行榜第二2015年1月 MS-SQL Server大版内专家分月排行榜第二2014年12月 VB大版内专家分月排行榜第二2014年11月 MS-SQL Server大版内专家分月排行榜第二2014年9月 MS-SQL Server大版内专家分月排行榜第二2013年8月 VB大版内专家分月排行榜第二2013年6月 VB大版内专家分月排行榜第二2013年5月 VB大版内专家分月排行榜第二2010年4月 VB大版内专家分月排行榜第二2010年3月 VB大版内专家分月排行榜第二2008年12月 VB大版内专家分月排行榜第二2008年8月 VB大版内专家分月排行榜第二2008年7月 VB大版内专家分月排行榜第二2007年11月 VB大版内专家分月排行榜第二
2017年1月 MS-SQL Server大版内专家分月排行榜第三2015年6月 MS-SQL Server大版内专家分月排行榜第三2015年3月 MS-SQL Server大版内专家分月排行榜第三2015年2月 MS-SQL Server大版内专家分月排行榜第三2014年12月 MS-SQL Server大版内专家分月排行榜第三2014年10月 VB大版内专家分月排行榜第三2014年10月 MS-SQL Server大版内专家分月排行榜第三2014年8月 MS-SQL Server大版内专家分月排行榜第三2013年9月 VB大版内专家分月排行榜第三2013年3月 VB大版内专家分月排行榜第三2012年5月 VB大版内专家分月排行榜第三2012年4月 VB大版内专家分月排行榜第三2010年10月 VB大版内专家分月排行榜第三2010年8月 VB大版内专家分月排行榜第三2010年7月 VB大版内专家分月排行榜第三2009年5月 VB大版内专家分月排行榜第三2008年9月 VB大版内专家分月排行榜第三2008年4月 VB大版内专家分月排行榜第三2008年2月 VB大版内专家分月排行榜第三
2016年11月 VB大版内专家分月排行榜第二2016年1月 MS-SQL Server大版内专家分月排行榜第二2015年12月 MS-SQL Server大版内专家分月排行榜第二2015年11月 MS-SQL Server大版内专家分月排行榜第二2015年5月 MS-SQL Server大版内专家分月排行榜第二2015年4月 MS-SQL Server大版内专家分月排行榜第二2015年1月 VB大版内专家分月排行榜第二2015年1月 MS-SQL Server大版内专家分月排行榜第二2014年12月 VB大版内专家分月排行榜第二2014年11月 MS-SQL Server大版内专家分月排行榜第二2014年9月 MS-SQL Server大版内专家分月排行榜第二2013年8月 VB大版内专家分月排行榜第二2013年6月 VB大版内专家分月排行榜第二2013年5月 VB大版内专家分月排行榜第二2010年4月 VB大版内专家分月排行榜第二2010年3月 VB大版内专家分月排行榜第二2008年12月 VB大版内专家分月排行榜第二2008年8月 VB大版内专家分月排行榜第二2008年7月 VB大版内专家分月排行榜第二2007年11月 VB大版内专家分月排行榜第二
2017年1月 MS-SQL Server大版内专家分月排行榜第三2015年6月 MS-SQL Server大版内专家分月排行榜第三2015年3月 MS-SQL Server大版内专家分月排行榜第三2015年2月 MS-SQL Server大版内专家分月排行榜第三2014年12月 MS-SQL Server大版内专家分月排行榜第三2014年10月 VB大版内专家分月排行榜第三2014年10月 MS-SQL Server大版内专家分月排行榜第三2014年8月 MS-SQL Server大版内专家分月排行榜第三2013年9月 VB大版内专家分月排行榜第三2013年3月 VB大版内专家分月排行榜第三2012年5月 VB大版内专家分月排行榜第三2012年4月 VB大版内专家分月排行榜第三2010年10月 VB大版内专家分月排行榜第三2010年8月 VB大版内专家分月排行榜第三2010年7月 VB大版内专家分月排行榜第三2009年5月 VB大版内专家分月排行榜第三2008年9月 VB大版内专家分月排行榜第三2008年4月 VB大版内专家分月排行榜第三2008年2月 VB大版内专家分月排行榜第三
匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。