2.Python基础 - 数据结构与算法 - 《Python技术体系》

1.Python内置类型性能分析
- list内置操作的时间复杂度
- dict内置操作的时间复杂度
2.排序算法
4.栈
5.队列
6.堆
7.树与树算法

1.Python内置类型性能分析

list内置操作的时间复杂度

list内置操作的时间复杂度.png

dict内置操作的时间复杂度

dict内置操作的时间复杂度.png

2.排序算法

常见排序算法效率比较

冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。冒泡排序.gif

def bubble_sort(arr):
    _len = len(arr)
    if _len <= 1:
        return
    for i in range(_len - 1):
        for j in range(_len - 1 - i):
            if arr[j + 1] < arr[j]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
bubble_sort(a_list)
print(a_list)

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。选择排序.gif

def select_sort(arr):
    _len = len(arr)
    if _len <= 1:
        return
    for i in range(_len - 1):
        min_idx = i
        for j in range(i + 1, _len):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
select_sort(a_list)
print(a_list)

插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序.gif

def insert_sort(lst):
    _len = len(lst)
    if _len <= 1:
        return
    for i in range(1, _len):
        for j in range(i, 0, -1):
            if lst[j] < lst[j - 1]:
                lst[j], lst[j - 1] = lst[j - 1], lst[j]
            else:
                break
a_list = [1, 12, 2, 11, 13, 5, 6, 18, 4, 9, -5, 3, 11]
insert_sort(a_list)
print(a_list)

快速排序

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。
步骤为：

挑选基准值：从数列中挑出一个元素，称为”基准”（pivot）;
分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成;
递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。
选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。快速排序.gif

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    low = [x for x in arr[1:] if x < pivot]
    high = [x for x in arr[1:] if x >= pivot]
    return quick_sort(low) + [pivot] + quick_sort(high)
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
a_list = quick_sort(a_list)
print(a_list)

归并排序

归并排序（Merge sort），是创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
分治法:

分割：递归地把当前序列平均分割成两半。
集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。 ```python def merge_sort(arr): _len = len(arr) if _len <= 1:
```
  return arr
```
mid = _len // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:])

merged = [] while left and right:
```
  merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
```
merged.extend(right if right else left)

return merged

a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20] a_list = merge_sort(a_list) print(a_list)


<a name="2u7MO"></a>
## 3.搜索算法
<a name="ofrFd"></a>
### 二分法查找
二分搜索是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。<br />![二分查找.png](https://cdn.nlark.com/yuque/0/2020/png/1987609/1606473931636-c4c9bc11-580d-41c8-afbb-e4e3058b983d.png#align=left&display=inline&height=244&margin=%5Bobject%20Object%5D&name=%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.png&originHeight=244&originWidth=382&size=5067&status=done&style=none&width=382)
```python
def binary_search(arr, l, r, target):
    if r >= l:
        mid_idx = (r - l) // 2 + l
        mid = arr[mid_idx]

        if mid > target:
            return binary_search(arr, l, mid_idx - 1, target)
        elif mid < target:
            return binary_search(arr, mid_idx + 1, r, target)
        else:
            return '{}在列表中，下标为 [{}]'.format(target, mid_idx)
    else:
        return '{}不在列表中'.format(target)


a_list = [17, 20, 26, 31, 44, 54, 55, 77, 93]
# a_list = [18]
print(binary_search(a_list, 0, len(a_list) - 1, 17))

4.栈

后进先出（LIFO, Last In First Out）

5.队列

队列是一种先进先出的（First In First Out）的线性表，简称FIFO。

6.堆

import heapq

a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]

print(a_list)
print(heapq.nlargest(3, a_list))  # 输出列表中最大的三个数

7.树与树算法

树的概念

树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点有零个或多个子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；

比如说：
树1.png
树2.png

树的术语

节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点的度称为树的度；
叶节点或终端节点：度为零的节点；
父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；
堂兄弟节点：父节点在同一层的节点互为堂兄弟；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
森林：由m（m>=0）棵互不相交的树的集合称为森林；

树的种类
无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
- 二叉树：每个节点最多含有两个子树的树称为二叉树；
  - 完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;
  - 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
  - 排序二叉树（二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树）；
- 霍夫曼树（用于信息编码）：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
- B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树。
  树的存储与表示
  顺序存储：将数据结构存储在固定的数组中，然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。

链式存储：
由于对节点的个数无法掌握，常见树的存储表示都转换成二叉树进行处理，子节点个数最多为2

常见的一些树的应用场景

xml，html等，那么编写这些东西的解析器的时候，不可避免用到树
路由协议就是使用了树的算法
mysql数据库索引
文件系统的目录结构
所以很多经典的AI算法其实都是树搜索，此外机器学习中的decision tree也是树结构

树5.jpeg

数据结构与算法