java 合并排序算法

合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。

实现逻辑

合并排序法基本是将两笔已排序的资料合并并进行排序，如果所读入的资料尚未排序，
 
       可以先利用其它的排序方式来处理这两笔资料，然后再将排序好的这两笔资料合并。
        
       合并排序法中用到了  快速排序法（三）

代码实现

package com.wepayweb.weixin.util.paixu;
//V型知识库 www.vxzsk.com
public class Mergesort {

	
	

	final int MAX=20;  
	   int num[]=new int[MAX];  
	   {  
	       System.out.print("生成的随机数组是：");  
	       for(int i=0;i<20;i++){  
	           num[i]=(int)(Math.random()*100);  
	           System.out.print(num[i]+" ");  
	       }  
	       System.out.println();  
	   } 
	   
	   int num2[]=new int[MAX]; //只用于合并排序法中  
	   {  
	       System.out.print("合并排序法需要使用的数组2是：");  
	       for(int i=0;i<20;i++){  
	           num2[i]=(int)(Math.random()*100);  
	           System.out.print(num2[i]+" ");  
	       }  
	       System.out.println();  
	   }  
	     
	   int num3[]=new int[MAX+MAX]; //用于存放合并排序法中被合并排序好的数组  
	   
	   public int partition(int number[], int left, int right) {  
	       int i, j, s, temp;  
	       s = number[right];  
	       i = left - 1;  
	       for(j = left; j < right; j++) {  
	           if(number[j] <= s) {  
	               i++;  
	               temp=number[i];  
	               number[i]=number[j];  
	               number[j]=temp;  
	           }  
	       }  
	       temp=number[i+1];  
	       number[i+1]=number[right];  
	       number[right]=temp;  
	       return i+1;  
	   }  
	   public void quicksort_3(int number[], int left, int right) {  
	       int q;  
	       if(left < right) {  
	           q = partition(number, left, right);  
	           quicksort_3(number, left, q-1);  
	           quicksort_3(number, q+1, right);  
	       }  
	   }  
	     
	   
	   /*-----------------------合并排序法--------------------------------------------- 
       合并排序法基本是将两笔已排序的资料合并并进行排序，如果所读入的资料尚未排序， 
       可以先利用其它的排序方式来处理这两笔资料，然后再将排序好的这两笔资料合并。 
       合并排序法中用到了  快速排序法（三） 
--------------------------------------------------------------------------------*/  

public void mergesort(int number1[],int number2[],int number3[]){  
 long start,end;  
   
 start=System.nanoTime();  
 quicksort_3(number1,0,MAX-1);  
 quicksort_3(number2,0,MAX-1);  
 mergesort_merge(number1,MAX,number2,MAX,number3);  
 end=System.nanoTime();  
   
 System.out.println("-----------------合并排序法------------------");  
 System.out.print("排序后是:");  
 for(int i=0;i<=MAX+MAX-1;i++){  
      System.out.print(number3[i]+" ");  
 }  
 System.out.println();  
 System.out.println("排序使用时间："+(end-start)+" ns");     
}  


public void mergesort_merge(int number1[], int M, int number2[], int N, int number3[]) {  
 int i = 0, j = 0, k = 0;  
 while(i < M && j < N) {  
     if(number1[i] <= number2[j]){  
         number3[k++] = number1[i++];  
     }else{  
         number3[k++] = number2[j++];  
     }     
 }  
 while(i < M){  
     number3[k++] = number1[i++];  
 }    
 while(j < N){  
     number3[k++] = number2[j++];  
 }  
}  


	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
   Mergesort m = new Mergesort();
   m.mergesort(m.num.clone(),m.num2.clone(),m.num3);    //合并排序法  
	}

}