Merge Sort

引言  

  一直用java,沉溺于面向对象与设计模式,以为那就是编程的一切,以为算法和c语言一样的古老!所以很多问题都止步于java的糖衣炮弹里面!

    多次的挣扎后,打开算法导论,细细的从头看起,慢慢的思考!突然豁然明白,算法才是计算机核心科学!不懂算法怎么能说自己是编程的?

                                                Merge Sort

core: divide-conquer-combine

 

package agri;

public class MergSort {

	public static void main(String[] args) {
		int[] arr = { 6, 2, 25, 8,58,4,12};
		mergeSort(arr, 0, arr.length);
		for (int i : arr) {
			System.out.print(i + " ");
		}
	}

	public static void mergeSort(int arr[], int start, int end) {
		if (end-start>1) {
			// divide
			int length = end - start;
			// conquer
			mergeSort(arr, start, start + length / 2);
			mergeSort(arr, start + length / 2, end);
			// merge
			merge(arr, start, end);
		}
	}

	public static void merge(int[] arr, int start, int end) {
		int size = end - start;
		int[] re = new int[size];
		int i = 0, k = 0;
		int j = size / 2;
		// start
		while (i < size / 2 && j < size) {
			if (arr[start + i] < arr[start + j]) {
				re[k++] = arr[start + i];
				i++;
			} else if (arr[start + i] > arr[start + j]) {
				re[k++] = arr[start + j];
				j++;
			}
		}
		// end
		if (i == size / 2) {
			while (j < size) {
				re[k++] = arr[start + j];
				j++;
			}
		} else {
			while (i < size / 2) {
				re[k++] = arr[start + i];
				i++;
			}
		}
		//
		for(int m=0;m<size;m++){
			arr[start+m] = re[m];
		}
	}

}

   这个是经过自己几个迭代才写出来的,所以非常值得反思自己其中的错误历程,以回答为什么不能一气呵成的原因?这个版本和别人实现的不一样,当然碰到的问题是一样的,只是别人用了非常巧妙方法解决了,而我却纠结于整体的正确性,局部采用最笨的方法来实现!

 

总结:

     没有想清楚就动手,自己从来没有写伪代码的习惯,也没有接受写伪代码正规的教育,所以脑袋里面大概有个印象就开始写代码了.在思路不清晰的情况下,也就没有办法去论证算法的正确性!

    从后来编写的情况来看,自己主要犯的错误是:前期算法的步骤不正确,后期java语言上犯的一些低级错误!解决办法是,一面看正确代码实现,一面理解自己是如何犯错的,到了最后,就是靠debugger跟踪,发现自己的一些低级错误!

 

第一版本的最初实现:

package agri;

public class MergeSort {

	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
        int[] arr = {6,2,3,8,4,9};
        int[] re = mergeSort(arr);
        for(int i:re){
        	System.out.print(i+" ");
        }
	}
	
	public static int[] mergeSort(int arr[]){
		//divide
		int[] beforeHalf = new int[arr.length/2];
		int i=0;
		int[] afterHalf = new int[arr.length-arr.length/2];
		for(;i<arr.length/2;i++)
			beforeHalf[i] = arr[i];
		for(;i<arr.length;i++)
			afterHalf[i-arr.length/2] = arr[i];
		//conquer
		mergeSort(beforeHalf);
		mergeSort(afterHalf);
		//merge
		return merge(beforeHalf,afterHalf);
	}
	
	public static int[] merge(int be[],int af[]){
		int i = be.length-1;
		int j = af.length-1;
		int k = i+j;
		int[] re  = new int[k+2];
		while(i>0&&j>0){
			if(be[i]>af[j]){
				re[k] = be[i];
				i--;
			}
			else if(be[i]<af[j]){
				re[k] = af[j];
				j--;
			}
			k--;
		}
		if(i==0){
			while(j>0){
				re[k] = af[j];
				k--;
				j--;
			}
		}else{
			while(i>0){
				re[k] = af[i];
				k--;
				i--;
			}
		}
		return re;
	}

}

 

  这个版本就是生搬硬套了divide-conquer-merge,所以整体算法就是错误的,细节方面碰到的问题有,如此多的重复代码,却不晓得如何的消除!整体的正确性得不到论证,考虑细节的正确性与否都是在做无用功!

   所以教训是,如果先用伪代码去论证整体算法思路的正确性,细节暂时不考虑!集中精力从大局入手!而等到我把握大局的时候,已经浪费了好长时间了!

 

