在本文中喉誊，我們將討論合并排序算法。我們將看到一些可視化示例來幫助理解算法掘剪，然后使用Java和Python代碼實(shí)現(xiàn)它腻格。
什么是合并排序算法画拾？
合并排序算法是一種基于分而治之算法的高效排序算法。它將元素的集合（數(shù)組）劃分為單個(gè)單元菜职，然后以有序的方式合并它們青抛。
讓我們看一個(gè)示例來了解合并排序的工作原理。
我們將使用合并排序算法對(duì)以下數(shù)字?jǐn)?shù)組進(jìn)行排序：4酬核、10蜜另、6、14嫡意、2举瑰、1、8蔬螟、5
這是一張圖片此迅，向您展示“劃分”過程：
該數(shù)組最初被分成兩個(gè)單獨(dú)的數(shù)組。然后這些陣列也被分割旧巾。這種劃分一直持續(xù)到數(shù)組中的所有元素都成為一個(gè)單元邮屁。
在此階段之后，合并開始菠齿。這是如何發(fā)生的：
這些元素被重新組合成數(shù)組，但這次是按排序順序排列的坐昙。就像它們被分割開來一樣绳匀，它們正在被合并。
在我們使用代碼實(shí)現(xiàn)此算法之前炸客，您應(yīng)該了解我們?nèi)绾文軌虬磁判蝽樞蚴占@些元素疾棵。
我們將使用將元素重新組合成兩個(gè)獨(dú)立數(shù)組的部分 - 4，6痹仙，10是尔，14和1，2开仰，5拟枚，8薪铜。下面是一個(gè)插圖，用于了解我們?nèi)绾蔚竭_(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)合并排序，下面是這樣的：
publicclassMergeSort{publicstaticvoidmain(String[]args){int[]numbers={4,10,6,14,2,1,8,5};mergeSort(numbers);System.out.println("Sorted array:");for(inti=0;i<numbers.length;i++){System.out.println(numbers[i]);}}privatestaticvoidmergeSort(int[]inputArray){intarrayLength=inputArray.length;if(arrayLength<2){return;}intmidPoint=arrayLength/2;int[]leftArray=newint[midPoint];int[]rightArray=newint[arrayLength-midPoint];for(inti=0;i<midPoint;i++){leftArray[i]=inputArray[i];}for(inti=midPoint;i<arrayLength;i++){rightArray[i-midPoint]=inputArray[i];}mergeSort(leftArray);mergeSort(rightArray);merge(inputArray,leftArray,rightArray);}privatestaticvoidmerge(int[]inputArray,int[]leftArray,int[]rightArray){intleftArrayLength=leftArray.length;intrightArrayLength=rightArray.length;intx=0;inty=0;intz=0;while(x<leftArrayLength&&y<rightArrayLength){if(leftArray[x]<=rightArray[y]){inputArray[z]=leftArray[x];x++;}else{inputArray[z]=rightArray[y];y++;}z++;}while(x<leftArrayLength){inputArray[z]=leftArray[x];x++;z++;}while(y<rightArrayLength){inputArray[z]=rightArray[y];y++;z++;}}}
讓我們分解一下代碼常侦。
publicstaticvoidmain(String[]args){int[]numbers={4,10,6,14,2,1,8,5};// 1, 2, 4, 5, 6, 8, 10, 14mergeSort(numbers);System.out.println("Sorted array:");for(inti=0;i<numbers.length;i++){System.out.println(numbers[i]);}}
在上面浇冰，我們創(chuàng)建了數(shù)字?jǐn)?shù)組。之后聋亡，我們調(diào)用該方法對(duì)數(shù)字進(jìn)行排序肘习。然后，我們循環(huán)瀏覽排序后的數(shù)字?jǐn)?shù)組坡倔，并將它們打印到控制臺(tái)漂佩。?mergeSort
privatestaticvoidmergeSort(int[]inputArray){intarrayLength=inputArray.length;if(arrayLength<2){return;}intmidPoint=arrayLength/2;int[]leftArray=newint[midPoint];int[]rightArray=newint[arrayLength-midPoint];for(inti=0;i<midPoint;i++){leftArray[i]=inputArray[i];}for(inti=midPoint;i<arrayLength;i++){rightArray[i-midPoint]=inputArray[i];}mergeSort(leftArray);mergeSort(rightArray);merge(inputArray,leftArray,rightArray);}
我們通過將數(shù)組長(zhǎng)度除以 2 來獲得數(shù)組的中點(diǎn)。左數(shù)組從第一個(gè)索引開始到中點(diǎn)罪塔，而右數(shù)組從中點(diǎn)之后的索引開始到數(shù)組結(jié)束的位置投蝉。
然后，我們創(chuàng)建了兩個(gè)循環(huán)征堪，根據(jù)元素的位置將元素復(fù)制到左右數(shù)組中瘩缆。然后，我們?cè)谧髠?cè)和右側(cè)數(shù)組上調(diào)用該方法佃蚜。這將不斷以遞歸方式分解數(shù)組庸娱，直到數(shù)組減少到單個(gè)單元（就像我們?cè)谏弦还?jié)中的圖像中看到的那樣）着绊。?mergeSort
最后，我們調(diào)用該方法以按排序順序?qū)?shù)組合并到一個(gè)數(shù)組中涌韩。讓我們看一下該方法中使用的邏輯畔柔。?merge?merge
privatestaticvoidmerge(int[]inputArray,int[]leftArray,int[]rightArray){intleftArrayLength=leftArray.length;intrightArrayLength=rightArray.length;intx=0;inty=0;intz=0;while(x<leftArrayLength&&y<rightArrayLength){if(leftArray[x]<=rightArray[y]){inputArray[z]=leftArray[x];x++;}else{inputArray[z]=rightArray[y];y++;}z++;}while(x<leftArrayLength){inputArray[z]=leftArray[x];x++;z++;}while(y<rightArrayLength){inputArray[z]=rightArray[y];y++;z++;}}
還記得上一節(jié)中圖像中的箭頭嗎？我們?cè)谶@里使用和然后對(duì)于合并數(shù)組來表示它們臣樱，其中數(shù)字將按排序順序推送到其中靶擦。?x?y?z
while 循環(huán)用于對(duì)兩個(gè)數(shù)組進(jìn)行比較并更改 的位置，以及當(dāng)元素被推入合并的數(shù)組時(shí)雇毫。?x?y?z
Python 中的插入排序示例
defmergeSort(array):iflen(array)>1:midPoint=len(array)//2leftArray=array[:midPoint]rightArray=array[midPoint:]mergeSort(leftArray)mergeSort(rightArray)x=0y=0z=0whilex<len(leftArray)andy<len(rightArray):ifleftArray[x]<rightArray[y]:array[z]=leftArray[x]x+=1else:array[z]=rightArray[y]y+=1z+=1whilex<len(leftArray):array[z]=leftArray[x]x+=1z+=1whiley<len(rightArray):array[z]=rightArray[y]y+=1z+=1defprintSortedArray(array):foriinrange(len(array)):print(array[i],end=" ")print()if__name__=='__main__':numbers=[4,10,6,14,2,1,8,5]mergeSort(numbers)print("Sorted array: ")printSortedArray(numbers)
此處的邏輯與上一節(jié)中的邏輯完全相同玄捕。上面，我們使用Python實(shí)現(xiàn)了合并排序算法棚放。您可以在上一節(jié)中找到有關(guān)代碼工作原理的說明枚粘。
合并排序的時(shí)間復(fù)雜度對(duì)于所有情況（最佳、平均和最差）均為 O（n*Log n）飘蚯。
結(jié)論
在本文中馍迄，我們了解了合并排序算法的工作原理。然后局骤，我們看到了一些示例以及如何在Java和Python代碼中應(yīng)用它攀圈。
祝您編碼愉快！
