Java歸并排序算法代碼實現(xiàn)

更新時間：2024年03月02日 14:24:31 作者：顧城猿

歸并(Merge)排序法是將兩個(或兩個以上)有序表合并成一個新的有序表,即把待排序序列分為若干個子序列,每個子序列是有序的,下面這篇文章主要給大家介紹了關(guān)于Java歸并排序算法的相關(guān)資料,需要的朋友可以參考下

歸并排序是常見的八大排序算法之一，歸并排序也是一種時間復(fù)雜度比較好的一種算法，為0(n*logn)級別。

歸并排序可以用遞歸和非遞歸兩種方式來實現(xiàn)，當然，遞歸方法是比較簡單的，而非遞歸則是相對而言比較難的一種思路。

歸并排序的總體思路就是將一個大的無序數(shù)組，劃分為多個內(nèi)部有序的數(shù)組，而組間可能是無序的，通過合并相鄰兩組得到一個新的有序數(shù)組來實現(xiàn)，最終合并成總體的大數(shù)組，即完成排序。

因此，對于歸并排序，我們需要先向下分組，然后再將各個數(shù)組合并，得到一個新的數(shù)組，直到最后合并成一個數(shù)組，算法結(jié)束。

具體細節(jié)，則是通過將大數(shù)組劃分，首先劃分為每一組單個元素，單個元素的數(shù)組可以認為是有序的。如何依次從左向右，每次取兩個相鄰數(shù)組，進行合并，即兩個有序數(shù)組的合并，合并完以后，再找下一組兩個相鄰的數(shù)組進行合并（并不包括上次合并好的數(shù)組），直到最后只有一個組或者沒有組了，就重新從頭開始合并，繼續(xù)上述步驟。

對于遞歸寫法，我們可以認為數(shù)組中的各個元素都是二叉樹的葉子結(jié)點，依據(jù)上述思路，兩兩合并成一個結(jié)點，最后合并成一個結(jié)點，即排序結(jié)束。

對于非遞歸寫法，我們可以設(shè)置一個變量來存儲要比較的數(shù)組長度，從一開始，到數(shù)組長度結(jié)束，即使分開后的數(shù)組元素個數(shù)并不等于這個變量，只要有和他配對的就可以合并。

代碼測試通過力扣中的題目進行測驗。

代碼實現(xiàn)：

遞歸：

class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums,0,nums.length-1);
        return nums;
    }
    public void mergeSort(int[] nums,int left,int right){
        if(right==left){
            return;
        }
        int center=(left+right)/2;
        mergeSort(nums,left,center);
        mergeSort(nums,center+1,right);
        merge(nums,left,center,right);
    }
    public void merge(int[] nums,int left,int center,int right){
        int i=left;
        int j=center+1;
        int[] temp=new int[right-left+1];
        int count=0;
        while(i<=center && j<=right){
            temp[count++]=nums[i]>nums[j]?nums[j++]:nums[i++];
        }
        while(i<=center){
            temp[count++]=nums[i++];
        }
        while(j<=right){
            temp[count++]=nums[j++];
        }
        for(int k=0;k<temp.length;k++){
            nums[left+k]=temp[k];
        }
    }
}

力扣提交結(jié)果：

非遞歸：

class Solution {
    public int[] sortArray(int[] nums) {
        for(int l,m,r,step=1;step<nums.length;step*=2){
            l=0;//設(shè)置初始值
            while(l<nums.length){//有左邊的組
                m=l+step-1;
                if(m+1>=nums.length){//如果沒有右邊的組，就退出
                    break;
                }
                r=Math.min(l+(step*2)-1,nums.length-1);//獲取右邊界，取兩者的最小值
                merge(nums,l,m,r);//將兩個組合并
                l=r+1;//找到下一個左邊的組
            }
        }
        return nums;
    }
    public void merge(int[] nums,int left,int center,int right){
        int i=left;
        int j=center+1;
        int[] temp=new int[right-left+1];
        int count=0;
        while(i<=center && j<=right){
            temp[count++]=nums[i]>nums[j]?nums[j++]:nums[i++];
        }
        while(i<=center){
            temp[count++]=nums[i++];
        }
        while(j<=right){
            temp[count++]=nums[j++];
        }
        for(int k=0;k<temp.length;k++){
            nums[left+k]=temp[k];
        }
    }
}

力扣提交結(jié)果：