用于归并排序的 Python 程序

pythonserver side programmingprogramming

在本文中，我们将了解下面给出的问题陈述的解决方案。

问题陈述 − 我们有一个数组，我们需要使用归并排序的概念对其进行排序

在这里我们将最大元素放在末尾。重复此操作直到数组排序完成。

现在让我们观察下面实现中的解决方案 −

示例

#merge 函数
def merge(arr, l, m, r):
   n1 = m - l + 1
   n2 = r- m
   # 创建数组
   L = [0] * (n1)
   R = [0] * (n2)
   # 将数据复制到数组
   for i in range(0 , n1):
      L[i] = arr[l + i]
   for j in range(0 , n2):
      R[j] = arr[m + 1 + j]
   i = 0 # 数组的前半部分
   j = 0 # 数组的后半部分
   k = l # 合并两半
   while i < n1 and j < n2 :
      if L[i] <= R[j]:
         arr[k] = L[i]
         i += 1
      else:
         arr[k] = R[j]
         j += 1
      k += 1
   # 复制左半部分的剩余元素
   while i < n1:
      arr[k] = L[i]
      i += 1
      k += 1
   # 复制右半部分的左侧元素
   while j < n2:
      arr[k] = R[j]
      j += 1
      k += 1
# sort
def mergeSort(arr,l,r):
   if l < r:
      # getting the average
      m = (l+(r-1))/2
      # Sort
      mergeSort(arr, l, m)
      mergeSort(arr, m+1, r)
      merge(arr, l, m, r)
# main
arr = [2,5,3,8,6,5,4,7]
n = len(arr)
mergeSort(arr,0,n-1)
print ("Sorted array is")
for i in range(n):
   print (arr[i],end=" ")