首页 > 代码库 > Python归并排序(递归实现)
Python归并排序(递归实现)
为什么归并排序如此有用?
1. 快捷和稳定
归并排序成为?一个非常棒的排序算法主要是因为它的快捷和稳
定。它的复杂度即使在最差情况下都是O(n log n)。而快速排序
在最差情况下的复杂度是O(n^2),当n=20的时候,它比归并要
慢4.6倍。
2.容易实现
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #coding:utf-8 def merge_sort(array): length = len (array) if length < = 1 : return array m = length / 2 left = array[:m] right = array[m:] left = merge_sort(left) right = merge_sort(right) return merge(left,right) def merge(left,right): result = [] while len (left)> 0 and len (right)> 0 : if left[ 0 ] < = right[ 0 ]: result.append(left.pop( 0 )) else : result.append(right.pop( 0 )) result.extend(left) result.extend(right) return result if __name__ = = ‘__main__‘ : print merge_sort([ 33 , 11 , 2 , 3 , 7 , 2234234234234234 , 4 , 23 , 2 , 3 , 4 , 7 ]) print merge_sort([ 0 , 1 , 2 , 3 , 4 , 5 , 5 , 6 , 7 , 8 , 9 ]) print merge_sort([ 9 , 8 , 7 , 6 , 5 , 5 , 4 , 3 , 2 , 1 , 0 ]) |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。