6. 排序算法

6.3 插入排序

插入排序思想：

• 拿后一位与前一位比较，若后者大，则继续往后比较
• 若后者小，则两者交换，如此往复，直至比至第一个元素

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

# 开始比较，整体是往后移动的，当遇到前一个比后一个大，那就往前移动比较，直至比较到第一个元素为止
a[1] < a[0]         # 交换，a[0], a[1] = a[1], a[0]        a = [26, 54, 93...]
a[2] > a[1]         # 不交换                             a = [26, 54, 93, 17....]

a[3] < a[2]         # 交换，a[2], a[3] = a[3], a[2]        a = [26, 54, 17, 93...]
a[2] < a[1]         # 交换，a[1], a[2] = a[2], a[1]        a = [26, 17, 54, 93...]
a[1] < a[0]         # 交换，a[0], a[1] = a[1], a[0]        a = [17, 26, 54, 93...]

规律：

• a[i] > a[i-1]：不交换
• a[i] < a[i-1]：交换，且 i-1，再比较 a[i-2] 与 a[i-1] 大小，一直比较下去，直至 i=0 为止

while i > 0:
    if alist[i] < alist[i-1]:
        alist[i-1], alist[i] = alist[i], alist[i-1]
        i -= 1
    else:
        break

最终实现：

def insert_sort(alist):
    n = len(alist)
    # 控制整体往后移动，需要移动到 n-1 的位置，即倒数第二个元素位置
    for j in range(n):
        i = j
        # 控制往前移动，直至移动到第二个元素为止
        while i > 0:
            if alist[i] < alist[i - 1]:
                alist[i - 1], alist[i] = alist[i], alist[i - 1]
                i -= 1
            else:
                break

if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(alist)
    insert_sort(alist)
    print(alist)

• 若 alist[i] < alist[i - 1]，即意味着后一个比前一个小，两者进行交换，再往前移动比较 alist[i-1] < alist[i - 2]，如此往复，i 每次减少，直至为 0
• 若 alist[i] < alist[i - 1]，则跳出循环，i 则往后移动一位，因为 i=j，而 j 是整个顺序表的索引循环。

运行结果如下：

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

6.4 希尔排序

希尔排序其核心也是插入排序，只不过引入了一个步长 gap 的概念。

[图片上传失败...(image-c44083-1593096306908)]

image

[图片上传失败...(image-1deb4b-1593096306908)]

def shell_sort(alist):
    n = len(alist)
    gap = n // 2        # 步长
    while gap > 0:
        for j in range(gap, n):  # 要循环到最后一个元素，与倒数第二个元素比较
            i = j
            while i > 0:
                if alist[i] < alist[i - gap]:
                    alist[i], alist[i - gap] = alist[i - gap], alist[i]
                    i -= gap
                else:
                    break
        # 缩短 gap 步长
        gap //= 2


if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(alist)
    shell_sort(alist)
    print(alist)

运行结果如下：

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

6.5 快速排序

第一次假定基准值为数列第一个元素，即：medium_value = alist[0]

• 两个游标，low 往后移动，找出比基准值大的元素，与 height 交换（此时 low 停止，换 height 移动）。若比基准值小则不交换
• height 往前移动，找出比基准值小的，与 low 交换（height 停止，换 low 移动），若比基准大，不交换
• 通过上面方式控制两个游标，使得比基准值大的数字始终在它右边，比起小的始终在它左边

[图片上传失败...(image-717898-1593096306908)]

实现

def quick_sort(alist, first, last):
    """快排"""
    if first >= last:   # 递归的退出条件
        return
    mid_value = alist[first]    # 设定起始元素为要寻找位置的基准元素
    low = first     # low为序列左边的由左向右移动的游标
    high = last     # high为序列右边的由右向左移动的游标

    # 只排序了一个元素
    while low < high:
         # 如果low与high未重合，high指向的元素不比基准元素小，则high向左移动
        while low < high and alist[high] >= mid_value:
            high -= 1

        alist[low] = alist[high]    # 将high指向的元素放到low的位置上
       
        # 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
        while low < high and alist[low] < mid_value:
            low += 1
        alist[high] = alist[low]    # 将low指向的元素放到high的位置上

    # 从循环退出时，low==high
    alist[low] = mid_value

    # 对low左边的列表执行快速排序
    quick_sort(alist, first, low-1)

    # 对low右边的列表排序
    quick_sort(alist, low+1, last)


if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(alist)
    quick_sort(alist, 0, len(alist)-1)
    print(alist)

方法二

def quick_sort(array):
    if len(array) < 2:
        return array
    else:
        # 基准值
        pivot = array[0]
        less = [i for i in array[1:] if i < pivot]
        print('less', less)
        greater = [j for j in array[1:] if j > pivot]
        print('greater', greater)
        return quick_sort(less) + [pivot] + quick_sort(greater)

