二路归并排序 代码实例分析

访客 阅读:410 2020-10-19 15:34:58 评论: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(); 
    } 
}
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号