java怎么實現歸并排序

這篇文章主要介紹“java怎么實現歸并排序”，在日常操作中，相信很多人在java怎么實現歸并排序問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”java怎么實現歸并排序”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

public class MergeSort {
    public static int arr[] = {2,4,7,8,9,4,5,1,2,3,6,8,7,8,54,4,2,58,47,5,8,4,2,5,0,0};
    public static void main(String[] args) {
        sort(0,arr.length-1);   //排序
        print();    //打印
    }

    //拆分
    public static void sort(int left,int right){
        if(left >= right)
            return;
        //遞歸終止條件，一個子數組只有一個或兩個元素
        if(right-left==1){
            if(arr[left]>arr[right]){
                int t = arr[left];
                arr[left] = arr[right];
                arr[right] = t;
            }
            return;
        }
        //遞歸分解
        int mid = (left + right)/2;
        sort(left,mid);
        sort(mid+1,right);
        //合并
        merge(left,mid,right);
    }
    //合并
    public static void merge(int left,int mid,int right){
        int i = left;
        int j = mid+1;
        int k = 0;
        //開辟臨時數組，合并兩個有序子數組
        int temp[] = new int[right-left+1];
        while(i<=mid && j<=right){
            if(arr[i]<arr[j]){
                temp[k++] = arr[i++];
            }else{
                temp[k++] = arr[j++];
            }
        }
        while(i<=mid){
            temp[k++] = arr[i++];
        }
        while(j<=right){
            temp[k++] = arr[j++];
        }
        //將臨時數組合并到原來數組中
        k = 0;
        for(i = left;i<=right;i++){
            arr[i] = temp[k++];
        }
    }

    /**
     * 打印
     */
    public  static void print(){
        for(int a:arr){
            System.out.print(a+",");
        }
        System.out.println();
    }
}

歸并排序，平均復雜度nlogn

到此，關于“java怎么實現歸并排序”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！