[building block] merge sort @ Python,mergepython,Here is th
[building block] merge sort @ Python,mergepython,Here is th
Here is the basic algorithm about merge sort:
def merge(s1,s2,s): i=j=0 while i + j < len(s): if j == len(s2) or (i < len(s1) and s1[i] < s2[j]): s[i + j] = s1[i] i += 1 else: s[i + j] = s2[j] j += 1 def merge_sort(s): """ Sort the elements of python list s using merge-sort algorithm""" # Time compelxity: O(nlogn), where n = len(s) n = len(s) if n < 2: return # Divide mid = n // 2 s1 = s[:mid] s2 = s[mid:] #conquer (with recursion) merge_sort(s1) merge_sort(s2) # merge results merge(s1,s2,s)
insertion sort: time complexity: O(n^2)
def insertion_sort(A): ”””Sort list of comparable elements into nondecreasing order.””” for k in range(1, len(A)): # from 1 to n-1 cur = A[k] # current element to be inserted j = k # find correct index j for current while j > 0 and A[j-1] > cur: # element A[j-1] must be after current A[j] = A[j-1] j -= 1 A[j] = cur # cur is now in the right place
[building block] merge sort @ Python
相关内容
- 安装完Pydev却无法创建Python工程,,为了方便以后工作,
- Debian 7 安装 Python3.4,debianpython3.4,Debian 7 自
- python实现列表中各元素的拼接,python拼接,功能要求:
- Python初学者第九天 字符串、列表、字典练习,python第九
- Python—MySQL线程池,,python实现版本
- #MySQL for Python(MySQLdb) Note,,#MySQL for
- 分享《Python深度学习》高清中文版pdf+高清英文版pdf+源
- Python之random模块(随机数模块),,random.ran
- python ---求100以内的质数有哪些,,#coding=ut
- 运维学python之爬虫中级篇(六)基础爬虫,,通过这么多
评论关闭