营销型网站建设培训/百度指数app下载

第一章  认识算法

广义的算法：指做一件事情 / 解决一个问题的方法。

狭义的算法：数据结构+控制流程。（实现算法就先确定数据结构，再明确控制流程，最后实现算法）

掌握算法的5个层次：

• 1、听说：知道有这么个算法
• 2、了解：知道算法的原理，用自然语言描述
• 3、理解：知道算法的细节，数据结构和控制流程，时空复杂度
• 4、实现：用编程语言实现
• 5、应用：举一反三

算法的难点在于：从概括性的原理转换为具体数据结构，一步步实现对应的控制流程。

对于每个算法：我们要讲抽象原理，再将其拆解成数据结构和控制流程，详细推演整个运行过程的细节，将细节写成代码。

第二章  控制流程

顺序、条件、循环等几种控制流程

第三章  计算机是如何运行的

数据的基本概念、计算机的前世今生

第四章  万物的抽象：数据结构

数组、链表的基本概念

第五章  复杂一些的数据结构：图和树

图和树的基本概念

二叉树的深度优先遍历算法：

先序遍历、中序遍历、后序遍历实际上是先根序遍历、中根序遍历、后根序遍历。--- 主体：根节点

• 先序遍历：先访问根节点
• 中序遍历：中间访问根节点
• 后序遍历：最后访问根节点

要求：

• 把树拆成左子树、根、右子树三部分。
• 将左子树、右子树分别作为两棵树，将他们分别按上一步拆分。
• 直到一颗子树只有一个节点为止。

第六章  第一行python代码

python语言基本介绍

第七章  开始用python语言编写程序

python基本数据结构

第八章  实现一个算法衡量其优劣

查找算法的要素：待查集合、目标数。

第一个算法：顺序查找，无序查找，待查集合未排序。

算法原理：从前往后依次查找。

代码实现

while

tn = 95  # 目标数
arr = [1, 5, 8, 19, 3, 2, 14, 6, 8, 22, 44, 95, 78]  # 待查集合
i = 0  # 从头开始查找
while i < len(arr):if arr[i] == tn:print("success:", i)breakelse:i = i + 1
if i == len(arr):  # 循环退出条件print("failed")

for

tn = 95  # 目标数
arr = [1, 5, 8, 19, 3, 2, 14, 6, 8, 22, 44, 95, 78]  # 待查集合
for i in range(0, len(arr)):if arr[i] == tn:print("success:", i)break
if i == len(arr):  # 循环退出条件print("failed")

时间复杂度：

运算速度的表达，标记为大O

空间复杂度：

占据存储空间的大小，标记为大O

第九章  简单但有用的经典查找算法

从1~1000内任意选择一个数做为神秘数字，猜中结束

1、不限次数，可以从前往后找。

tn = 165
found = False
for i in range(1, 1001):if i == tn:print("success:", i)found = Truebreak
if not found:print("failed")

2、限制次数就要跳跃找。

首先要确定跳的方向，其次要确定跳的距离。确定这个思路后，二分查找就是一个不错的想法。

二分查找：

从有序序列中查找特定元素。

arr = [3, 5, 7, 9, 12, 15, 18, 32, 66, 78, 84, 103, 209]  # 待查序列
tn = 5  # 目标数low = 0
high = len(arr) - 1  # 区域起始范围while low <= high:  # 待查区域存在m = int((high - low) / 2) + low  # 当前区域中间位置if arr[m] == tn:print("success:", m)else:if arr[m] < tn:low = m + 1else:high = m - 1
if low > high:print("failed")

第十章  程序中的函数

函数四要素：

• 函数名：标识函数的名字
• 参数：输入数据传递给函数的变量
• 函数体：实现函数功能的代码块
• 返回值：函数处理完返回给外界的值

将二分查找封装成函数：

def binary_search(arr, tn):low = 0high = len(arr) - 1while low <= high:m = int((high - low) / 2) + lowif arr[m] == tn:return melse: if arr[m] < tn:low = m + 1else:high = m - 1if low > high:return -1

arr = [3, 5, 7, 9, 12, 15, 18, 32, 66, 78, 84, 103, 209]  # 待查序列
tn = 5  # 目标数result = binary_search(arr, tn)
if result > 0:print("success:", result)
else:print("failed")

函数的作用主要有三个：

