算法之合并算法

合并算法是将一个数组分解为两个排序数组, 但是每个数组中都必须排序好的 这样才能实现合并算法

将数组替换原来的数组中的元素,该算法至少需要三个数组

以下是实现算法的java代码:

package suanfa;
public class Fenzhi {
	int merge(int[] a, int p, int q, int r){
		int n1 = q - p;	//4
		int n2 = r - q;		//4
		
		int [] L = new int[n1 + 1];
		int [] R = new int[n2 + 1];
		
		int i = 0;
		int j = 0;
		
		//将数据分解到两个数组里面
		for( i=0; i<n1; i++){
			L[i] = a[i];
		}
		for( j=0; j<n2; j++){
			R[j] = a[q+j];
		}
		
		for(i = 0; i < n1; i++){
			System.out.println("L["+i+"]"+L[i]);
		}
		
		for(j = 0; j < n2; j++){
			System.out.println("R["+j+"]"+R[j]);
		}
		L[n1] = 100;
		R[n2] = 100;
		
		i = 0;
		j = 0;
		
		int k = 0;
		for(k = p; k<a.length; k++){
			//System.out.println(k);
			
			if(L[i]<=R[j]){
				//System.out.println("L["+i+"] is :" + L[i]);
				a[k] = L[i];
				i = i + 1;
			}
			else{
				//System.out.println("R["+j+"] is :" + R[j]);
				a[k] = R[j];
				j =  j + 1;
			}
		}
		
		return 0;
	}
	public static void main(String[] args) {
		System.out.println("heh");
		int []a = {2,4,5,7,1,2,3,6,8};
		Fenzhi x = new Fenzhi();
		x.merge(a, 0, a.length/2, a.length);
		for(int i = 0; i < a.length; i++){
			System.out.print(a[i]);
		}
		/*System.out.println(a[0]);
		System.out.println(a.length);
		System.out.println('e');*/
	}
}

数组int []a = {2,4,5,7,1,2,3,6,8};中, 元素个数必须在a.length/2,分解到两个数组中时是已经排序号的.否则在merge函数中分解到两个数组中后要各自进行排序再操作

个人觉得,可以将merge改成递归调用方式,不断的将数组分解

以上是个人简介.不对的话有浏览者欢迎指正,万分感谢