Java 中的歸併排序

每個程式設計師都必須先思考未來工作的方案/計畫/架構，否則一切都會一團糟，完全無政府狀態。與任何帖子一樣，您最初需要一個計劃，讓我們開始吧。

• 1）讓我們以初學者的歸併排序為主題。
• 2）我們將為進一步的工作創建一個架構和計劃。
• 3) 我們將研究並描述計劃的所有部分。
• 4）讓我們檢查一下性能和品質。

• 2.1）什麼是歸併排序。
• 2.2) 可能簽名的描述。
• 2.3）舉個例子。
• 2.4) 使用範例描述 Java 中的實作。
• 2.5）任何額外的東西。

合併——Java中的合併排序

隱含著「分而治之」的原則。這個想法和意義是什麼？

1. 排序。

   我們將陣列分成幾個部分，直到它等於 1 個元素。每 1 個元素都已排序。

2. 合併。

   合併已排序的元素。
   基於兩副牌的原理。我們將 2 副牌放在桌上，牌值朝上，最低的牌放在第三堆牌中。最終，如果我們用完某一副牌中的牌，我們會將它們一張一張地移動到最終的牌組中。結果將是兩個已排序數組的合併，一個新的已排序數組。

花費的時間是O(n log2 n)。排序被認為是相當快的。 簡單說一下演算法複雜度，如果有人需要的話， 你常常可以看到這樣的函數：

Sort(A, p, q);
Merge(A, p, q, r);

這是同樣的事情，只是與索引相關。其中的變數有：

A = Array = Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q + 1 - начало второго массива
r - конец второго массива

如果不描述這些變量，那麼要求自己製作這樣一個函數的人就不知道自己想要什麼。你必須在谷歌上搜尋才能找到它是什麼，也許你會找到它。讓我們舉一個排序的例子。有一個數組{6, 1, 3, 5, 2, 4, 7, 8}，如果它的長度大於1，那麼我們將它分成兩部分，得到左部分{6, 1, 3, 5}和右部分{2, 4, 7, 8}。我們繼續進行分成2部分的動作，直到其長度大於1。這樣，我們就得到了一堆長度為1個元素的數組，即：{6} {1} {3} {5} {2} {4} {7} {8}。Java 中的實作是這樣的：

public int [] sortArray(int[] arrayA){ // sorting Массива который передается в функцию
        // проверяем не нулевой ли он?
        if (arrayA == null) {
            return null;
        }
        // проверяем не 1 ли элемент в массиве?
        if (arrayA.length < 2) {
            return arrayA; // возврат в рекурсию в строки ниже см комменты.
        }
        // копируем левую часть от начала до середины
        int [] arrayB = new int[arrayA.length / 2];
        System.arraycopy(arrayA, 0, arrayB, 0, arrayA.length / 2);

        // копируем правую часть от середины до конца массива, вычитаем из длины первую часть
        int [] arrayC = new int[arrayA.length - arrayA.length / 2];
        System.arraycopy(arrayA, arrayA.length / 2, arrayC, 0, arrayA.length - arrayA.length / 2);

        // рекурсией закидываем поделенные обе части обратно в наш метод, он будет крутится до тех пор,
        // пока не дойдет до 1 element в массиве, после чего вернется в строку и будет искать второй такой же,
        // точнее правую часть от него и опять вернет его назад
        arrayB = sortArray(arrayB); // левая часть возврат из рекурсии строкой return arrayA;
        arrayC = sortArray(arrayC); // правая часть возврат из рекурсии строкой return arrayA;

        // далее опять рекурсия возврата слияния двух отсортированных массивов
        return mergeArray(arrayB, arrayC);
    }

