首页 » python » 正文

python 归并排序 动画演示

Merge-sort-example-300px

到了包含递归的排序了

代码参考:http://wuchong.me/blog/2014/02/09/algorithm-sort-summary/#comments

理解这段代码最核心的还是要绕明白递归的那个巡环,其实,举个例子就明白了,假如,我们要排序的是一个非常简单的数租

【2】

这个时候我们传递给merge_sort,这个时候len(arg)=1,直接返回了【2】

再假如我们还有一个另外一个数租

【1】,同理,也是直接返回【1】

但是,如果我们有一个数租【2,1】,我们传递给merge_sort之后,len(arg)=2,所以

left = merge_sort([2])

right = merge_sort([1])

在上面我们已经知道当数租是[1]或者【2】时候返回给我门的数值

也就是说left=[2],right=[1],这个数租是无序的,我们需要通过mere()来变成有序的,经过merge之后

我们得到的是【1,2】

假如,我们现在要比较的数组是:[4,2,1]

传递给merge_sort之后,我们得到的是

left=merge_sort([4])

right=merge_sort([2,1])

同样的,我们知道left=[4],right=[1,2]

但是,这个还是无序的,没有关系,调用merge就好了

……..

这就是递归

发表评论