Python 归并排序

Question

我正在尝试实现 Python 合并排序，但我在某些方面失败了。我拥有的伪代码是准确的，但看起来它是为另一种语言构建的。

伪需要以下内容
/声明输入数组a大小的数组临时值

我不确定这在 Python 中如何实现。无论如何，代码如下。整个想法是我需要对数组/列表进行排序并返回排序后的数组。

截至目前，它失败并显示以下消息。我会说这是因为新的临时数组/列表，但我不确定

Traceback (most recent call last):  
  File "./mergesort", line 56, in <module>  
    main()  
  File "./mergesort", line 52, in main  
    mergesortbase(array)  
  File "./mergesort", line 4, in mergesortbase  
    mergesort(num, 0, len(num)-1)  
  File "./mergesort", line 10, in mergesort  
    mergesort(num, low, mid)  
  File "./mergesort", line 10, in mergesort  
    mergesort(num, low, mid)  
  File "./mergesort", line 12, in mergesort  
    merge(num, low, mid, mid+1, high)  
  File "./mergesort", line 27, in merge  
    temp[k] = a[j]  
IndexError: list assignment index out of range  

注意:完全修改代码没有帮助，因为我需要使用完全相同的伪代码。

#!/usr/bin/python3.6

def mergesortbase(num):
    mergesort(num, 0, len(num)-1)


def mergesort(num, low, high):
    if low < high:
      mid = (low + high) // 2
      mergesort(num, low, mid)
      mergesort(num, mid+1, high)
      merge(num, low, mid, mid+1, high)

def merge(a, l1, u1, l2, u2):
# declare array temp of size of input array a
# Comment -- Not doable in Python to create array/list with specific size
    temp = []
    i = l1
    j = l2
    k = l1

    while (i <= u1 and j <= u2):
      if (a[i] <= a[j]):
         temp[k] = a[i]
         i = i + 1
      else:
         temp[k] = a[j]
         j = j + 1

      k = k + 1

    while ( i <= u2 ):
       temp[k] = a[i]
       k = k + 1
       i = i + 1

    while ( j <= u2 ):
       temp[k] = a[j]
       k = k + 1
       i = i + 1

    h = l1

    while ( h <= u2 ):
       a[h] = temp[h]
       h = h + 1


def main():
   array = [8, 5, 7, 1, 9, 3]
   mergesortbase(array)


if __name__ == "__main__":
  main()

Answer 1

我很好奇您为什么不直接使用 Python 的内置排序功能，根据您的需要使用 sort 或 sorted。它可能比您自己滚动的东西更有效(除非您在数据集上使用特定的额外信息，这里似乎不是这种情况)。 可能您这样做是出于教育目的，在这种情况下，请随意忽略此段落，但如果您的意图只是对一些数据进行排序。

无论如何，您的具体问题似乎是如何“声明输入数组 a 大小的数组临时值”。

这很容易用语句完成:

temp = [0] * len(a)

下面的记录显示了这一点:

>>> a = [1,2,3]
>>> temp = [0] * len(a)
>>> temp
[0, 0, 0]

---

你现在拥有的是:

temp = []

它创建一个大小为零的列表，然后是:

temp[k] = a[i]

这总是会导致问题，因为没有 k 的值可以工作。

---

最重要的是，您的实际合并存在缺陷，因为您使用了不正确的变量来处理数组。您已经非常合乎逻辑地将某些项目联系在一起，例如 i 与第一个数组部分，以及 j 与第二个部分，但稍后您违反了:

while ( i <= u2 ):  # i and u1 should be associated: while i <= u1:
   temp[k] = a[i]   # (no need for '()' in Python conditions by the way).
   k = k + 1
   i = i + 1

while ( j <= u2 ):
   temp[k] = a[j]
   k = k + 1
   i = i + 1        # j and u2 should be associated: j = j + 1

即使您修复了数组创建，上面的第二个循环也可能会导致问题。它将永远运行(或直到异常，以先到者为准)，因为您正在检查 j 但永远不会更改它。但是，上面的两项都是不正确的，所以应该修正。

一旦我将数组设置为正确的大小，进行这两项更改，并在排序前后打印出数组，它看起来会好一些:

[8, 5, 7, 1, 9, 3]
[1, 3, 5, 7, 8, 9]