在本文中，我們將討論合并排序算法。我們將看到一些可視化示例來幫助理解算法，然后使用Java和Python代碼實現(xiàn)它。

　　什么是合并排序算法？

　　合并排序算法是基于分而治之算法的高效排序算法。它將元素的集合(數(shù)組)劃分為單個單元，然后以有序的方式合并它們。

　　讓我們看一個示例來了解合并排序的工作原理。

　　我們將使用合并排序算法對以下數(shù)字數(shù)組進行排序：4， 10， 6， 14， 2， 1， 8， 5

　　下圖顯示了“劃分”過程：

　　該數(shù)組首先分為兩個單獨的數(shù)組。然后這些陣列也被分割。這種劃分一直持續(xù)到陣列中的所有元素都成為一個單元。

　　在此階段之后，合并開始。這是如何發(fā)生的：

　　這些元素正在重新分組到數(shù)組中，但這次是按排序順序排列的。就像它們被拆分一樣，它們正在被合并。

　　在我們使用代碼實現(xiàn)此算法之前，您應(yīng)該了解我們?nèi)绾文軌虬磁判蝽樞蚴占@些元素。

　　我們將使用將元素重新組合成兩個單獨數(shù)組的部分 - 4，6，10，14和1，2，5，8。下面是一個插圖，用于了解我們是如何到達最終數(shù)組的：

　　如上所示，我們有兩個箭頭指向兩個數(shù)組的第一個索引。將進行比較以找出哪個索引較小。在我們的例子中，1小于4，因此將被推送到合并的數(shù)組。然后，紅色箭頭將移動到下一個索引。那是：

　　將進行另一個比較：2<4?

　　2 小于 4，因此它將被推送到合并的數(shù)組，箭頭移動到下一個索引。

　　對于下一個比較：

　　4 小于 5，因此 4 將被推送到合并的數(shù)組，青色箭頭將移動到下一個索引。

　　這種比較將一直持續(xù)到合并的數(shù)組被填滿。如果它到達一個數(shù)組變?yōu)榭盏狞c，則具有剩余元素的數(shù)組將按排序順序復(fù)制到合并的數(shù)組中。

　　讓我們看一些代碼示例！

　　Java 中的合并排序示例

　　如果我們想用Java實現(xiàn)合并排序，那會是什么樣子：

　　讓我們分解代碼。

　　在上面，我們創(chuàng)建了數(shù)字數(shù)組。之后，我們調(diào)用該方法對數(shù)字進行排序。然后，我們循環(huán)遍歷排序后的數(shù)字數(shù)組，并將它們打印到控制臺。mergeSort

　　我們通過將數(shù)組長度除以二來獲得數(shù)組的中點。左數(shù)組從第一個索引開始到中點，而右數(shù)組從中點之后的索引開始到數(shù)組結(jié)束的位置。

　　然后，我們創(chuàng)建了兩個循環(huán)，根據(jù)元素的位置將元素復(fù)制到左側(cè)和右側(cè)數(shù)組中。然后，我們在左側(cè)和右側(cè)數(shù)組中調(diào)用該方法。這將以遞歸方式分解數(shù)組，直到數(shù)組被縮減為單個單元(就像我們在上一節(jié)中的圖像中看到的那樣)。mergeSort

　　最后，我們調(diào)用該方法以按排序順序?qū)?shù)組合并為一個數(shù)組。讓我們看一下該方法中使用的邏輯。merge merge

　　還記得上一節(jié)中圖像中的箭頭嗎?我們在這里使用然后用于合并數(shù)組來表示它們，其中數(shù)字將按排序順序推入其中。xyz

　　while 循環(huán)用于在兩個數(shù)組上進行比較并更改 的位置，并且當(dāng)元素被推入合并數(shù)組時。xyz

　　Python 中的插入排序示例

　　此處的邏輯與上一節(jié)中的邏輯完全相同。上面，我們使用Python實現(xiàn)了合并排序算法。您可以在上一節(jié)中找到有關(guān)代碼工作原理的說明。

　　合并排序的時間復(fù)雜度是 O(n*Log n)適用于所有情況(最佳、平均和最差)。

　　結(jié)論

　　在本文中，我們了解了合并排序算法的工作原理。然后，我們看到了一些示例以及如何在 Java 和 Python 代碼中應(yīng)用它。