与Go学习算法今天继续上基本排序算法的图和Go代码的实现。这次分享一个时间复杂度为***的。时间复杂度先保密，文末会有分析。本次分享的排序算法是MergeSort。归并排序的思想和快速排序是一样的。归并排序也采用分而治之的策略。将原问题分解成一些小问题来解决，然后将这些小问题的答案修剪在一起，得到原问题的答案。达到分而治之的目的。归并排序算法将待排序序列分成两个等长的子序列，当每个子序列只有一个数据时，将子序列合并。合并是指将两个已排序的子序列合并为一个已排序的序列。重复此操作，直到所有子序列合并为一个整体。归并排序的过程接下来，我们还是用图例来走一遍通过归并排序对一个序列进行排序的过程。传说来自——《我的第一本算法书》首先，假设有一个待排序的数列如下：一系列待排序的数将数列分成两半。将序列分成两段，然后继续将子序列分成两半，分解。继续划分，直到没有划分，并且每个子序列中只有一个数据。分解直到每个子序列只有一个数据，然后合并分割后的数据。合并时，数字需要按升序排列。合并序列时，根据大小对6和4进行排序。合并的时候，按照数字的大小排序。合并后的顺序是[4,6]。接下来合并3和7，合并后的顺序为[3,7]。[继续按大小顺序合并以下序列](/Users/klein/Library/ApplicationSupport/typora-user-images/image-20220405142734949.png)。接下来，让我们看看如何合并两个序列[4,6]和[3,7]。合并此类包含多个数字的子序列时，首先比较第一个数字，然后移动较小的数字。合并多元素序列时，从第一个开始比较，小的先走。这里，要比较的两个子序列的第一个数字是4和3。由于4>3，合并序列时先移动3。4>3，所以合并序列时先移3，然后合并两个序列，按照比较两个序列的第一位，小的先合并，留下大的继续比较.顺序。4小于7，所以先将4移动到合并序列中。由于4<7，移动4的两个子序列的剩余元素中，6小于7，所以先移动6。6<7，所以先移动6，最后移动剩下的7。最后在子序列中留下7，将其合并到序列中递归执行上述操作，直到所有数字合并成一个整体序列。将小序列合并成两个大序列，然后在完整序列上继续合并，得到完整的排序序列。Mergeandsort排序序列的Go代码实现记得点个赞），有空在电脑上运行试试看。packagemainimport"fmt"//自上而下归并排序，排序范围在[begin,end)arrayfuncMergeSort(array[]int,beginint,endint){//只有元素个数为才进入递归大于1end-begin>1{//将数组一分为二，分为array[begin,mid)和array[mid,high)mid:=begin+(end-begin+1)/2//对数组进行排序leftsidefirstGoodMergeSort(array,begin,mid)//排序右侧MergeSort(array,mid,end)//合并两个有序数组merge(array,begin,mid,end)}}//合并操作funcmerge(array[]int,beginint,midint,endint){//申请额外空间合并两个有序数组，两个数组为array[begin,mid),array[mid,end)leftSize:=mid-begin//左数组的长度rightSize:=end-mid//右数组的长度newSize:=leftSize+rightSize//辅助数组的长度result:=make([]int,0,newSize)l,r:=0,0forl
