归并排序

Tags: html5
[html
package mergesort; 
 
import java.util.Arrays; 
 
public class MergeSort2 { 
 
    private int[] arrays; 
    private static int count=0; 
    public void partation(int low,int high)  //对数组进行分的方法 
    { 
        if(high-low<=1)  //这儿说明已经分解到一个元素时,一个元素是有序的就跳出分的过程 
            return ; 
        int mid=(low+high)/2; 
        partation(low,mid); 
        partation(mid,high); 
        mergeSort(low,high); 
        count++;          //统计归并的总次数 
    } 
    public void mergeSort(int low,int high)   //对已排好序的数组进行归并 
    { 
        int mid=(low+high)/2; 
        //将数组arrays从[low,mid)复制到数组a中,不包含mid位置的元素;数组b同理 
        int[] a=Arrays.copyOfRange(arrays,low,mid); 
        int[] b=Arrays.copyOfRange(arrays,mid,high); 
        for(int k=low,indexa=0,indexb=0;k<high;k++) 
        { 
            /** 
             * 说明a数组中的所有元素都已移动完,将数组b从indexb索引位置全部移动 
             * 到arrays数组中,移动的个数从indexb到b.length-indexb 
             */ 
            if(indexa>=a.length)     
            { 
                System.arraycopy(b ,indexb,arrays,k,b.length-indexb); 
                break; 
            } 
            if(indexb>=b.length) 
            { 
                System.arraycopy(a, indexa, arrays, k, a.length-indexa); 
                break; 
            } 
            if(a[indexa]<b[indexb]) 
                arrays[k]=a[indexa++]; 
            else 
                arrays[k]=b[indexb++];   
        } 
        for(int i=low;i<high;i++)  //打印归并过程 
            System.out.print(arrays[i]+"  "); 
        System.out.println(); 
    } 
    public void sort(int[] arr) 
    { 
        this.arrays=arr; 
        partation(0,arr.length); 
    } 
    public static void main(String[] args) 
    { 
        //int[] arr={1,432,54,3,65,34,7,565,88,66}; 
        int[] arr={1,432,54,3}; 
        System.out.println("以下是归并的过程:"); 
        new MergeSort2().sort(arr); 
        System.out.println("count:"+MergeSort2.count); 
    } 

本文链接:http://www.4byte.cn/learning/43156.html