Python---算法-------归并排序，二分查找

归并排序：

归并排序将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

最优时间复杂度位：O(nlogn)

最坏时间复杂度位：O(nlogn)

稳定性：稳定

def merge_sort(alist): n = len(alist) if n <= 1: return alist mid = n // 2 # left，right 采用归并排序后形成的有序的新的列表 left_li = merge_sort(alist[:mid]) right_li = merge_sort(alist[mid:]) # 将两个有序的子序列合并为一个新的整体 # merge(left,right) left_pointer, right_pointer = 0, 0 result = [] while left_pointer < len(left_li) and right_pointer < len(right_li): if left_li[left_pointer] < right_li[right_pointer]: result.append(left_li[left_pointer]) left_pointer += 1 else: result.append(right_li[right_pointer]) right_pointer += 1 result += left_li[left_pointer:] result += right_li[right_pointer:] return result

二分查找：

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难

最优时间复杂度：O(1)

最坏时间复杂度：O(logn)

def binary_search(alist, item): first = 0 last = len(alist)-1 while first<=last: midpoint = (first + last)/2 if alist[midpoint] == item: return True elif item < alist[midpoint]: last = midpoint-1 else: first = midpoint+1 return False def binary_search(alist, item): n = len(alist) if n > 0: mid = n // 2 if alist[mid] == item: return True elif item < alist[mid]: return binary_search(alist[:mid]) else: return binary_search(alist[mid:]) return False