[building block] merge sort @ Python
浏览数：36 /
时间：2015年06月08日
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
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