• 重用：重复使用
• 抽象：只需要知道功能，参数，返回值即可
• 封装：将抽象的功能包装

arr = []  #生成arr
for i in range(0, 1001):arr.append(i)for tn in range(1, 1001):  # 1-1000的数都可以做一次二分查找result = binary_search(arr, tn)if result >= 0:print("success:", result)elseprint("failed")

函数参数的简化理解：

• 如果变量是基础类型，就算将它传给函数，调用完后，原值不变
• 如果变量是列表类型，将其传给函数调用后，列表中内容改变。

第十一章  编程实现猜数游戏

low = 1
high = 1000  # 范围
loop_num = 0  # 初始循环次数为 0while low <= high:m = int((high - low) / 2) + lowloop_num += 1print("[Loop %s]: My guess is %s, and high is %s" % (loop_num, low, high))user_input = ""while user_input != '1' and user_input != '2' and user_input != '3':print("1) %s == sn 2) %s < sn 3) %s > sn." % (m, m, m))user_input = input("Your option: ")user_input = user_input.strip()if user_input == '1':print("Success: sn is :", m)breakelse:if user_input == '2':low = m + 1else:high = m - 1if low > high:print("failed")

防止bug危害的方法：

• 代码层：代码审查
• 运行层：软件测试
• 开发层：测试驱动开发，先写测试用例

第十二章  二分查找的变形

含有重复目标数组的二分查找，并确定重复目标数的头或者尾

def repeating_sequence_binary_search(arr, tn, delta):low = 0high = len(arr) - 1while low <= high:m = int((high - low) / 2) + lowif arr[m] == tn:  # 找到目标数之后根据delta确定寻找方向的数是否等于目标数while 0 <= m + delta < len(arr) and arr[m + delta] == tn:  # m+delta一定判断范围是否越界，and判断有先后顺序m += deltareturn melse:if arr[m] < tn:low = m + 1else:high = m - 1if low > high:return -1

在找到目标数之后，m + delta环节再做二分查找，快速找到头或尾元素

def quick_repeating_sequence_binary_search(arr, tn, delta):low = 0 high = len(arr) - 1while low <= high:m = int((high - low) / 2) + lowif arr[m] == tn:if 0 <= m + delta < len(arr) and arr[m + delta] == tn:if delta < 0:  # 在有某一个方向上的其他重复数等于tn的时候，直接在该方向做二分查找high = m - 1else:low = m + 1else:return melse:if arr[m] < tn:low = m + 1else:high = m - 1if low > high:return -1

旋转数列的二分查找

旋转数列的三种情况：

• [14, 17, 29, -3, 0, 1, 5, 8, 12]     情况1：arr[m] < arr[low]
• [5, 8, 12, 14, 17, 29, -3, 0, 1]     情况2：arr[m] > arr[high]
• [-3, 0, 1, 5, 8, 12, 14, 17, 29]     情况3：arr[m] 是未经过旋转的有序数列

所有三种情况中，只要数列经过旋转，所有的 arr[low] > arr[high]。

情况1，如果找比 arr[m] 小的数字，只有左边一种可能

情况2， 如果找比 arr[m] 大的数字，只有右边一种可能

def binary_search_in_rotated_sequence(arr, tn):low = 0high = len(arr) - 1while low <= high:m = int((high - low) / 2) + lowif arr[m] == tn:return melse:if arr[m] < tn:  # 如果中间数比目标数小，寻找比m大的数if arr[m] < arr[low]:  # 第一种情况下，比m大的数有两种可能if arr[low] <= tn: # 1.如果low比目标数小，目标数一定在m左边high = m - 1else:              # 2.如果low比目标数大，目标数在m右边low = m + 1else:                  # 其他两种情况low = m + 1        # 比m大的数都在右侧else:                      # 如果中间数比目标数大，寻找比m小的数if arr[m] > arr[high]: # 第二种情况下，比m小的数有两种可能if arr[high] >= tn:# 1.如果high比目标数大，小的数在m右侧low = m + 1else:              # 2.如果high比目标数小，小的数在m左侧high = m - 1else:high = m - 1       # 其他两种情况小的数都在左侧if low > high:return -1

代码优化