中间的一个版本:

 

package agri;

public class MergeSort {

	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
        int[] arr = {6,2,3,8,4,9};
       mergeSort(arr,0,arr.length);
        for(int i:arr){
        	System.out.print(i+" ");
        }
	}
	
	public static void mergeSort(int arr[],int start,int end){
		//divide
//		int[] beforeHalf = new int[arr.length/2];
//		int i=0;
//		int[] afterHalf = new int[arr.length-arr.length/2];
//		for(;i<arr.length/2;i++)
//			beforeHalf[i] = arr[i];
//		for(;i<arr.length;i++)
//			afterHalf[i-arr.length/2] = arr[i];
		int length = end - start;
		if(length==1)
			return;
			
		//conquer
		mergeSort(arr,start,start+length/2);
		mergeSort(arr,arr.length/2,arr.length-arr.length/2);
		//merge
	}
	
	public static int[] merge(int[] arr){
		int[] re  = new int[arr.length];
		int i=0,k=0;
		int j=arr.length/2;
		while(i<arr.length/2||j<arr.length){
			if(arr[i]<arr[j]){
				re[k++] = arr[i++];
			}else if(arr[i]>arr[j]){
				re[k++] = arr[j++];
			}
		}
		if(i==arr.length/2){
			while(j<arr.length)
				re[k++] = arr[j++];
		}else{
			while(i<arr.length/2)
				re[k++] = arr[i++];
		}
		return re;
	}

}

 

这个版本将陷入无限的死循环,而我却惶惶找不到答案,直到打开debugger跟踪才发现问题!我发现自己如此的依赖debugger,为什么不能第一次就正确呢?现在想起来,应该是实现function特别要注意的是局部变量,都是局部变量引起的错误,关注参数,关注局部变量,认真推敲与思考!但是有时候觉得怎么都无法避免此类错误,只有依赖debugger才能找到!

 

 

整体的正确性是千真万确的了,但是程序运行不正常,只有慢慢的一步一步调试了,下面是离最终版本很近的另以版本

package agri;

public class MergSortByMyself {

	public static void main(String[] args) {
		int[] arr = { 6, 2, 3, 8, 4, 9 };
		mergeSort(arr, 0, arr.length);
		for (int i : arr) {
			System.out.print(i + " ");
		}
	}

	public static void mergeSort(int arr[], int start, int end) {
		if (end-start>1) {
			System.out.println(start+":"+end);
			// divide
			int length = end - start;
			// conquer
			mergeSort(arr, start, start + length / 2);
			mergeSort(arr, start + length / 2, end);
			// merge
			merge(arr, start, end);
		}
	}

	public static void merge(int[] arr, int start, int end) {
		int size = end - start;
		int[] re = new int[size];
		int i = 0, k = 0;
		int j = size / 2;
		// start
		while (i < size / 2 || j < size) {
			if (arr[start + i] < arr[start + j]) {
				re[k++] = arr[start + i];
				i++;
			} else if (arr[i] > arr[j]) {
				re[k++] = arr[start + j];
				j++;
			}
		}
		// end
		if (i == size / 2) {
			while (j < size) {
				re[k++] = arr[start + j];
				j++;
			}
		} else {
			while (i < size / 2) {
				re[k++] = arr[start + i];
				i++;
			}
		}
		//
		for(int m=0;m<size;m++){
			arr[start+m] = re[m];
		}
	}

}

 

这个版本犯了两个低级错误!或许最终觉得它们真够低级的,但是发现与探索之旅时间却是如此之长,值得深思啊!

 

从代码来看,混乱的局部变量,不管是命名和使用上都值得考量,这个错误或许很难避免,但是发现的容易与否在于代码的规范与整齐上,看来花时间整理代码是永远都有必要的!

 

记得一句印象很深的话:建立在不良的解决方案上,只会带来更多的问题,所以与其在不良解决方案上修改,还不如脚踏实地在正确的道路上一步一步前行!

 

做一样东西,如果有捷径的话,那么我认为是:规范地慢慢走每一步,因为任何问题都不可避免,可以避免的是犯错的概率!对于算法来说,前期的设计,论证的正确性,实现其规范性,分析与改进,每一步都需要时间去梳理!