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

　　什么是合并排序算法？

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

　　讓我們看一個(gè)示例來(lái)了解合并排序的工作原理。

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

　　下圖顯示了“劃分”過(guò)程：

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

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

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

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

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

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

　　將進(jìn)行另一個(gè)比較：2<4?

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

　　對(duì)于下一個(gè)比較：

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

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

　　讓我們看一些代碼示例！

　　Java 中的合并排序示例

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

　　讓我們分解代碼。

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

　　我們通過(guò)將數(shù)組長(zhǎng)度除以二來(lái)獲得數(shù)組的中點(diǎn)。左數(shù)組從第一個(gè)索引開始到中點(diǎn)，而右數(shù)組從中點(diǎn)之后的索引開始到數(shù)組結(jié)束的位置。

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

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

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

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

　　Python 中的插入排序示例

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

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

　　結(jié)論

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