Блог

Я написал программу, которая должна выполнять рекурсивную сортировку слиянием, сначала я создал fusion метод для объединения двух списков с использованием индексов

Вот fusion метод

 def Fusion (L,d,f,m):
  aux=[]
  i_d=d
  i_m=m
  while (i_d<=m-1 and i_m<=f-1):
    if(L[i_d]<=L[i_m]):
        aux.append(L[i_d])
        i_d =1
    else:
        aux.append(L[i_m])
        i_m =1
  while (i_d<=m-1):
    aux.append(L[i_d])
    i_d =1
  while (i_m<=f-1):
    aux.append(L[i_m])
    i_m =1
  for j in range(len(aux)):
    L[j]=aux[j]
 

Этот метод работает корректно, я протестировал его с двумя отсортированными списками.

merge Метод здесь

  def sort_fusion(T,a,b):
  if (a<b):
    m=(a b)//2
    sort_fusion(T,a,m) 
    sort_fusion(T,m 1,b)
    Fusion(T,a,b,m)  
 

Для запуска программы

 k1 =[3,1,0,9,1,2,6,8,5,7]
a=0
b=len(k1)
sort_fusion(k1,a,b)
 

Программа выдает это [2, 5, 6, 6, 7, 8, 1, 8, 5, 7] в качестве вывода, предоставляя этот ввод [3, 1, 0, 9, 1, 2, 6, 8, 5, 7]

Я не могу понять поведение программы, когда я комментирую sort_fusion(T,m 1,b) инструкцию, она выдает мне это [0, 1, 2, 3, 6, 8, 5, 7, 9, 1] в качестве вывода, для меня алгоритм просто прекрасен, когда я слежу за его ходом.

Кто-нибудь может указать на проблему.

 L[j]=aux[j]
 

Здесь вам, вероятно, нужно

 L[j   d] = aux[j]
 

Причина в том, что вы принимаете значения из L, которые начинаются с индекса d . Когда вы записываете вспомогательный массив обратно в L, вы хотите записать числа в то же место.