二路归并排序代码实例

虾米姐阅读：829 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.作者投稿可能会经我们编辑修改或补充。

二路归并排序 代码实例

二路归并排序代码实例