1.歸并排序算法思想

也稱合并排序算法，是將兩個(gè)或兩個(gè)以上的有序數(shù)據(jù)序列合并成一個(gè)新的有序數(shù)據(jù)序列。該算法采用分治法（Divide and Conquer）的思想，將待排序的序列分成若干個(gè)子序列，分別對(duì)子序列進(jìn)行排序，然后將有序的子序列合并成一個(gè)大的有序序列
注：將幾個(gè)有序隊(duì)列合并成一個(gè)新的有序數(shù)據(jù)隊(duì)列就稱為幾路歸并排序算法

2.歸并排序算法實(shí)現(xiàn)步驟

歸并排序的基本步驟如下：
（1）分解
將待排序的序列分成若干個(gè)子序列，每個(gè)子序列都是有序的。這是通過遞歸實(shí)現(xiàn)的，每次遞歸都將原序列分成兩個(gè)子序列
（2）解決
對(duì)每個(gè)子序列進(jìn)行排序。這是通過遞歸調(diào)用的方式實(shí)現(xiàn)的，遞歸調(diào)用歸并排序函數(shù)對(duì)子序列進(jìn)行排序。
（3）歸并
將已排序的子序列歸并成一個(gè)大的有序序列。這是通過歸并操作實(shí)現(xiàn)的，將兩個(gè)有序的子序列歸并成一個(gè)新的有序序列。在歸并的過程中，采用歸并算法（Merge Algorithm）將兩個(gè)有序的子序列歸并成一個(gè)新的有序序列。具體操作如下：
1）初始化兩個(gè)指針i和j，分別指向兩個(gè)子序列的起始位置。
2）比較兩個(gè)指針?biāo)赶虻脑?，將較小的元素復(fù)制到一個(gè)臨時(shí)數(shù)組中，然后將指針加1，繼續(xù)比較下一個(gè)元素。
3）當(dāng)一個(gè)指針到達(dá)子序列的末尾時(shí)，將另一個(gè)子序列剩余的元素復(fù)制到臨時(shí)數(shù)組中。
4）將臨時(shí)數(shù)組中的元素復(fù)制回原數(shù)組，完成合并操作。
通過遞歸調(diào)用和合并操作，最終得到一個(gè)有序的序列文章來源地址http://www.zghlxwxcb.cn/news/detail-797016.html

3.歸并排序算法性能分析

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

public class Demo {
    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10};
        mergeSort(arr,0,arr.length-1);
        for(int i:arr){
            System.out.println(i);
        }
    }
    //歸并排序的歸并操作
    public static void merge(int[] arr,int low,int mid ,int high){
        int i,j,k;
        int[] tempArr = new int[arr.length];//輔助數(shù)據(jù)
        for(k = low; k <=high; k++){ //將原數(shù)組復(fù)制到輔助數(shù)組中
            tempArr[k] = arr[k];
        }
        //arr[low...mid]和arr[mid+1...high]各自有序，將兩個(gè)部分歸并
        for(i=low, j=mid+1, k=i; i<=mid && j <= high; k++){
            if(tempArr[i] > tempArr[j]){ //“>”號(hào)代表升序，“<”號(hào)代表降序
                arr[k] = tempArr[i++];
            }else{
                arr[k] = tempArr[j++];
            }
        }
        while(i <= mid){ //將左半部分的剩余元素依次放入到新數(shù)組中
            arr[k] = tempArr[i++];
            k++;
        }
        while( j <= high){ //將右半部分的剩余元素依次放入到新數(shù)組中
            arr[k] = tempArr[j++];
            k++;
        }
    }
    //歸并排序的遞歸部分
    public static void mergeSort(int[] arr,int low,int high){
       if(low < high){ // 遞歸結(jié)束條件
           int mid = (low + high)/2;
           mergeSort(arr,low,mid); //對(duì)數(shù)組左半部分歸并排序
           mergeSort(arr,mid+1,high); //對(duì)數(shù)組右半部分歸并排序
           merge(arr,low,mid,high); //歸并
       }
    }
}

到了這里，關(guān)于歸并排序算法（Java實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！