python中归并排序

 1 # coding=UTF-8
 2 #!/usr/bin/python
 3
 4 import sys
 5
 6 def merge(nums, first, middle, last):
 7     "merge"
 8     #切片边界,左闭右开,从0开始
 9     lnums = nums[ first:middle+1 ]
10     rnums = nums[ middle+1:last+1 ]
11     lnums.append(sys.maxint)
12     rnums.append(sys.maxint)
13     l = 0
14     r = 0
15     for i in range( first, last+1 ):
16         if lnums[l] < rnums[r]:
17             nums[i] = lnums[l]
18             l+=1
19         else:
20             nums[i] = rnums[r]
21             r+=1
22
23 def merge_sort(nums, first, last):
24     """mergesort
25         mergesort函数中传递的是下标,不是元素的个数
26     """28     if first < last:
29         middle = (first + last)/2
30         #print "middle in loop", count, "is:", middle
32         merge_sort(nums, first, middle)
33         merge_sort(nums, middle+1, last)
34         merge(nums,first, middle, last)
35         #print "loops:",count,">>", nums
36
37
38
39 if __name__ == ‘__main__‘:
40     nums = [10, 8, 4, -1, 2, 6, 7, 3]
41     print "nums is ", nums
42     merge_sort(nums, 0, 7)
43     print "merge_sort", nums

/usr/bin/python2.7 /root/PycharmProjects/Sort/merge-sort.py
nums is  [10, 8, 4, -1, 2, 6, 7, 3]
merge_sort [-1, 2, 3, 4, 6, 7, 8, 10]

Process finished with exit code 0

时间: 12-23

python中归并排序的相关文章

python中的归并排序

本来在博客上看到用python写的归并排序的程序,然后自己跟着他写了一下,结果发现是错的,不得不自己操作.而自己对python不是很了解所以就变百度边写,终于在花了半个小时之后就写好了. def merge(a, first, end, temp): if first < end: mid = (first+end)//2 merge(a, first, mid, temp) #前半部分拍好序 merge(a, mid+1, end, temp) #后半部分拍好序 merger(a, first

python实现归并排序,归并排序的详细分析。

学习归并排序的过程是十分痛苦的.它并不常用,看起来时间复杂度好像是几种排序中最低的,比快排的时间复杂度还要低,但是它的执行速度不是最快的.很多朋友不理解时间复杂度低为什么运行速度不一定快,这个不清楚的伙伴可以看下我之前发表的文章http://www.cnblogs.com/Lin-Yi/p/7301535.html看完之后也许你会对时间复杂度有一个新的认识. 我谈的观点往往不是官方的定义,我希望能帮助更多基础薄弱的同学读懂思想~ 归并排序: 先分开再合并,分开成单个元素,合并的时候按照正确顺序合

Python中的序列

Python中有四种内建的数据结构,即列表.元组.字典.集合.其中字典和集合我会以后再写,现在先说列表和元组,它们两个和以前提到很多次的字符串, 其实都属于——序列. 一.列表(list): 1. list 是处理一组有序项目的数据结构,即你可以在一个列表中存储一个序列的项目. 列表中的项目应该包括在方括号中,这样Python 就知道你是在指明一个列表.一旦你创建了一个列表,你可以添加.删除或是搜索列表中的项目.由于你可以 增加或删除项目,我们说列表是可变的数据类型,即这种类型是可以被改变的.

python中的堆排序peapq模块

heapq模块实现了python中的堆排序,并提供了有关方法.让用Python实现排序算法有了简单快捷的方式. heapq的官方文档和源码:8.4.heapq-Heap queue algorithm 下面通过举例的方式说明heapq的应用方法 实现堆排序 #! /usr/bin/evn python #coding:utf-8 from heapq import * def heapsort(iterable): h = [] for value in iterable: heappush(h

python实现归并排序,归并排序的详细分析

学习归并排序的过程是十分痛苦的.它并不常用,看起来时间复杂度好像是几种排序中最低的,比快排的时间复杂度还要低,但是它的执行速度不是最快的.很多朋友不理解时间复杂度低为什么运行速度不一定快,这个不清楚的伙伴可以看下我之前发表的文章http://www.cnblogs.com/Lin-Yi/p/7301535.html看完之后也许你会对时间复杂度有一个新的认识. 我谈的观点往往不是官方的定义,我希望能帮助更多基础薄弱的同学读懂思想~ 归并排序: 先分开再合并,分开成单个元素,合并的时候按照正确顺序合

走入计算机的第四十天(python中sockserver模块)

一.Python中的sockserver模块 1.该模块与sock模块不同之处是该模块自动帮我们分装好了一些功能,让我们在编程的时候直接调用这些功能就可以了,节省了编程步骤. 2.如图所示 注释:上图为服务端设置 该模块的操作方法比较死板,我们只要会熟悉的使用他就可以了.

python中if __name__ == &#39;__main__&#39;:

Using a module's __name__ Example? 8.2.? Using a module's __name__ #!/usr/bin/python # Filename: using_name.py if __name__ == '__main__': print 'This program is being run by itself' else: print 'I am being imported from another module' Output $ pytho

关于Python中的yield

关于Python中的yield http://www.cnblogs.com/tqsummer/archive/2010/12/27/1917927.html http://www.ibm.com/developerworks/cn/opensource/os-cn-python-yield/ 一.迭代器(iterator) 在Python中,for循环可以用于Python中的任何类型,包括列表.元祖等等,实际上,for循环可用于任何“可迭代对象”,这其实就是迭代器 迭代器是一个实现了迭代器协议

python中的那些“神器”

"武林至尊,宝刀屠龙,号令天下,莫敢不从,倚天不出,谁与争锋",这是神器.不过今天要说的python中的"神器"就没有这么厉害了,这里要说的"神器"其实就是名称里面带了个"器"的,如下: 列表解析器 迭代器 生成器 装饰器 列表解析器 现在遇到了这样一个问题需要解决:"有一个数字的列表,要求对该列表中的奇数乘以2,返回处理完成后的列表(不改变原来列表的顺序,仅对列表中的奇数乘以2)",比较传统的方法可能会是