对合并排序傻瓜说明 [英] Explanation of Merge Sort for Dummies

问题描述

我发现这个code在线：

I found this code online:

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

def mergesort(list):
    if len(list) < 2:
        return list
    middle = len(list) / 2
    left = mergesort(list[:middle])
    right = mergesort(list[middle:])
    return merge(left, right)

它的工作原理100％，当我运行它。我真的不明白如何合并排序工作以及如何递归函数是能够正确订购了左和右。

It works 100% when I run it. I just do not really get how the merge sort works or how the recursive function is able to properly order both a left and a right.

推荐答案

我认为，理解的关键归并排序是了解以下原则 - 我称之为合并原则：

I believe that the key to understanding merge sort is understanding the following principle -- I'll call it the merge principle:

给定两个单独的列表A和B至少责令最大，构造一个列表下通过反复比较，A的最小值到B的最低值，除去较小的值，并将其附加到C.当一个列表疲惫，附加于其他列表中的其余项目到下在顺序。列表C是那么也是一个排序的列表。

Given two separate lists A and B ordered from least to greatest, construct a list C by repeatedly comparing the least value of A to the least value of B, removing the lesser value, and appending it onto C. When one list is exhausted, append the remaining items in the other list onto C in order. The list C is then also a sorted list.

如果你的工作了这一点，用手几次，你会发现它是正确的。例如：

If you work this out by hand a few times, you'll see that it's correct. For example:

A = 1, 3
B = 2, 4
C = 
min(min(A), min(B)) = 1

A = 3
B = 2, 4
C = 1
min(min(A), min(B)) = 2

A = 3
B = 4
C = 1, 2
min(min(A), min(B)) = 3

A = 
B = 4
C = 1, 2, 3

现在A被用尽，因此延长下与其余的值从B：

Now A is exhausted, so extend C with the remaining values from B:

C = 1, 2, 3, 4

合并原则，也很容易证明的。 A的最小值小于A的所有其他值，和B的最小值小于B的所有其他值如果A的最低值小于B的最小值，那么它也必须小比B的全部的值。因此它小于A和所有值B的所有值。

The merge principle is also easy to prove. The minimum value of A is less than all other values of A, and the minimum value of B is less than all other values of B. If the minimum value of A is less than the minimum value of B, then it must also be less than all values of B. Therefore it is less than all values of A and all values of B.

所以，只要你不断追加，以满足这些标准，以C的值，你就会得到一个排序的列表。这就是合并功能上面做。

So as long as you keep appending the value that meets those criteria to C, you get a sorted list. This is what the merge function above does.

现在，鉴于这一原则，这是很容易理解的一个分拣技术，通过将其分割成更小的列表，整理这些名单，然后将这些排序的列表合并在一起进行排序列表。该 merge_sort 函数只是一个函数，把一半的列表，排序这两个列表，然后合并这两个列表一起在上述方式。

Now, given this principle, it's very easy to understand a sorting technique that sorts a list by dividing it up into smaller lists, sorting those lists, and then merging those sorted lists together. The merge_sort function is simply a function that divides a list in half, sorts those two lists, and then merges those two lists together in the manner described above.

，唯一的缺点是，因为它是递归的，当它排序两个子表，它是通过他们传递给自己！如果你遇到困难的递归这里了解，我建议先学习简单的问题。但是如果你递归的基础知识已经，那么你必须认识到的是，一个项目列表已经排序。合并两个一项目列表生成一个排序的两个项目清单;合并两个两项目列表生成一个有序的四项目清单;等等。

The only catch is that because it is recursive, when it sorts the two sub-lists, it does so by passing them to itself! If you're having difficulty understanding the recursion here, I would suggest studying simpler problems first. But if you get the basics of recursion already, then all you have to realize is that a one-item list is already sorted. Merging two one-item lists generates a sorted two-item list; merging two two-item lists generates a sorted four-item list; and so on.

这篇关于对合并排序傻瓜说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！