if __name__ == '__main__':
    array = [1, 3, 5, 8, 2, 9, 4]
    print(array)
    print(quick_sort(array))

6.6 归并排序

[图片上传失败...(image-52f4e-1593096306908)]

def mermge_sort(alist):
    """归并排序"""
    n = len(alist)
    if n <= 1:
        return alist
    mid = n // 2

    # 递归，将数列分割成每个一份
    left_li = mermge_sort(alist[: mid])
    right_li = mermge_sort(alist[mid:])

    # 合并，定义两个游标 left_point、right_point
    # 分别在前一个数列和后一个数列中移动，表示在数列中的索引
    left_point, right_point = 0, 0         # 刚开始都为 0

    # 定义一个列表用于接收排序后的数列
    result = []

    while left_point < len(left_li) and right_point < len(right_li):
        if left_li[left_point] < right_li[right_point]:
            result.append(left_li[left_point])
            left_point += 1
        else:
            result.append(right_li[right_point])
            right_point += 1

    result += left_li[left_point:]
    result += right_li[right_point:]

    return result


if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print(alist)
    sorted_alist = mermge_sort(alist)
    print(alist)
    print(sorted_alist)

运行结果如下：

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

7. 查找算法

查找/搜索一个元素是否在某种数据结构中，是非常常见的。搜索的几种常见方法：顺序查找、二分法查找、二叉树查找、哈希查找

7.1 二分查找

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

image

二分查找必须满足以下两个条件：

• 要查找的数列必须是有序的，所有只能是顺序表，不能是链表
• 数列中元素要么是从小到大排列的，要么从大到小排列的

递归实现

递归实现，每次传递的都是一个新的数列

def binary_search(alist, item):
    """递归"""
    n = len(alist)
    if n > 0:
        mid = n // 2
        if alist[mid] == item:
            return True
        # 要查找的元素在 mid 左边
        elif item < alist[mid]:
            return binary_search(alist[:mid], item)
        else:
            return binary_search(alist[mid+1:], item)

    return False

if __name__ == '__main__':
    li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
    print(binary_search(li, 31))
    print(binary_search(li, 9999))

非递归实现

def binary_search_2(alist, item):
    """非递归"""
    n = len(alist)
    first = 0       
    last = n - 1
    while first <= last:
        mid = (first + last) // 2
        if alist[mid] == item:
            return True
        elif item < alist[mid]:
            last = mid - 1
        else:
            first = mid + 1
    return False


if __name__ == '__main__':
    li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
    print(binary_search(li, 31))
    print(binary_search(li, 9999))

过程：

alist = [1, 2, 3, 4, 5,  6, 7]
# first, last, mid, alist[mid]，要查找的元素 0
# 第一次
(0, 6),  mid=3,  alist[3] > 0

# 第二次
(0, 2), mid=1, alist[1] > 0

# 第三次
(0, 1), mid=0, alist[0] > 0

# 第四次，退出循环
(0, 0), mid=0, alist[0] >0

时间复杂度

• 最优：O(1)
• 最坏：O(logn)

8. 树和树算法

8.1 什么是树

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

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

树结构：

image

---

树的术语

• 节点的度：一个节点含有的子树的个数称为该节点的度（如：上面节点 3，它的度为 2）
• 树的度：一棵树中，最大的节点的度称为树的度（如：上面节点 1 是最大的节点）
• 叶子节点或终端节点：度为零的节点，即没有子节点的节点（如：7 、8 、9 、 5、 6等）
• 父亲节点或父节点：即节点的父亲，有且仅一个（如： 7 的父节点为 3）
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点，（如：7 、 8 是 3 的子节点）
• 兄弟节点：具有相同父节点的节点互称为兄弟节点（如：7 和 8 是兄弟节点，共同父亲为 3）
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推（如：上面总共有 4 层）
• 树的高度或深度：树中节点的最大层次，（如：树的深度为 4 ）
• 堂兄弟节点：父节点在同一层的节点互为堂兄弟（如：7 和 9 互为堂兄弟）
• 节点祖先：从根到该节点所经分支上的所有节点（如：7 的祖先节点有：0 、1、 3、 4）
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙（如：1 的子孙有 3、 4、 7、 8、 9）
• 森林：由m（m>=0）棵互不相交的树的集合称为森林

---

树的种类

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

---

树的存储于表示

• 顺序表实现：遍历速度快，但浪费空间，非主流实现方式（不常用）
• 链表实现：缺陷是指针域指针个数不定，改进（将多叉树转换为二叉树，每个子节点有且最多只有两个指针）

