Python数据结构 第五章--排序和搜索

本章目标：

(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)