在本文中，我们将讨论合并排序算法。我们将看到一些可视化示例来帮助理解算法，然后使用Java和Python代码实现它。
什么是合并排序算法？
合并排序算法是一种基于分而治之算法的高效排序算法。它将元素的集合（数组）划分为单个单元，然后以有序的方式合并它们。
让我们看一个示例来了解合并排序的工作原理。
我们将使用合并排序算法对以下数字数组进行排序：4、10、6、14、2、1、8、5
这是一张图片，向您展示“划分”过程：
该数组最初被分成两个单独的数组。然后这些阵列也被分割。这种划分一直持续到数组中的所有元素都成为一个单元。
在此阶段之后，合并开始。这是如何发生的：
这些元素被重新组合成数组，但这次是按排序顺序排列的。就像它们被分割开来一样，它们正在被合并。
在我们使用代码实现此算法之前，您应该了解我们如何能够按排序顺序收集这些元素。
我们将使用将元素重新组合成两个独立数组的部分 - 4，6，10，14和1，2，5，8。下面是一个插图，用于了解我们如何到达最终数组：
从上面可以看出，我们有两个箭头指向两个数组的第一个索引。将进行比较以确定哪个索引较小。在我们的例子中，1 小于 4，因此将被推送到合并的数组。然后，红色箭头将移动到下一个索引。那是：
将进行另一个比较：2<4？
2 小于 4，因此它将被推送到合并的数组，箭头移动到下一个索引。
对于下一个比较：
4 小于 5，因此 4 将被推送到合并的数组，青色箭头将移动到下一个索引。
此比较将继续，直到合并的数组被填满。如果它到达一个数组变为空的点，则剩余元素的数组将按排序顺序复制到合并的数组中。
让我们看一些代码示例！
Java 中的合并排序示例
如果我们想用Java实现合并排序，下面是这样的：
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]);}}
在上面，我们创建了数字数组。之后，我们调用该方法对数字进行排序。然后，我们循环浏览排序后的数字数组，并将它们打印到控制台。 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);}
我们通过将数组长度除以 2 来获得数组的中点。左数组从第一个索引开始到中点，而右数组从中点之后的索引开始到数组结束的位置。
然后，我们创建了两个循环，根据元素的位置将元素复制到左右数组中。然后，我们在左侧和右侧数组上调用该方法。这将不断以递归方式分解数组，直到数组减少到单个单元（就像我们在上一节中的图像中看到的那样）。 mergeSort
最后，我们调用该方法以按排序顺序将数组合并到一个数组中。让我们看一下该方法中使用的逻辑。 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++;}}
还记得上一节中图像中的箭头吗？我们在这里使用和然后对于合并数组来表示它们，其中数字将按排序顺序推送到其中。 x y z
while 循环用于对两个数组进行比较并更改 的位置，以及当元素被推入合并的数组时。 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)
此处的逻辑与上一节中的逻辑完全相同。上面，我们使用Python实现了合并排序算法。您可以在上一节中找到有关代码工作原理的说明。
合并排序的时间复杂度对于所有情况（最佳、平均和最差）均为 O（n*Log n）。
结论
在本文中，我们了解了合并排序算法的工作原理。然后，我们看到了一些示例以及如何在Java和Python代码中应用它。
祝您编码愉快！