接下來，您需要將這些數字組合併為 1。這是如何完成的？為了避免多次遍歷每個數組，讓我們輸入每個數組的位置索引。然後我們將循環一次，循環的長度等於這兩個數組總和的長度。取第一個數組和第二個數組，並取第一個元素，比較第一個數組中的元素號 1和第二個數組中的元素號 1？較小的一個放入結果陣列中。這裡重要的是，如果我們從第一個陣列中取出一個元素，那麼當循環通過時，它應該會引用第一個陣列的第二個元素和第二個陣列的第一個元素。為此，您需要將第二個陣列的索引增加 +1，並在檢查時從循環數中減去它，與第一個陣列類似。清楚為什麼要這樣做嗎？或者根本就什麼都不清楚？:-) 例如，有 2 個陣列： {1}{4}{8}and{3}{6}{7} 並且有一個循環：

for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i] < arrayB[i]) {
	arrayC[i] = arrayA[i];
	} else {
	arrayC[i] = arrayB[i];
	}
}

在循環的第一遍中，事實證明arrayC[1] = {1}：我們從第一個數組中獲取了這個元素。然後，當進行第二個循環時，我們必須已經比較元素{4}和{3}，但為了做到這一點，我們需要考慮兩個陣列的位置索引和偏移量，為此我們輸入它們。

int positionA = 0, positionB = 0;
for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}

但這還不是全部，您需要考慮到某些數組可能會提前結束。例如，有3個陣列： {1}{3}{5}並且{6}{7}{9} 第一個陣列將在第二個陣列到達之前結束，為此您需要輸入檢查，原則上合併功能已準備就緒。

public int [] mergeArray(int [] arrayА, int [] arrayB) {

int [] arrayC = int[arrayA.length + arrayB.length];
int positionA = 0, positionB = 0;

for (int i = 0; i < arrayC.length; i++) {
	if (positionA == arrayA.length){
	arrayC[i] = arrayB[i - positionB];
	positionB++;
	} else if (positionB == arrayB.length) {
	arrayC[i] = arrayA[i - positionA];
	positionA++;
	} else if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}
return arrayC;

這種排序最難的就是遞歸過渡的原理。那些。我們把左邊扔進遞歸，直到它能被2整除，然後再把它展開回來，用語言來說，這是非常複雜和混亂的，但是當你嘗試想像時，如果還不清楚，那就一團糟了。讓我們來看看數組：{2}{1}{4}{3}。第一次排序遞歸將其分成兩部分，然後對元素2-1再次運行該函數，然後再次對元素2和1運行該函數，依次返回它們，因此它們將首先進入合併函數，然後1-2會出現out ，然後遞歸將返回並將4-3放入合併中，然後是4和3，之後合併將返回3-4，然後遞歸將再次旋轉回來，並且1-2和3-4將包含在合併中，排序後的陣列將傳回1-2-3-4。好了，就是這樣，排序由兩個函數組成。

sortArray(array); 			// кладем массив который нужно отсортировать
mergeArray(arrayA, arrayB); 	// кладем 2 массива которые нужно слить в один

如果你寫下某種 main，你會得到類似的東西：

public static void main(String[] args) {
        Merge testMerge = new Merge();
        int [] result = testMerge.sortArray(new int[]{2,3,1,4});

        for (int i = 0; i < result.length ; i++) {
            System.out.print(result[i] + " ");
        }
    }

對我來說，這次排序完全失敗了，有一百萬個問題，但沒有答案，我翻遍了整個互聯網，重新閱讀，觀看了一堆視頻，但一如既往，我只能自己找到答案。只有當我開始編寫一個與到處閃爍的解決方案完全不同的解決方案時）但最終結果與所有其他解決方案相似）））排序實際上是最簡單的，主要是在操作中以交互方式呈現它，而且如果你掌握了竅門，一切都會就位，我會製作一個視頻）））到目前為止，這就是我已經受夠了的：合併排序 合併排序 最重要的是始終制定計劃開始。在開始做任何事情之前最好先等一下並思考一下。這可能需要更多時間，但理解和解決方案將會出現，而不是必須重寫幾次並想出拐杖。感謝大家抽出寶貴的時間，祝你好運和好心情。）PS：非常歡迎批評，好的和壞的，以及問題。）））