奔走在算法的大路上（一）排序之归并排序

归并排序（Merge sort）是创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并操作归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

算法描述归并操作的过程如下：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列设定两个指针，最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针到达序列尾将另一序列剩下的所有元素直接复制到合并序列尾

代码实现：

package Sort;import java.util.Random;/** * * Description: 归并排序的各种实现方式 * * @author zhangjunshuai * @version 1.0 * Create Date: 2015年4月14日上午11:58:27 * Project Name: ArithMetic * * <pre> * Modification History: *DateAuthorVersionDescription * ———————————————————————————————————– * LastChange: $Date:2015年4月14日$$Author: zhangjunshuai$$Rev:1.0 $* </pre> * *//** * * Description: * * @author zhangjunshuai * @version 1.0 * Create Date: 2015年4月21日下午5:54:09 * Project Name: ArithMetic * * <pre> * Modification History: *DateAuthorVersionDescription * ———————————————————————————————————– * LastChange: $Date:2015年4月21日$$Author: zhangjunshuai$$Rev:1.0 $* </pre> * */{/*** * 打印输出* * @author zhangjunshuai* @date 2015年4月3日下午4:19:03* @param a*/(Comparable[] a){for(int i = 0; i < a.length; i++){System.out.print(a[i] + ” “);}System.out.println();}/*** * 原地归并排序，思想是：* 将带比较的数据先拷贝到另外的数组中b[Size]中，然后进行归并排序，，再复制会a【】中* * @author zhangjunshuai* @date 2015年4月14日下午12:10:05* @param a* @param Size* @param start* @param end*/(Comparable[] a,int start,int middile,int end){//将a[start….middle]和a[middle+1….end]合并int length = end – start +1;Comparable[] b = new Comparable[length] ;for(int i = 0;i<length;i++){b[i] = a[start+i];}int h = 0,y = middile – start+1;for(int j = 0;j<length;j++){if(h>(middile – start)){a[start+j] = b[y++];}else{if(y>=b.length){a[start+j] = b[h++];}else{if(b[h].compareTo(b[y])<0)a[start+j] = b[h++];elsea[start+j] = b[y++];}}}}/*** * 实现原地交换归并排序* * @author zhangjunshuai* @date 2015年4月14日下午4:49:14*/(Comparable[] a){int Bsize =1;//步长do{int start = 0;int middile = 0;int end = 0;while(start < a.length){middile = start + Bsize-1;end = start +2*Bsize – 1;if(end >=a.length)//不要超过总长end = a.length -1;if(middile < end)//防止最后只够一个数组的localMerge(a,start,middile,end);start = end+1;}System.out.println(“——–步长：”+Bsize);Bsize = 2*Bsize ;}while(Bsize<a.length);show(a);}/*** * * @author zhangjunshuai* @date 2015年4月14日下午5:27:31* @param a* @param lo* @param hi*/(Comparable[]a,int lo,int hi){if(hi <= lo) return;int mid = lo + (hi -lo)/2;TopEnd(a,lo,mid);//将左半边排序TopEnd(a,mid+1,hi);//将右半边排序localMerge(a,lo,mid,hi);//归并结果}/*** * 自下而上的排序* * @author zhangjunshuai* @date 2015年4月21日下午5:54:23* @param a*/(Comparable[] a){int N = a.length;Comparable[] aux = new Comparable[N];for(int sz = 1;sz < N;sz = sz+sz){for(int lo = 0; lo < N -sz;lo+=sz+sz)localMerge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1, N-1));}}/*** * * @author zhangjunshuai* @date 2015年4月14日下午4:48:36* @param args*/(String[] args) {Random random = new Random();int rondomsize = random.nextInt(1000);Integer[] a = new Integer[rondomsize];for(int w =0;w<rondomsize;w++){a[w] = random.nextInt(rondomsize+w);}//ShowLocalMerge(a);EndToUp(a);show(a);}}

造物之前，必先造人。

相关文章：

你感兴趣的文章：

标签云：