欢迎访问我的博客：http://wangnan.tech
第一章 算法介绍
二分查找Python代码
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)
示例代码
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等）。
