归并排序

1. 原理
   分治法：先递归分解数组，再合并数组。基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
2. 实现

• 稳定排序

def merge_sort(alist):

	#拆分
	if n <= 1:
		return alist
	n = len(alist)
	mid = n//2
	
	#左边列表形成新的列表
	left_li = merge_sort(alist[:mid])
	#右边列表形成新的列表
	right_li = merge_sort(alist[mid:])
	
	# 将两个有序的数列合并
	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_point])
			left_pointer += 1
		else:
			result.append(right_li[right_point])
			right_pointer += 1
	
	#左边走到头和右边走到头的处理		
	result += left_li[left_pointer]
	result += right_li[right_pointer]
	
	return result

搜索

搜索是在一个项目集合中找到一个特定项目的算法过程。搜索的几种常见方法：顺序查找、二分法查找、二叉树查找、哈希查找。

二分查找

1. 原理
   二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。
   ![[Binary_search_into_array.png]]
2. 实现
   （1）递归

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],item)
		else:
			return binary_search(alist[mid+1:],item)
	return False

(2) 非递归

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