使用 Python 解释归并排序

归并排序是一种排序技术。它是一种有效的排序算法，其时间复杂度为 (n logn)，其中 n 为要排序的数组长度。

归并排序是一种遵循分而治之范式的算法。它不断地将数组分成两半。然后，它开始对每个元素都为一个元素的列表进行排序，并不断合并已排序的列表以形成完整排序的列表。

因此，我们得到一个排序好的数组。

示例

紫色方框和黑色箭头显示了将列表分成两半的方式。

绿色方框和红色箭头显示了两个已排序列表的合并方式。

实现归并排序

将列表分成两半非常容易，并且我们会递归地执行这项操作，直到只剩下一个元素。然后进行合并过程，我们实际上是在该过程中应用将两个已排序列表合并在一起的逻辑。

示例

merge 函数将两个要合并的已排序数组收录进去。将 a1 中的最前面元素与 a2 中的最前面元素进行比较。两个元素中较小的一个添加到列表 c 中，并且会增加该数组的指针。

 动态演示

def merge(a1,a2):
   c=[]
   x=0
   y=0
   while(x<len(a1) and y<len(a2)):
      if(a1[x]<a2[y]):
         c.append(a1[x])
         x+=1
      else:
         c.append(a2[y])
         y+=1
   while(x<len(a1)):
      c.append(a1[x])
      x+=1
   while(y<len(a2)):
      c.append(a2[y])
      y+=1
   return c

def mergesort(array):
   if(len(array)==1):
      return array
   mid=(len(array))//2
   a1=mergesort(array[:mid])
   a2=mergesort(array[mid:])
   return merge(a1,a2)
array=[2,3,1,5,4,6,8,10,7,9]
print(mergesort(array))

输出

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

更新于: 2021 年 3 月 11 日

878 次观看

开启你的职业生涯

通过完成课程，取得认证

开始
广告