欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java二路归并排序示例分享

程序员文章站 2024-02-25 17:34:57
归并排序就是采用分治法进行排序: (1)将一个数组分成小的2个数组分别进行排序; (2)之后将分出来的已经拍好序的数组进行合并; 复制代码 代码如下:import j...

归并排序就是采用分治法进行排序:

(1)将一个数组分成小的2个数组分别进行排序;

(2)之后将分出来的已经拍好序的数组进行合并;

复制代码 代码如下:

import java.util.scanner;
public class mergesort {
    int[] a=null;
    int[] b=null;
    int n;
    scanner sin=null;

    mergesort()
    {
        a=new int[10000];
        b=new int[10000];
        sin=new scanner(system.in);
    }

    void sort(int start,int end)    //排序a[start...end]
    {
        int mid;
     if(start >= end)    //只有一个元素的时候,直接返回
            return ;
        else
        {
            mid=(end-start)/2;    //将元素分成两半,分别排序
            sort(start,start+mid);
            sort(start+mid+1,end);

            //归并两个有序的数组a[start...start+mid]和a[start+mid+1...end]
            merge(start,start+mid,end);   
        }
    }

    void merge(int start,int mid,int end)    //归并
    {
        int t=start;
        int i=start,j=mid+1;
        while(i<=mid && j<=end)
        {
            if(a[i]<a[j])
                b[t++]=a[i++];
            else
                b[t++]=a[j++];
        }
        while(i<=mid)
            b[t++]=a[i++];
        while(j<=end)
            b[t++]=a[j++];

        for(i=start;i<=end;i++)    //排序后的内容写回a数组的相应位置去
            a[i]=b[i];
    }

    void run()
    {
        system.out.print("输入要排序的数的个数:");
        n=sin.nextint();
        for(int i=0;i<n;i++)
            a[i]=sin.nextint();
        sort(0,n-1);
        system.out.println("排序结果是:");
        //输入要排序的数据
        for(int i=0;i<n;i++)
            system.out.println(a[i]+"  ");
    }

    public static void main(string[] args) {
        new mergesort().run();
    }
}