首页 > 代码库 > 怎样使用递归实现归并排序

怎样使用递归实现归并排序

       归并排序:归并排序是建立在归并操作上的一种有效的排序算法,该算法是採用分治法(Divide and Conquer)的一个很典型的应用。将已有序的子序列合并,得到全然有序的序列。即先使每一个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序,称为二路归并

       数据结构的学习过程中。我们常常会遇到排序算法,当中归并排序是一种高效而且算法复杂度比較简单的一种。

在课本的介绍中,大部分都会介绍归并排序算法。可是,每次看书总是认为非常easy,自己尝试去实现时,总是会出错。

学习数据结构已经有一段时间了,可是直接让我裸写归并排序的代码。也须要花上不少时间去调试。

难道就没有更好的方式让我们记住代码吗? 

       事实上仅仅要我们在写代码时。注意下技巧。便可轻松实现归并排序算法。以下介绍下我使用的方式:

       第一步:先写一个合并两个排序好数组的方法,方法名就叫做merge,例如以下:

    public static void merge(int[] a, int aSize, int[] b, int bSize, int[] c){
		int tempA = 0, tempB = 0, tempC = 0;
		while(tempA < aSize && tempB < bSize){
		    if(a[tempA] > b[tempB]){
			    c[tempC++] = b[tempB++];
			}else{
			    c[tempC++] = a[tempA++];
			}
		}
		
		while(tempA < aSize){
		    c[tempC++] = a[tempA++];
		}
		
		while(tempB < bSize){
		    c[tempC++] = b[tempB++];
		}
	}

       这种方法很easy,一共同拥有着5个參数(也能够简化为3个參数),当中a,b数组是待合并数组,aSize,bSize是数组长度(这两个參数能够去掉),c为目标数组。基本的流程就是不断的比較a,b数组的大小,然后将较小数据复制进c中。这里面关键的一点就是使用了3个暂时变量,用于标志每一个数组相应的位置。这样子能够极大简化我们的代码设计。

以下是相应的图示过程:

       技术分享


       有了这种方法之后。我们就能够開始写归并排序的主体方法了。

写主体方法也非常easy。思想就是分治算法。

  • 第一步:就是将大数组分成两个小的数组
  • 第二部:排序这两个数组。使用的是递归排序方法,也就是自己调用自己
  • 第三部:调用上面的合并方法合并起来就可以
       代码很easy。直接贴上
public class TowersApp{
    
	public static void main(String[] args){
	    int[] a = {1,1,0,1,1,5,3};
        mergeSort(a);
		
		for(int i=0; i<a.length; i++){
		    System.out.print(a[i]);
		}
	}
	
	
	public static void mergeSort(int[] source){
	    //递归出口
		if(source.length == 1) return;
		
		//将大数组分成两个小数组
		int middle = source.length / 2;
		int[] left = new int[middle];
		for(int i=0; i<middle; i++){
		    left[i] = source[i];
		}
		
		int[] right = new int[source.length - middle];
		for(int i=middle; i<source.length; i++){
		    right[i-middle] = source[i];
		}
		
		//对数据进行排序(这里使用递归排序)
		mergeSort(left);
		mergeSort(right);
		
		//合并排序好的数据
		merge(left, left.length, right, right.length, source);
	}
	
	
	public static void merge(int[] a, int aSize, int[] b, int bSize, int[] c){
		int tempA = 0, tempB = 0, tempC = 0;
		while(tempA < aSize && tempB < bSize){
		    if(a[tempA] > b[tempB]){
			    c[tempC++] = b[tempB++];
			}else{
			    c[tempC++] = a[tempA++];
			}
		}
		
		while(tempA < aSize){
		    c[tempC++] = a[tempA++];
		}
		
		while(tempB < bSize){
		    c[tempC++] = b[tempB++];
		}
	}
}



       总结:要记住归并排序算法的核心核心思想:分而治之。

怎样使用递归实现归并排序