在Python中合并排序给定的列表

Question

问题:在python中实现合并排序。不要使用Python构建的排序或排序。假设您的输入足以满足您所拥有的内存。

我应该如何使这个代码更好呢？

def merge_sort(list_sort):
    """splits the list in two parts until each part is left with one member"""

    if len(list_sort) ==  1:
        return list_sort

    if len(list_sort)>= 2:
        x= len(list_sort) / 2
        part_a = list_sort[:x]
        part_b = list_sort[x:]
        sorted_part_a = merge_sort(part_a)
        sorted_part_b = merge_sort(part_b)
        return merge(sorted_part_a, sorted_part_b)

def merge(left , right):
    """merges the two parts of list after sorting them"""
    sorted_list = []
    i = 0
    while left[:] and right[:] :
        if  left [i] > right [i]:
            sorted_list.append(right[i])
            right.remove(right[i])

        else :
            sorted_list.append(left[i])
            left.remove(left[i])

    if left[:]:
            sorted_list.extend(left[:])
    elif right[:] :
            sorted_list.extend(right[:])
    return sorted_list

details = [1, 127, 56, 2, 1, 5, 7, 9, 11, 65, 12, 24, 76, 87, 123, 65, 8,32, 86, 123, 67, 1, 67, 92, 72, 39, 49, 12, 98, 52, 45, 19, 37, 22, 1, 66, 943, 415, 21, 785, 12, 698, 26, 36, 18, 97, 0, 63, 25, 85, 24, 94, 150 ]
print "List to be sorted  = ", details
print "Sorted List = ", merge_sort(details)

Answer 1

您的代码中有一些巨大的低效。

每次您正确使用left[:]或right[:]时，它都会复制列表！您在merge()中做了几次，不必要的。

i = 0是一个毫无意义的变量，正如您使用它的方式:它只是一种模糊的方式来表示0。此外，right.remove(right[i])和left.remove(left[i])只是right.pop(0)和left.pop(0)，但更冗长、效率更低。最后，对于列表中的任何内容，.remove()或.pop()都是非常低效的，因为它需要复制后续的每个元素来填补空白。

因此，您应该做的是以非破坏性的方式遍历left和right列表，使用两个变量i和j来跟踪您所做的工作。

Answer 2

排序算法

• 而不是if len(list_sort)>= 2:，只需使用else:
• 我会把中间的所有步骤都处理掉。
• list_sort听起来太像merge_sort，一种方法，而不是变量
• 若要防止在Python3中使用此算法时出现意外，请使用//进行楼层划分。
• 您可以使用事实1 // 2计算结果为False布尔运算。

所以它最终会像：

def merge_sort_list(lost_list):
    """splits the list in two parts until each part is left with one member"""
    x = len(lost_list) // 2
    if not x: # length is 1
        return lost_list
    else:
        return merge(merge_sort(lost_list[:x]), merge_sort(lost_list[x:]))

合并算法

为了以后的重用，我将使用一个使用generators的更通用的算法，它不会改变传递给它的项。这也将有助于更容易地对其他容器调整排序算法。

def merge(left, right):
    try:
        left = iter(left)
        right = iter(right)
        l = next(left)
        r = next(right)
    except StopIteration as exc:
        raise ValueError('left and right should be iterables with at least length 1', exc)
    try:
        while True:
            if l <= r:
                yield l
                l = None
                l = next(left)
            else:           
                yield r
                r = next(right)
    except StopIteration:
        yield r if l is None else l  # l is None if left is exhausted
        yield from left
        yield from right
        return

感谢PeylonRayz注意到了这个bug

替代版

def merge(left, right):
    try:
        left = iter(left)
        right = iter(right)
        iterators = (
            (next(left), 'left', left), 
            (next(right), 'right', right),
        )
    except StopIteration as exc:
        raise ValueError('left and right should be iterables with at least length 1', exc)
    try:
        while True:
            (value, key, iterator), other = min(iterators), max(iterators)
            yield value
            iterators = other, (next(iterator), key, iterator)
    except StopIteration:
        value, key, iterator = other
        yield value
        yield from iterator

我发现这个替代的版本稍微优雅一些，如果是ex aequo的话，它在右前保持左。它可以很容易地适应以支持降序合并。

排序分词

def merge_sort_dict_keys(items):
    import collections
    sorted_keys = merge_sort_list(list(items.items()))
    return collections.OrderedDict((key, value) for key, value in sorted_keys)

def merge_sort_dict_values(items):
    import collections
    sorted_keys = merge_sort_list(list((value, key) for key, value in items.items()))
    return collections.OrderedDict((key, value) for value, key in sorted_keys)