Python - 合并排序递归算法 [英] Python - Merge Sort Recursive Algorithm

问题描述

  **程序** * mergesort *（（）） L = a1，a2，...，an）
 ** if ** n> 1 **然后** 
m：=⌊n/2⌋
 L1：= a1，a2，...，am 
 L2：= am + 1，am + 2，... $ an b $ b L：= merge（mergesort（L1），mergesort（L2））
 {L现在按递增顺序排序为元素} 
 
 **过程** *合并*（ L1，L2：排序列表）
 L：=空列表
 **，而** L1和L2都是非空的
从列表中删除L1和L2中较小的第一个元素; 
放在L 
 **的右端如果**这个移除使得一个列表变空
 **然后**从另一个列表中移除所有元素并将它们附加到L 
返回L {L是具有递增顺序元素的合并列表} 
  

其目的是为了写它在python上，到目前为止我编写了所有它，但它不能正常运行，每当我运行它打印：函数合并在0x0000000002024730。这里是python代码：

  #Recursive Merge Sort 
 import math 
 ent = [10000，967 （L 1，L 2）：
 
，而len（L 1）和len（L 2）！= 0 ：
 L.append（L1 [0]）
 L1.remove（L1 [0]）
 L.append（L2 [0]）
 L2.remove（L2 [ 0）
 if len（L1）== 0：
 L.append（L2）
 elif len（L2）== 0：
 L.append（L1）
返回L 
 
 
 def mergesort（ent）：
 
如果len（ent）> 1：
m = math.floor（len （ent）/ 2）
 L1 = [] 
 L2 = [] 
 L1 = L1 + ent [：m] 
 L2 = L2 + ent [m + 1：len （ent）] 
 L =合并（mergesort（L1），mergesort（L2））
 
 
 
 
打印（合并）
  

我对函数是如何递归地一起工作有些怀疑，这就是为什么我认为我无法解决和编码对的。任何帮助或建议？

解决方案

您没有执行 merge ，但打印本身的功能。这样做：

  print（merge（））
  

然而，你的逻辑有点混乱，你甚至没有递归函数。

取一个看看这个问题

另外，我想什么你需要调用mergesort：

  def mergesort（ent）：
 if len（ent）> 1： 
m = math.floor（len（ent）/ 2）
 L1 = ent [：m] 
 L2 = ent [m + 1：len（ent）] 
 L =合并（mergesort（L1），mergesort（L2））
 return L 
  

然后执行它：

  print（mergesort（ent））
  

I was trying to implement this pseudocode for the recursive merge sort algorithm:

**procedure**  *mergesort*(L = a1, a2,…,an )
**if**  n  > 1 **then** 
     m := ⌊n/2⌋
     L1 := a1, a2,…,am 
     L2 := am+1, am+2,…,an
     L   := merge(mergesort(L1), mergesort(L2 ))
{L is now sorted into elements in increasing order}

**procedure**  *merge*(L1, L2 :sorted lists)
L := empty list
**while** L1  and L2  are both nonempty
 remove smaller of first elements of L1 and L2 from its list; 
         put at the right end of L
 **if** this removal makes one list empty 
     **then** remove all elements from the other list and append them to L
return L {L is the merged list with the elements in increasing order}

The purpose its to write it on python, so far I have coded all of it but it does not run properly, everytime I run it prints: function merge at 0x0000000002024730. Here is the python code:

#Recursive Merge Sort
import math
ent = [10000, 967, 87, 91, 117, 819, 403, 597, 1201, 12090]
def merge(L1, L2):

        while len(L1) and len(L2) != 0:
            L.append(L1[0])
            L1.remove(L1[0])
            L.append(L2[0])
            L2.remove(L2[0])
            if len(L1) == 0:
                L.append(L2)
            elif len(L2) == 0:
                L.append(L1)
        return L


def mergesort(ent):

if len(ent)>1:
    m=math.floor(len(ent)/2)
    L1 = []
    L2 = []
    L1=L1+ent[:m]
    L2=L2+ent[m+1:len(ent)]
    L=merge(mergesort(L1),mergesort(L2))




print(merge)

I have some doubts about how the functions are supossed to work recursively together, which is why I think I cant solve and code it right. Any help or suggestions?

解决方案

You're not executing merge, but printing the function itself. Do this:

print(merge())

However, your logic is a bit messed up, you don't even have a recursive function there.

Take a look at this question

Also, i think what you need is to call mergesort:

def mergesort(ent):
    if len(ent)>1:
        m=math.floor(len(ent)/2)
        L1 = ent[:m]
        L2 = ent[m+1:len(ent)]
        L=merge(mergesort(L1),mergesort(L2))
return L

And execute it:

print(mergesort(ent))

这篇关于Python - 合并排序递归算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！