python递归排序组合,Python - 合并排序递归算法

待我称王封你为后i 2023-10-03 11:23 42阅读 0赞

![Image 1][]

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))

[Image 1]:

发表评论

表情：
评论列表 （有 0 条评论，42人围观）

还没有评论，来说两句吧...

相关阅读