def binary_search_in_rotated_sequence(arr, tn):low = 0high = len(arr) - 1while low <= high:m = int((high - low) / 2）+ lowif arr[m] == tn:return melse:if arr[m] < tn:                  # m 比 tn 小，找一个大的数if arr[m] < arr[low] <= tn:  # 只有第一种情况下比low大的数才向左找high = m - 1else:                        # 其他情况向右找low = m + 1else:                            # m 比 tn 大， 找一个小的数if arr[m] > arr[high] >= tn: # 只有第二种情况下比high小的数向右找low = m + 1                           else:high = m - 1             # 其他情况向左找  if low > high:return -1

包含重复元素的旋转数列二分查找

def binary_search_in_rotated_repeating_sequence(arr, tn, delta):low = 0high = len(arr) - 1if delta < 0 and arr[0] == tn:    # 头尾元素需要特殊处理，旋转的缘故，重复数存在头尾元素相同的情况return 0if delta > 0 and arr[-1] == tn:return len(arr) - 1while low <= high:m = int((high - low) / 2) + low if arr[m] == tn:if 0 <= m + delta < len(arr) and arr[m + delta] == tn:if delta < 0:high = m - 1else:low = m + 1else:return melse:if arr[m] < tn:if arr[m] < arr[low] <= tn:high = m - 1else:low = m + 1else:if arr[m] > arr[high] >= tn:low = m + 1else:high = m - 1if low > hgih:return -1    

第十三章  认识排序算法

排序就需要交换

def swap(arr, i, j):  # 在数组arr中，交换下标i和j的元素if len(arr) < 2:  # 长度小于2，不需要交换returnif i < 0 or i >= len(arr) or j < 0 or j >= len(arr):  # 超过下标范围，不需要交换returnif i == j:  # 下标相等，不需要交换returntmp = arr[i]arr[i] = arr[j]arr[j] = tmpreturn

第十四章  几种简单排序算法

选择排序

• 从未排好序的数列中选择最小的数放在排好序的数列后面

def selection_sort(arr):for start_position in range(0, len(arr)):  # 从前往后遍历序列min_position = start_position          # 处理最小值设为开头for i in range(start_position + 1, len(arr)):   # 遍历剩余未拍好序列if (arr[i] < arr[min_position]):            # 将min_position设置到最小位置min_position = iswap(arr, start_position, min_position)         # 将当前循环下最小值交换到start_positonreturn

冒泡排序：

• 从前往后或从后往前遍历未排好序列，两两比较交换，是最值上浮

def bubble_sort(arr):for i in range(0, len(arr)):  # 遍历整个序列swapped = False           # 设置交换标志位for j in range(len(arr) - 1, i, -1):  # 从后向前遍历未排好序队列if arr[j] < arr[j - 1]:           # 如果当前数比前一个数小swap(arr, j, j - 1)           # 交换swapped = True                # 设置交换标志位为trueif not swapped:                       # 如果未交换，说明已排好，跳出循环returnreturn

插入排序：

• 从后面找一个数，遍历插入前面已排好序的队列中

def insertion_sort(arr):if len(arr) == 1:  # 长度等于1，不需要排序returnfor i in range(1, len(arr)):  # 默认第一个元素已排好序，从第二个元素开始遍历for j in range(i, 0, -1): # 0 ~ i是要进行插入排序的队列if arr[j] < arr[j - 1]:  # 如果存在后一个数比前一个数小，交换swap(arr, j, j - 1)else:break                # 否则认为已排好序，结束本次循环return

简单排序在数据量大的时候就可能面临性能问题。

第十五章  必须掌握的排序算法

快速排序，与二分查找并驾齐驱。

简单分区函数：

def partition(arr):  # 分治if len(arr) < 2:return arr, None, Noneleft_partition = []   # 定义左分区right_partition = []  # 定义右分区pivot = arr[0]        # 定义轴for i in range(1, len(arr)):  # 遍历轴以外的数列if arr[i] <= pivot:       # 小于等于轴，添加左分区left_partition.append(arr[i])else:fight_partition.append(arr[i])  # 反之，添加到右分区return left_partition, pivot, right_partition  # 返回左分区，轴，右分区

进行修改，使上述思路返回的还是一个列表

def partition(arr):  # 分区函数if len(arr) < 2:  return - 1left_partition = []  # 定义左分区right_partition = []  # 定义右分区pivot = arr[0]        # 定义轴for i in range(1, len(arr)):  # 遍历轴以外的所有元素if arr[i] <= pivot:left_partition.append(arr[i])   # 比轴小放左分区else:right_partition.append(arr[i])   # 比轴大放右分区arr[0:len(left_partition)] = left_partition[0:len(left_partition)]   #将左分区放到原数列arr[len(left_partition)] = pivot   # 轴放到原数列arr[len(letf_partition) + 1:len(arr)] = right_partition[0:len(right_partition)]  # 右分区放到原数列return len(left_partition)  # 分区之后轴的位置

再升级到任意区间：

def partition(arr, low , high):if low >= high:return -1left_partition = []right_partition = []pivot = arr[low]for i in rang(low + 1, high + 1):  # 遍历轴后的区间if arr[i] <= pivot:left_partition.append(arr[i])else:right_partition.append(arr[i])arr[low:low + len(left_partition)] = left_partition[0:len(left_partition)]arr[low + len(left_partition)] = pivotarr[low + len(left_partition) + 1:hight + 1] = right_partition[0:len(right_partition)]return low + len(left_aprtition)  # 返回轴的位置

再升级，压缩空间复杂度

def partition_v2(arr, low, high):  # 改进的分区算法if low >= high:return -1pi = low      # 用指针代替赋值给左右两个队列和轴li = low + 1ri = highwhile li <= ri:      # 两个指针没有出现错位if arr[li] > pi:       # 如果左边指针比轴大swap(arr, li, ri)  # 跟右边指针元素交换位置ri = ri - 1        # 右边指针向左else:                  li = li + 1        # 否则，不动，左边指针往右pi = li - 1                # 轴位置在左边指针减1的位置swap(arr, low, pi)         # 将low 和轴位置的值交换return pi                  # 返回轴位置

通过分区用分治的思想实现快速排序

用一个二维数组来表示待分的区域，迭代表示

[[a1, b1],

[a2, b2],

...

[an, bn]]

思路：一开始low和high之间为待分区间，第一次分出了左右两个区间，将这两个区间添加到二维数组，同样的方法对新的区间再分，再添加到二维数组中，直到不可分为止

def q_sort_iteration(arr, low, high):   # 迭代的方法if low >= high:returnregions = [[low, high]]    # 存放迭代的区域的二位数组i = 0while i < len(regions):    # 用数组长度控制循环low = regions[i][0]    # low是二位数组中一行第一个数high = regions[i][1]   # high是二位数组中一行中第二个数p = partition_v2(arr, low, high)   # 找到这一行的轴if p != -1:regions.append([low, p - 1])    # 以轴为单位划分区域regions.append([p + 1, high])i = i + 1return

第十六章  递归实现快速排序

递归的基本函数表示

在函数体内部调用函数本身

def recursion():recursion()return

限制递归次数

def recursion(depth):if depth < 1000:recursion(depth + 1)return

斐波那契数列

def fibonacci(n):if n < 0:print("invalid input")elif n == 0:return 0elif n == 1:return 1else:return fibonacci(n - 1) + fibonacci(n - 2)

递归实现快速排序

def qsort_recursion(arr, low, high):if low >= high:returnp = partition_v2(arr, low, high)qsort_recursion(arr, low, p - 1)qsort_recursion(arr, p + 1, high)return

第十七章  算法精进

算法的五个层次

• 听说
• 了解
• 理解
• 实现
• 应用

例题：

实现一个函数，满足如下要求：输入一个正整数，输出也是正整数；输出值是与输入值平方根最近的那个数；整个过程只能用加减乘除，算法时间复杂度要求尽量小。

分析：

1、实现一个函数，函数四要素，函数名、参数、函数体、返回值

• 函数名：目的，该函数是要求输入值平方根最近的整数，所以命名为closest_sort
• 参数：输入是一个整数，命名为 n
• 返回值：整数，由函数体中命名而来
• 函数体：过程，如何实现函数的目的

2、不能开方，就找一个数的平方最接近输入值，找，就是查找算法，考虑二分查找

def closest_sqrt(n):if n <= 0:print("invalid input")return -1low = 1high = nwhile low <= high:m = int((high - low) / 2) + lowif m * m == n:return melif m * m < n < (m + 1) * (m + 1):if n - m * m > (m + 1) * (m + 1) - n:return m + 1else:return melse:if m * m > n:high = m - 1else:low = m + 1return -1