---

树的应用场景

• 解析 xml，html 时，需要用到树算法

• 路由协议使用树算法

• MySQL 数据库索引

• 文件系统目录结构

• 很多经典 AI 算法其实就是树算法，机器学习中的 decision tree 也是树结构

8.2 二叉树

二叉树的子节点最多只有两个子树，子树又分为左子树（left subtree）和右子树（right tree）。

完全二叉树

若二叉树高度为 n，那么除第 n-1 层外，其他各层的节点数都达到了最大个数。

如下图中：除 H、I、J 外，其他节点都有两个子节点（子树），那么这个二叉树就是完全二叉树。

[图片上传失败...(image-762373-1593096306908)]

满二叉树

即除叶子节点外，所有节点都达到最大节点数（即都有两个子树）。

image

---

二叉树性质

• 在二叉树的第 i 层上至多有 2^(i-1) 个结点（i>0）
• 深度为 k 的二叉树至多有 2^k - 1 个结点（k>0）
• 对于任意一棵二叉树，如果其叶结点数为 N0，而度数为 2 的结点总数为 N2，则 N0=N2+1
• 具有 n 个结点的完全二叉树的深度必为 log2(n+1)
• 对完全二叉树，若从上至下、从左至右编号，则编号为 的结点，其左孩子编号必为 2i，其右孩子编号必为 2i＋1；其双亲的编号必为 i/2（i＝1 时为根，除外）

二叉树的节点表示以及树的创建

1、节点表示：

class Node(object):
    """节点类"""
    def __init__(self, elem):
        """
        :param elem: 节点本身
        :param lchild: 左孩子
        :param rchild: 右孩子
        """
        self.elem = elem
        self.lchild = None
        self.rchild = None
        pass

2、二叉树实现：

class Tree(object):
    """二叉树"""
    def __init__(self):
        self.root = None        # 根节点

    def add(self, elem):
        """增加元素"""
        node = Node(elem)
        if self.root == None:
            self.root = node
            return
        queue = []
        queue.append(self.root)

        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild == None:
                cur_node.lchild = node
                return
            else:
                queue.append(cur_node.lchild)

            if cur_node.rchild == None:
                cur_node.rchild = node
                return
            else:
                queue.append(cur_node.rchild)

8.3 二叉树的遍历

遍历二叉树元素有两种方式：

• 广度优先：按照根节点——>左节点——>右节点方式从上到下遍历，一般采用队列实现
• 深度优先：即尽可能深地遍历树的节点，分为先序、中序和后序遍历，一般采用递归（也可以用堆栈）实现

广度优先

从根节点开始，再是左孩子节点，最后才是右孩子节点，从上到下依次遍历：

def breadth_travel(self):
    """广度优先：根左右"""
    if self.root == None:
        return
    queue = [self.root]
    while queue:
        cur_node = queue.pop(0)
        print(cur_node.elem, end=' ')
        if cur_node.lchild is not None:
            queue.append(cur_node.lchild)
        if cur_node.rchild is not None:
            queue.append(cur_node.rchild)

深度优先

1、先序遍历（根左右）

从根节点开始，再遍历左孩子节点，直至叶子节点，再遍历右孩子节点：

 def preorder(self, node):
      """先序遍历：根左右"""
      if node is None:
          return
      print(node.elem, end=' ')
      self.preorder(node.lchild)
      self.preorder(node.rchild)

2、中序遍历

从左孩子节点开始，再遍历根节点，再遍历右孩子节点：

def inorder(self, node):
      """中序遍历：左根右"""
      if node is None:
          return
      self.inorder(node.lchild)
      print(node.elem, end=' ')
      self.inorder(node.rchild)

3、后序遍历

从左孩子节点开始，再遍历右孩子节点，再遍历根节点：

def postorder(self, node):
    """后序遍历：左右根"""
    if node is None:
        return
    self.postorder(node.lchild)
    self.postorder(node.rchild)
    print(node.elem, end=' ')

测试：

if __name__ == "__main__":
    tree = Tree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.add(8)
    tree.add(9)
    tree.preorder(tree.root)
    print(" ")
    tree.inorder(tree.root)
    print(" ")
    tree.postorder(tree.root)
    print(" ")

    tree.breadth_travel()

运行结果：

0 1 3 7 8 4 9 2 5 6         # 先
7 3 8 1 9 4 0 5 2 6         # 中
7 8 3 9 4 1 5 6 2 0         # 后
0 1 2 3 4 5 6 7 8 9         # 广

[图片上传失败...(image-4416dc-1593096306908)]

Tips：如果想确定一颗二叉树，至少需要中序和前序（或后序）两种方式，中序是必须的