合并排序不适用于大于10^7个元素的数组

Question

我的算法适用于最多10^6个元素的数组，尽管它的效率不如它的工作。我希望它排序的数组是随机生成的。我从一个文件中读取数组的元素数量和最大值，然后创建列表。

def mergeSort(listaNumere):
n = len(listaNumere)
if n == 1:
return listaNumere
mij = n//2
stanga = []
for i in range (0, mij):
stanga.append(listaNumere[i])
dreapta = []
for i in range(mij, n):
dreapta.append(listaNumere[i])
#stanga = listaNumere[:mij]
#dreapta = listaNumere[mij:]
stanga = mergeSort(stanga)
dreapta = mergeSort(dreapta)
return merge(stanga, dreapta)
def merge(stanga, dreapta):
aux = []
while len(stanga) != 0 and len(dreapta) != 0:
if stanga[0] < dreapta[0]:
aux.append(stanga[0])
del stanga[0]
else:
aux.append(dreapta[0])
del dreapta[0]
while len(stanga) != 0:
aux.append(stanga[0])
del stanga[0]
while len(dreapta) != 0:
aux.append(dreapta[0])
del dreapta[0]
return aux

该程序已在后台运行了30分钟，尚未完成对数组的排序。

我怎样才能使程序更有效率，这样它就不会花那么多时间运行？

尝试过这个：

def merge(stanga, dreapta):
aux = []
i,j = 0,0
while i < len(stanga) and j < len(dreapta):
if stanga[i] < dreapta[j]:
aux.append(stanga[i])
i += 1
else:
aux.append(dreapta[j])
j += 1
while i < len(stanga):
aux.append(stanga[i])
i += 1
while j < len(dreapta):
aux.append(dreapta[i])
i += 1
return aux

Answer 1

Delete操作具有O(N(复杂性，这将不可避免地使程序执行非常缓慢
去掉所有del dreapta[0]和del stanga[0]语句，并使用两个指针重构合并逻辑。

def merge(stanga, dreapta):
aux = []
i,j = 0,0
while i < len(stanga) and j < len(dreapta):
if stanga[i] < dreapta[j]:
...

Answer 2

制作数组的一次性副本。使用递归级别替换合并方向，以避免过度复制数据。此示例代码对10^7个整数进行排序需要1分钟以上的时间。这是Python速度较慢的情况。C|C++中的相同代码的速度要快50多倍。

def sort(a):
if(len(a) < 2):                     # if nothing to do, return
return
b = a[:]                            # b = copy of a
sortr(b, a, 0, len(a))              # merge sort
def sortr(b, a, beg, end):              # merge sort
if((end - beg) < 2):                # if < 2 elements
return                          #   return
mid = (beg+end)//2                  # set mid point
sortr(a, b, beg, mid)               # merge sort left  half to b
sortr(a, b, mid, end)               # merge sort right half to b
mrg(b, a, beg, mid, end)            # merge halves   from b to a
def mrg(a, b, ll, rr, ee):              # merge a pair of runs from a to b
o = ll                              # o = b[]        index
l = ll                              # l = a[] left   index
r = rr                              # r = a[] right  index
while True:
if(a[l] <= a[r]):               # if a[l] <= a[r]
b[o] = a[l]                 #   copy a[l]
o += 1
l += 1
if(l < rr):                 #   if not end of left run
continue                #     continue (back to while)
b[o:ee] = a[r:ee]           #   else copy rest of right run
return                      #     and return
else:                           # else a[l] > a[r]
b[o] = a[r]                 #   copy a[r]
o += 1
r += 1
if(r < ee):                 #   if not end of right run
continue                #     continue (back to while)
b[o:ee] = a[l:rr]           #   else copy rest of left run
return                      #     and return

Answer 3

使用append和del效率低下，因为需要重新分配和/或移动中间数组。相反，您应该将中间数组分配到适当的大小，并将元素存储在适当的索引中：

def mergeSort(listaNumere):
n = len(listaNumere)
if n < 2:
return listaNumere
mij = n // 2
stanga = listaNumere[:mij]
dreapta = listaNumere[mij:]
stanga = mergeSort(stanga)
dreapta = mergeSort(dreapta)
return merge(stanga, dreapta)
def merge(stanga, dreapta):
slen = len(stanga)
dlen = len(dreapta)
aux = [0] * (slen * dlen)
i = 0
j = 0
k = 0
while i < slen and j < dlen:
if stanga[i] <= dreapta[j]:
aux[k] = stanga[i]
i += 1
k += 1
else:
aux[k] = dreapta[j]
j += 1
k += 1
if i < slen:
aux[k:] = stanga[i:]
else
aux[k:] = dreapta[j:]
return aux