合并排序 return 不再有序

Mergesort return no longer in order

我不是初学者 python 编码员，但我也不是高级编码员。如果您能看一下我正在描述的内容，问题将更容易解释。这是我在其中看到问题的代码：

import operator

def mergeSort(L, compare = operator.lt):
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L)/2)
        left = mergeSort(L[:middle], compare)
        right = mergeSort(L[middle:], compare)
        return merge(left, right, compare)

def merge(left, right, compare):
    result = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while (i < len(left)):
        result.append(left[i])
        i += 1
    while (j < len(right)):
        result.append(right[j])
        j += 1
    return result

合并功能有效。最终的 return 结果总是有序的。问题是，如果你从最终的 return 结果向前迈出一步，returning 到 mergesort 中的 return merge(left, right, compare)，return ed 列表 L 不再按顺序排列，然后将这个排序错误的列表 returned 到调用 mergesort 的函数。我什至不明白为什么会这样。从 return 结果到 return 合并（左、右、比较）的 return 行程会发生什么？ returned 列表不是随机列表，它看起来像一个部分排序的列表，但它在最终 return 结果时完全排序，而这个结果不是 return编辑到合并排序。

我以前使用过这种合并排序，没有任何问题，所以问题可能出在我正在排序的数据中。 L 是一个列表的列表，每个列表元素都是一个字符串列表，长度都相同，要导出到 csv 并最终导出到 Excel。我的数据是 table，第一列是网站标题，第二列是 urls，我正在对它们进行排序以识别重复项。完整的 table 中还有其他几个字段，但我只在标题和 url 列中看到了这个问题，这是我简化的内容，因此我可以尝试查看出了什么问题。我不确定 mergesort 是否可以处理此数据结构，但 merge 的最终 return 结果肯定表明它可以。但是在最后 return.

中发生了一些神秘的事情

合并的结果似乎没有被保存。这是一个修复：

def mergeSort(L, compare = operator.lt):
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L)/2)
        left = mergeSort(L[:middle], compare)
        right = mergeSort(L[middle:], compare)
        L[:] = merge(left, right, compare)
    return L

关于这个问题我最后写了the python.org list，第一个回复一针见血：

2016 年 12 月 22 日星期四上午 11:55，Deborah Swanson 写道：

The problem is that while mergeSort puts the list ls in perfect order, which I can see by looking at result on merge's final return to mergeSort, and at the left and the right once back in mergeSort. Both the left half and the right half are in order. But the list L is still in its original order, and after mergeSort completes, ls is still in its original order. Maybe there's some bonehead error causing this, but I just can't see it.

你的分析很棒。下面是发生的事情：当你合并排序时，你总是返回一个新列表（"return L[:]" 或 "result = []"），但是你这样称呼它：

# sort: Description only, to make hyperelinks & find duplicates
mergeSort(ls)

这会调用 mergeSort，然后将新排序的列表放在地板上。相反，请尝试："ls = mergeSort(ls)".

感谢您让我们如此轻松！

克里斯

因此，可以使用合并排序对列表的列表进行排序，这是我直到现在才确定的。

合并排序 return 不再有序

Mergesort return no longer in order

python

mergesort

function