本章目標(biāo)：

(1)了解和實(shí)現(xiàn)順序搜索和二分法搜索。

(2)了解和實(shí)現(xiàn)選擇排序、冒泡排序、歸并排序、快速排序、插入排序和希爾排序。

(3)了解用散列法實(shí)現(xiàn)搜索的技術(shù)。

(4)了解抽象數(shù)據(jù)類型：映射Map。

(5)采用散列實(shí)現(xiàn)抽象數(shù)據(jù)類型Map。

(6)搜索算法
1、二分搜索

def binary_search(ls, item):
  '''

  :param ls:  有序列表
  :param item: 查詢的元素
  :return:返回查詢?cè)卦谟行蛄斜碇械乃饕?  '''  
  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循環(huán)，外層循環(huán)對(duì)內(nèi)層循環(huán)

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]

快速排序：
快速排序指的是使用一個(gè)分割值，將列表劃分為小于分割值，等于分割值，大于分割值三部分，然后對(duì)每一部分遞歸的使用同樣的方法進(jìn)行快排，然后將三部分拼接，就可以得到排序的列表。

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)