IT源码网

二路归并排序 代码实例讲解

lxf 2020年10月19日 程序员 247 0

  感觉好久没有写排序程序了,C语言有qsort()函数,C++有sort()函数,java语言有Arrays类(主要这个不是Array)。今天写了一下归并排序还有点费劲呀。晚上回来写写。

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

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

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

晚上写的java二路归并排序代码如下:

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(); 
    } 
}
发布评论

分享到:

IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

物件捆绑 背包问题 动态规划 求解讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。