# 歸并排序 Java 示例 > 原文： [https://howtodoinjava.com/algorithm/merge-sort-java-example/](https://howtodoinjava.com/algorithm/merge-sort-java-example/) 在計算機科學中，**歸并排序**（也通常稱為拼寫歸并排序）是一種基于`O(n log n)`比較的排序算法。 大多數實現都會產生[穩定排序](https://en.wikipedia.org/wiki/Sorting_algorithm#Stability)，這意味著該實現會在排序后的輸出中保留相等元素的輸入順序。 **歸并排序是一種分而治之的算法。** 分而治之算法將原始數據分為較小的數據集以解決該問題。 在歸并排序過程中，集合中的對象分為兩個集合。 要拆分集合，歸并排序將采用集合的中間部分并將其拆分為左側和右側。 通過歸并排序算法將生成的集合再次遞歸拆分，直到將其分解為每個集合中的單個元素為止。 分割每個集合后，歸并排序算法開始組合通過上述過程獲得的所有集合。 為了合并兩個集合，歸并排序從每個集合的開頭開始。 它選擇較小的對象，然后將該對象插入新集合中。 對于此集合，它現在通過一次比較每個集合中的一個元素，來選擇下一個元素，并從兩個集合中選擇較小的元素。 此過程將創建一個已排序元素的集合（所有需要排序的元素的子集）。 對于在第一步中獲得的所有可用集合，即對集合進行拆分，將以遞歸方式完成此過程。 將兩個集合中的所有元素都插入新集合后，歸并排序已成功對集合進行了排序。 為了避免創建太多集合，通常只創建一個新集合，而將新集合和現有集合視為不同的集合。 為了更好地理解，請看下面遵循上述方法的圖表。  歸并排序算法 從概念上講，歸并排序以遞歸方式進行如下工作： 1. 將未排序的列表分為兩個大小約為一半的子列表 2. 對兩個子列表中的每個列表進行排序 3. 將兩個已排序的子列表合并回一個已排序的列表 ## 歸并排序示例 在下面的示例中，我們以表達方式實現了歸并排序算法，以使其更易于理解。 在給定**歸并排序代碼**的情況下，遵循下面每個步驟/語句上方寫的注釋。 ```java import java.util.*; public class MergerSort { public static void main(String[] args) { //Unsorted array Integer[] a = { 2, 6, 3, 5, 1 }; //Call merge sort mergeSort(a); //Check the output which is sorted array System.out.println(Arrays.toString(a)); } @SuppressWarnings("rawtypes") public static Comparable[] mergeSort(Comparable[] list) { //If list is empty; no need to do anything if (list.length <= 1) { return list; } //Split the array in half in two parts Comparable[] first = new Comparable[list.length / 2]; Comparable[] second = new Comparable[list.length - first.length]; System.arraycopy(list, 0, first, 0, first.length); System.arraycopy(list, first.length, second, 0, second.length); //Sort each half recursively mergeSort(first); mergeSort(second); //Merge both halves together, overwriting to original array merge(first, second, list); return list; } @SuppressWarnings({ "rawtypes", "unchecked" }) private static void merge(Comparable[] first, Comparable[] second, Comparable[] result) { //Index Position in first array - starting with first element int iFirst = 0; //Index Position in second array - starting with first element int iSecond = 0; //Index Position in merged array - starting with first position int iMerged = 0; //Compare elements at iFirst and iSecond, //and move smaller element at iMerged while (iFirst < first.length && iSecond < second.length) { if (first[iFirst].compareTo(second[iSecond]) < 0) { result[iMerged] = first[iFirst]; iFirst++; } else { result[iMerged] = second[iSecond]; iSecond++; } iMerged++; } //copy remaining elements from both halves - each half will have already sorted elements System.arraycopy(first, iFirst, result, iMerged, first.length - iFirst); System.arraycopy(second, iSecond, result, iMerged, second.length - iSecond); } } ``` ```java Output: Input Array : [ 2, 6, 3, 5, 1, 1, 8 ] Output Array : [ 1, 1, 2, 3, 5, 6, 8 ] Input Array : [ 12, 16, 333, 50, 1000, 5, 897, 1, 3, 66, 13 ] Output Array : [ 1, 3, 5, 12, 13, 16, 50, 66, 333, 897, 1000 ] ``` ## 何時使用歸并排序 1. 當數據結構不支持隨機訪問時使用歸并排序，因為它可以與純順序訪問（正向迭代器，而不是隨機訪問迭代器）一起使用。 它也廣泛用于外部排序，與順序訪問相比，隨機訪問的費用非常高。 例如，當對不適合內存的文件進行排序時，您可以將其分成適合內存的塊，單獨使用對它們進行排序，將每個數據寫入文件，然后合并對生成的文件進行排序。 2. 另外，當您需要穩定排序時，可以使用歸并排序。 這是歸并排序的非常重要的功能。 3. 當處理鏈接列表時，歸并排序更快。 這是因為合并列表時可以輕松更改指針。 它只需要遍歷列表一次（O（n））。 4. 如果發生大量并行化，則歸并排序并行化要比其他排序算法簡單。 這就是關于歸并排序 Java 教程的全部內容。 在下面的評論部分中將您的問題/疑問交給我。 **祝您學習愉快！**