Table of Contents

  1. 第一章 算法介绍
    1. 二分查找Python代码
    2. 小结
  2. 第二章 选择排序
    1. 小结

第一章 算法介绍

二分查找Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def binary_search(list,item):
low = 0
high = len(list-1)
while low <= high:
mid =(low+high)
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid -1
else:
low = mid + 1
return None

小结

  • 二分查找的速度比简单查找快得多
  • O(log n)比O(n)快,需要搜索的元素越多,前者比后者就快得越多
  • 算法运行时间并不是以秒为单位
  • 算法运行时间是从其增速的角度度量的
  • 算法运行时间用大O表示法表示

第二章 选择排序

  • 很多算法仅在数据经过排序后才管用.选择排序是下一章介绍的快速排序的基石
  • 数组和链表操作运行时间
# 数组 链表
读取 o(1) o(n)
输入 o(n) o(1)
删除 o(n) o(1)
  • 需要随机读取元素时,数组效率高,当需要中间插入元素时,链表是更好的选择,链表只能随机访问

  • 选择排序,需要的总时间是O(nxn)

  • 示例代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1,len(arr)):
    if arr[i] < smallest;
    smallest = arr[i]
    smallest_index = i
    return smallest_index
    def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
    smallest = findSmallest(arr)
    newArr.append(arr.pop(smallest))
    return newArr

小结

  • 计算机内存犹如一大堆抽屉。
  • 需要存储多个元素时,可使用数组或链表。
  • 数组的元素都在一起。
  • 链表的元素是分开的,其中每个元素都存储了下一个元素的地址。
  • 数组的读取速度很快。
  • 链表的插入和删除速度很快。
  • 在同一个数组中,所有元素的类型都必须相同(都为int、double等)。