【Java】使用归并排序对整形数组进行排序

小灰灰 2022-10-01 12:54 262阅读 0赞

package edu.test;
    
    
    import java.lang.reflect.Array;
    import java.util.Arrays;
    
    public class GuiBing {
        
        public static void sort(int a[]){
        
            int l=0;
            int r=a.length-1;
            //归并
            devide(a,l,r);
        }
        /**
         * 归：分治
         */
        private static void devide(int a[],int left, int right){
        
            //归
            int mid=(left+right)/2;
            if(left<right){
        
    
                devide(a,left,mid);
                devide(a,mid+1,right);
                //并
                merge(a,left,mid,mid+1,right);
            }
        }
        private static void merge(int a[], int left, int mid, int i, int right) {
        
            int[]temp= new int[a.length];
            int index=left;
            int ls=left,le=mid;//左起~左结束
            int rs=i,re=right;//右start~右end
            //至少把一边排好
            while(ls<=le&&rs<=re){
        
                if (a[ls]<a[rs]){
        
                    temp[index]=a[ls];
                    ls++;
                }else{
        
                    temp[index]=a[rs];
                    rs++;
                }
                index++;
            }
            //判断左边是否有剩余
            if(ls<=le){
        
                for (int j=ls;j<=le;j++){
        
                    temp[index++]=a[j];
                }
            }
            if (rs<=re){
        
                for (int j=rs;j<=re;j++){
        
                    temp[index++]=a[j];
                }
            }
            for(int j=left;j<=right;j++){
        
                a[j]=temp[j];
            }
        }
    }

public class Test {
        
        public static void main(String[] args) {
        
            int a[] = {
        10, 12, 55, 11, 54, 22, 5, 7, 2, 4};
            edu.test.GuiBing.sort(a);
            StringBuffer str=new StringBuffer();
            for(int i=0;i<a.length;i++) {
        
                if(i==a.length-1) {
        
                    str.append(a[i]);
                }else {
        
                    str.append(a[i]+" ");
                }
            }
            String s=str.toString();
            System.out.println(s);
        }
    }

![在这里插入图片描述][2019061210524637.png]

[2019061210524637.png]: /images/20220118/909677426d114d0cba6cef22bd6e7d72.png