快捷導(dǎo)航

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

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

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

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

歸并排序可以用遞歸和非遞歸兩種方式來(lái)實(shí)現(xiàn)，當(dāng)然，遞歸方法是比較簡(jiǎn)單的，而非遞歸則是相對(duì)而言比較難的一種思路。

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

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

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

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

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

代碼測(cè)試通過(guò)力扣中的題目進(jìn)行測(cè)驗(yàn)。

代碼實(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);//將兩個(gè)組合并
                l=r+1;//找到下一個(gè)左邊的組
            }
        }
        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é)果：