本章目标：
(1)了解和实现顺序搜索和二分法搜索。
(2)了解和实现选择排序、冒泡排序、归并排序、快速排序、插入排序和希尔排序。
(3)了解用散列法实现搜索的技术。
(4)了解抽象数据类型：映射Map。
(5)采用散列实现抽象数据类型Map。
(6)搜索算法
1、二分搜索
def binary_search(ls, item):
'''
:param ls: 有序列表
:param item: 查询的元素
:return:返回查询元素在有序列表中的索引
'''
start = 0
end = len(ls) - 1
mid = (start + end)
while start <= end:
mid = (start + end) / 2
if ls[mid] == item:
return mid
elif ls[mid] > item:
end = mid - 1
elif ls[mid] < item:
start = mid + 1
return -1
ls = [1, 3, 4, 5, 6, 7, 8, 9]
print binary_search(ls, 5)
# 3
(7)排序算法
冒泡排序：
两层for循环，外层循环对内层循环
def bubble_sort(ls):
for i in range(len(ls) - 1):
for j in range(len(ls)-1-i):
if ls[j] > ls[j + 1]:
ls[j], ls[j + 1] = ls[j + 1], ls[j]
return ls
print bubble_sort([1, 3, 2, 4, 5, 2, 1])
# [1, 1, 2, 2, 3, 4, 5]
快速排序：
快速排序指的是使用一个分割值，将列表划分为小于分割值，等于分割值，大于分割值三部分，然后对每一部分递归的使用同样的方法进行快排，然后将三部分拼接，就可以得到排序的列表。
def quick_sort(ls):
if not ls:
return []
else:
left = [item for item in ls if item<ls[0]]
right = [item for item in ls if item>ls[0]]
mid = [item for item in ls if item==ls[0]]
return quick_sort(left) + mid + quick_sort(right)
