一、数据结构与算法

一、数据结构和算法基础

1.算法的概念

算法是独立存在的一种解决问题的方法和思想
算法的五大特性:
- 输入:算法具有0个或多个输入
- 输出:算法至少有1个或多个输出
- 有穷性:算法在有限的步骤之后会自动结束而不会无限循环,并且每一个步骤可以在可接受的时间内完成
- 确定性:算法中的每一步都有确定的含义,不会出现二义性
- 可行性:算法的每一步都是可行的,也就是说每一步都能够执行有限的次数完成

2.算法效率衡量

执行时间反应算法效率
- 实现算法程序的执行时间可以反应出算法的效率(在特定计算机环境下),即算法的优劣
时间复杂度与‘大O记法’
- ‘大O记法’
  
  对于单调的整数函数f,如果存在一个整数函数g和实常数c>=0,使得对于充分大的n,总有f(n)<=c*g(n),就说函数g是f的一个渐进函数(忽略常数),记为f(n)=O(g(n)),即在趋向无穷的极限意义下,函数f的增长速度受到函数g的约束,亦即函数f与函数g的特征相似
- 时间复杂度
  
  假设存在函数g,使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n)),则称O(g(n))为算法A的渐近时间复杂度,简称时间复杂度,记为T(n)
最坏时间复杂度
- 最优时间复杂度
  - 算法完成工作最少需要多少基本操作
- 最坏时间复杂度
  - 算法完成工作最多需要多少基本操作
- 平均时间复杂度
  - 算法完成工作平均需要多少基本操作
时间复杂度的几条基本计算规则
- 基本操作,即只有常数项,认为其时间复杂度为O(1)
- 顺序结构,时间复杂度按加法进行计算
- 循环结构,时间复杂度按乘法进行计算
- 分支结构,时间复杂度取最大值
- 判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要和常数项可以忽略
- 在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度

3.代码执行时间测量模块itmeit

timeit模块

timeit模块可以用来测试一小段python代码的执行速度

class timeit.Timer(stmt='pass', setup='pass', timer=<timer function>)
# Timer是测量小段代码执行速度的类
# stmt参数是要测试的代码语句(statment)
# setup参数是运行代码时需要的设置
# timer参数是一个定时器函数,与平台有关


timeit.Timer.timeit(number=1000000)
# Timer类中测试语句执行速度的对象方法,number参数是测试代码时的测试速度,默认为10000000次
# 方法返回执行代码的平均耗时,一个float类型的秒数.


import timeit
def t():
    li = [i for in in range(1000)]
    
timer_ = timeit.Timer(stmt='t()', setup='from __main__ import t')
time_ = timer_.timeit(1000)
print(time_)

4.数据结构

概念

数据结构指数据对象中数据元素之间的关系
算法和数据结构的区别
- 数据结构只是静态的描述了数据元素之间的关系
- 高效的程序需要在数据结构的基础上设计和选择算法
  - 程序=数据结构+算法
  - 算法是为了解决实际问题而设计的,数据结构是算法需要处理的问题载体

5.抽象数据类型(Abstract Data Type)

抽象数据类型(ADT)的含义

是指一个数学模型以及定义在此数学模型上的一组操作,即把数据类型和数据类型上的运算捆在一起,进行封装
引入抽象数据类型的目的

把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开,使它们互相独立
常用的数据运算有五种:
- 插入
- 删除
- 修改
- 查找
- 排序

二、顺序表

线性表

一个线性表是某类元素的一个集合,记录着元素之间的一种顺序关系
按线性表的实际存储方式,分为两种实现模型
- 顺序表
  
  将元素顺序地存放在一块连续的存储区里,元素间的顺序关系由它们的存储顺序自然表示
- 链表
  
  将元素存放在通过链接构造起来的一系列存储块中

1.顺序表的形式

图解
- 图a
  - 表示的是顺序表的基本形式,数据元素本身连续存储,每个元素所占的存储单元大小固定相同
  - 元素的下标是其逻辑地址,而元素存储的物理地址(实际内存地址)可以通过存储区的起始地址Loc(e0)加上逻辑地址(第i个元素)与存储单元大小(c)的乘积计算而得,即Loc(ei)=Loc(e0)+c*i
  - 访问指定元素时无需从头遍历,通过计算便可获得对应地址,其时间复杂度为O(1)
- 图b
  - 当元素的大小不统一,则须采用图b的元素外置的形式,将实际数据元素另行存储,而顺序表中各单元位置保存对应元素的地址信息(即链接)
  - 由于每个链接所需的存储量相同,通过a中总结的公式,可以计算出元素链接的存储地址,而后顺着链接找到实际存储的数据元素
  - 此时图中的c不再是数据元素的大小,而是存储一个链接地址所需的存储量,这个量通常很小

2.顺序表的结构与实现

顺序表的结构

一个顺序表的完整信息包括两部分,一部分是表中的元素集合,另一部分是为实现正确操作而需记录的信息,即有关表的整体情况的信息,这部分信息主要包括元素存储区的容量和当前表中已有的元素个数
顺序表的实现
- 图a
  - 一体式结构
  - 存储表信息的单元与元素存储区以连续的方式安排在一块存储区里,两部分数据的整体形成一个完整的顺序表对象
  - 一体式结构整体性强,易于管理,但是由于数据元素存储区域是表对象的一部分,顺序表创建后,元素存储区就固定了
- 图b
  - 分离式结构
  - 表对象里只保存与整个表有关的信息(即容量和元素个数),实际数据元素存放在另一个独立的元素存储区里,通过链接与基本表对象关联
元素存储区替换
- 一体式
  
  一体式结构由于顺序表信息区与数据区连续存储在一起,所以当想要更换数据区时,就只能整体搬迁,即整个顺序表对象(指存储顺序表的结构信息的区域)改变了
- 分离式
  
  分离式结构若想要更换数据区,只需要将表信息区中的数据区链接地址更新即可,而该顺序表对象不变
元素存储区扩充
- 定义
  
  采用分离式结构的顺序表,若将数据区更换为存储空间更大的区域,则可以在不改变表对象的前提下对其数据存储区进行了扩充,所有使用这个表的地方都不必修改.
  
  只要程序的运行环境(计算机系统)还有空闲存储,这种表结构就不会因为满了而导致操作无法进行.
  
  把采用这种技术实现的顺序表称为动态顺序表,因为其容量可以在使用中动态变化.
- 扩充的两种策略
  - 每次扩充增加固定数目的存储位置,如每次扩充增加10个元素位置,这种策略可称为线性增长
    
    特点:节省空间,但是扩充操作频繁,操作次数多
  - 每次扩充容量加倍,如每次扩充增加一倍存储空间
    
    特点:减少了扩充操作的执行次数,但可能会浪费空间资源,以空间换时间,推荐的方式

三、链表

定义

链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是不像顺序表一样连续存储数据,而是在每一个节点(数据存储单元)里存放下一个节点的位置信息(即地址)

1.单向链表

定义

单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域,这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值.
- 表元素域elem用来存放具体的数据
- 链接域next用来存放下一个节点的位置(python中的标识)
- 变量p指向链表的头节点(首节点)的位置,从p出发能找到列表中的任意节点

节点实现

class SingleNode(object):
    """单链表的节点"""
    def __init__(self, item):
        # item存放数据元素
        self.item = item
        # next是下一个节点的标识
        self.next = None

单链表的操作
- is_empty()链表是否为空
- length()链表长度
- travel()遍历整个链表
- add(item)链表头部添加元素
- append(item)链表尾部添加元素
- insert(pos, item)指定位置添加元素
- remove(item)删除节点
- search(item)查找节点是否存在

单链表的实现

class Node(object):
    """节点"""

    def __init__(self, elem):
        self.elem = elem
        self.next = None


class SingleLinkList(object):

    def __init__(self, node=None):
        self._head = node

    # 链表是否为空
    def is_empty(self):
        return self._head is None

    # 链表长度
    def length(self):
        cur = self._head  # cur游标，用来移动遍历节点
        count = 0  # count记录数量
        while cur is not None:
            count += 1
            cur = cur.next
        return count

    # 遍历整个链表
    def travel(self):
        cur = self._head  # cur游标，用来移动遍历节点
        while cur is not None:
            print(cur.elem, end=' ')
            cur = cur.next

    # 链表头部添加元素,头插法
    def add(self, item):
        node = Node(item)
        node.next = self._head
        self._head = node

    # 链表尾部添加元素，尾插法
    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            cur = self._head
            while cur.next is not None:
                cur = cur.next
            cur.next = node

    # 指定位置添加元素
    def insert(self, pos, item):
        pre = self._head
        count = 0
        if pos <= 0:
            self.add(item)
        elif pos > self.length() - 1:
            self.append(item)
        else:
            while count < int(pos) - 1:
                pre = pre.next
                count += 1
            node = Node(item)
            node.next = pre.next
            pre.next = node

    # 删除节点
    def remove(self, item):
        cur = self._head
        pre = None
        while cur is not None:
            if cur.elem = item:
                # 先判断此节点是否是头节点
                if cur == self._head
                    self._head = cur.next
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next

    # 查找节点是否存在
    def search(self, item):
        cur = self._head
        while cur is not None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False


if __name__ == "__main__":
    ll = SingleLinkList()
    print(ll.is_empty())
    print(ll.length())

    ll.append(23)
    ll.append(36)
    ll.append(7)
    ll.add(8)
    ll.insert(0, 10)
    ll.insert(3, 100)
    ll.insert(6, 101)
    print(ll.is_empty())
    print(ll.length())
    ll.travel()

链表域顺序表的对比

链表失去了顺序表随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大,但对存储空间的使用要相对灵活
- 虽然表面看起来复杂度都是O(n),但是链表和顺序表在插入和删除时进行的是完全不同的操作,链表的主要耗时操作是遍历查找,删除和插入操作本身的复杂度是O(1);顺序表查找很快,主要耗时的操作是拷贝覆盖,因为除了目标元素在尾部的特殊情况,顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作,只能通过拷贝和覆盖的方法进行

2.单向循环链表

定义

单链表的一个变形是单向循环链表,链表中最后一个节点的next域不再为None,而是指向链表的头节点
单向循环链表的操作
- is_empty()链表是否为空
- length()链表长度
- travel()遍历整个链表
- add(item)链表头部添加元素
- append(item)链表尾部添加元素
- insert(pos, item)指定位置添加元素
- remove(item)删除节点
- search(item)查找节点是否存在

单向循环链表的实现

class Node(object):
    """节点"""

    def __init__(self, elem):
        self.elem = elem
        self.next = None


class SingleLinkList(object):

    def __init__(self, node=None):
        self._head = node
        if node:
            node.next = node

    # 链表是否为空
    def is_empty(self):
        return self._head is None

    # 链表长度
    def length(self):
        if self.is_empty():
            return 0
        cur = self._head  # cur游标，用来移动遍历节点
        count = 1  # count记录数量
        while cur.next ！= self._head:
            count += 1
            cur = cur.next
        return count

    # 遍历整个链表
    def travel(self):
        if self.is_empty():
            return
        cur = self._head  # cur游标，用来移动遍历节点
        while cur.next != self._head:
            print(cur.elem, end=' ')
            cur = cur.next
        # 退出循环，cur指向尾节点，但尾节点的元素未打印
        print(cur.elem, end='')

    # 链表头部添加元素,头插法
    def add(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
            node.next = node
        else:
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            # 退出循环，cur指向尾节点
            node.next = self._head
            self._head = node
            cur.next = self._head

    # 链表尾部添加元素，尾插法
    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
            node.next = node
        else:
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            cur.next = node
            node.next = self._head

    # 指定位置添加元素
    def insert(self, pos, item):
        pre = self._head
        count = 0
        if pos <= 0:
            self.add(item)
        elif pos > self.length() - 1:
            self.append(item)
        else:
            while count < int(pos) - 1:
                pre = pre.next
                count += 1
            node = Node(item)
            node.next = pre.next
            pre.next = node

    # 删除节点
    def remove(self, item):
        if self.is_empty():
            return
        cur = self._head
        pre = None
        while cur.next != self._head:
            if cur.elem = item:
                # 先判断此节点是否是头节点
                if cur == self._head:
                    # 找尾节点
                    rear = self._head
                    while rear.next != self._head:
                        rear = rear.next
                    self._head = cur.next
                    rear.next = self._head
                else:
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next
        # 退出循环，cur指向尾节点
        if cur.elem == item:
            # 如果只有一个节点
            if cur.next == self._head:
                self._head = None:
            else:
                pre.next = cur.next

    # 查找节点是否存在
    def search(self, item):
        if self.is_empty():
            return False
        cur = self._head
        while cur.next != self._head:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        # 退出循环，cur指向尾节点
        if cur.elem == item:
            return True
        return False


if __name__ == "__main__":
    ll = SingleLinkList()
    print(ll.is_empty())
    print(ll.length())

    ll.append(23)
    ll.append(36)
    ll.append(7)
    ll.add(8)
    ll.insert(0, 10)
    ll.insert(3, 100)
    ll.insert(6, 101)
    print(ll.is_empty())
    print(ll.length())
    ll.travel()

3.双向链表

定义

一种更复杂的链表时‘双向链表’或‘双面链表’,每个结点有两个链接,:一个指向前一个结点,当此结点为第一个结点时,指向空值;而另一个指向下一个结点,当此结点为最后一个结点时,指向空值.
双向链表的操作
- is_empty()链表是否为空
- length()链表长度
- travel()遍历整个链表
- add(item)链表头部添加元素
- append(item)链表尾部添加元素
- insert(pos, item)指定位置添加元素
- remove(item)删除节点
- search(item)查找节点是否存在

双向链表的实现

class Node(object):
    """节点"""

    def __init__(self, elem):
        self.elem = elem
        self.next = None
        self.prev = None


class DoubleLinkList(object):

    def __init__(self, node=None):
        self._head = node

    # 链表是否为空
    def is_empty(self):
        return self._head is None

    # 链表长度
    def length(self):
        cur = self._head  # cur游标，用来移动遍历节点
        count = 0  # count记录数量
        while cur is not None:
            count += 1
            cur = cur.next
        return count

    # 遍历整个链表
    def travel(self):
        cur = self._head  # cur游标，用来移动遍历节点
        while cur is not None:
            print(cur.elem, end=' ')
            cur = cur.next

    # 链表头部添加元素,头插法
    def add(self, item):
        node = Node(item)
        node.next = self._head
        self._head = node
        node.next.prev = node

    # 链表尾部添加元素，尾插法
    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            cur = self._head
            while cur.next is not None:
                cur = cur.next
            cur.next = node
            node.prev = cur

    # 指定位置添加元素
    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos > self.length() - 1:
            self.append(item)
        else:
            cur = self._head
            count = 0
            while count < int(pos):
                count += 1
                cur = cur.next
            node = Node(item)
            node.next = cur
            node.prev = cur.prev
            cur.prev.next = node
            cur.prev = node

    # 删除节点
    def remove(self, item):
        cur = self._head
        while cur is not None:
            if cur.elem = item:
                # 先判断此节点是否是头节点
                if cur == self._head
                    self._head = cur.next
                    if cur.next:
                        # 判断链表是否只有一个节点
                        cur.next.prev =None
                else:
                    cur.prev.next = cur.next
                    if cur.next:
                        cur.next.prev = cur.prev
                break
            else:
                cur = cur.next

    # 查找节点是否存在
    def search(self, item):
        cur = self._head
        while cur is not None:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        return False


if __name__ == "__main__":
    ll = DoubleLinkList()
    print(ll.is_empty())
    print(ll.length())

    ll.append(23)
    ll.append(36)
    ll.append(7)
    ll.add(8)
    ll.insert(0, 10)
    ll.insert(3, 100)
    ll.insert(6, 101)
    print(ll.is_empty())
    print(ll.length())
    ll.travel()

四、栈与队列

1.栈

定义

栈(stack),又称堆栈,是一种容器,可存入数据元素、访问元素、删除元素,它的特点在于只能允许在容器的一端(称为栈顶端指标,top)进行加入数据(push)和输出数据(pop)的运算,没有位置概念,保证任何时候都可以访问,删除的元素都是此前最后存入的那个元素,确定了一种默认的访问顺序.

由于栈数据结构只允许在一端进行操作,因而按照后进先出(LIFO,Last in First Out )的原理操作.

栈的实现

栈可以通过线性表(顺序表或链表)来实现

class Stack(object):
    """栈"""

    def __init__(self):
        self.__list = []

    def push(self, item):
        """添加一个新的元素item到栈顶"""
        self.__list.append(item)

    def pop(self):
        """弹出栈顶元素"""
        return self.__list.pop()

    def peek(self):
        """返回栈顶元素"""
        if self.__list:
            return self.__list[-1]
        return None

    def is_empty(self):
        """判断栈是否为空"""
        return self__list == []

    def size(self):
        """返回栈的元素个数 """
        return len(self.__list)


if __name__ == "__main__":
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)
    print(s.pop())

2.队列

定义

队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表.

队列是一种先进先出的(First in First Out)的线性表,简称FIFO,允许插入的一端为队尾,允许删除的一端为队头,队列不允许在中间部位进行操作.

单向队列实现

class Queue(object):
    """队列"""

    def __init__(self):
        self.__list = list()

    def enqueue(self, item):
        """往队列中添加一个item元素"""
        self.__list.append(item)
        # self.__list.insert(0, item)

    def dequeue(self):
        """从队列头部删除一个元素"""
        return self.__list.pop(0)
        # return self.__list.pop()

    def is_empty(self):
        """判断一个队列是否为空"""
        return self.__list == []

    def size(self):
        """返回队列的大小"""
        return len(self.__list)

双端队列

定义

双端队列(duque, 全名double-ended queue),是一种具有队列和栈的性质的数据结构

双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行,双端队列可以在队列任意一端入队和出队.

双向队列实现

class Deque(object):
    """双端队列"""

    def __init(self):
        self.__list = list()

    def add_front(self, item):
        """往队列头部中添加一个item元素"""
        self.__list.insert(0, item)

    def add_rear(self, item):
        """往队列尾部中添加一个item元素"""
        self.__list.append(item)

    def pop_front(self):
        """从队列头部删除一个元素"""
        return self.__list.pop(0)

    def pop_rear(self):
        """从队列尾部删除一个元素"""
        return self__list.pop()

    def is_empty(self):
        """判断一个队列是否为空"""
        return self.__list == []

    def size(self):
        """返回队列的大小"""
        return len(self.__list

五、搜索与排序

排序算法(Sorting algorithm)是一种能将一串数据依照特定顺序进行排列的一种算法
排序算法的稳定性
- 稳定性
  
  稳定排序算法会让原本有相等键值的记录维持相对次序,即如果一个排序算法是稳定的,当有两个相等键值的记录R和S,且在原本的列表中R出现在S之前,在排序过的列表中R叶将会是在S之前.
  
  不稳定排序算法可能会在相等的键值中改变记录的相对次序.

1.冒泡排序

定义

冒泡排序(Bubble Sort)是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.遍历数列的工作是重复地进行直到没有再需要交换,即说该数列已经排序完成

这个算法的名字由来是因为越小的元素会经由交换慢慢‘浮’到数列的顶端
冒泡排序算法的运作:
- 比较相邻的元素,如果第一个比第二个大(升序),就交换他们两个
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这步做完后,最后的元素会是最大的数
- 针对所有的元素重复以上的步骤,除了最后一个
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较

冒泡排序的实现

def bubble_sort(alist):
    """冒泡排序"""
    n = len(alist)
    for i in range(0, n - 1):
        # 外层控制将所有元素替换完
        count = 0
        for j in range(0, n - 1 - i):
            # 内层控制单对元素的交换
            if alist[j] > alist[j + 1]:
                alist[j], alist[j + 1] = alist[j + 1], alist[j]
                count += 1
        if count == 0:
            return


if __name__ == "__main__":
    li = [123, 4, 54, 34, 54, 23, 655]
    print(li)
    bubble_sort(li)
    print(li)

2.选择排序

定义

选择排序(Selection sort)是一种简单直观的排序算法.
原理

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置(结束位置),然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕
优点

选择排序的主要优点与数据移动有关,如果某个元素位于正确的最终位置上,则它不会被移动.选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换.

在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种

选择排序的实现

def select_sort(alist):
    """选择排序"""
    n = len(alist)
    for j in range(0, n-1):
        min_index = j
        for i in range(j+1, n):
            if alist[min_index] > alist[i]:
                min_index = i
        alist[j], alist[min_index] = alist[min_index], alist[j]

if __name__ == "__main__":
    li = [123, 4, 54, 34, 54, 23, 655]
    print(li)
    select_sort(li)
    print(li)

3.插入排序

定义

插入排序(Insertion Sort)是一种简单直观的排序算法
原理

通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.

插入排序在实现上,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为新元素提供插入空间

插入排序实现

def insert_sort(alist: list):
    """插入排序"""
    n = len(alist)
    for i in range(1, n):
        j = i
        while j > 0:
            if alist[j] < alist[j - 1]:
                alist[j], alist[j - 1] = alist[j - 1], alist[j]
                j -= 1
            else:
                break


if __name__ == "__main__":
    li = [123, 4, 54, 34, 54, 23, 655]
    print(li)
    insert_sort(li)
    print(li)

4.快速排序

定义

快速排序(Quicksort),又称划分交换排序(partition-exchange sort), 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列.
步骤
1. 从数列中挑出一个元素,称为‘基准’(pivot)
2. 重新排序数列,所有元素比基准小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以放到任一边).在这个分区结束之后,该基准就处于数列的中间位置.这个称为分区(partition)操作
3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序

递归的最底层情形,是数列的大小是零或一,也就是永远都已经被排序好了,虽然一直递归下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去.

快速排序实现

def quick_sort(alist, first, last):
    """快速排序"""
    if first == last:
        return
    n = len(alist)
    mid_value = alist[first]
    low = first
    high = last
    while low < high:
        # 让high左移
        while low < high and alist[high] >= mid_value:
            high -= 1
        alist[low] = alist[high]
        # 让low右移
        while low < high and alist[low] < mid_value:
            low += 1
        alist[high] = alist[low]
    # 从循环退出时，low=high
    alist[low] = mid_value
    # 对low左边的列表执行快速排序
    quick_sort(alist, first, low)
    # 对low右边的列表执行快速排序
    quick_sort(alist, low+1, last)

    
if __name__ == "__main__":
    li = [123, 4, 54, 34, 54, 23, 655]
    print(li)
    quick_sort(li, 0, len(li)-1)
    print(li)

5.希尔排序

定义

希尔排序(shell sort)是插入排序的一种,也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本.

希尔排序是非稳定排序算法.

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止.
希尔排序过程
- 将数组列在一个表中并对列分别进行插入排序,重复这一过程
- 不过每次用更长的列(步长更长了,列数更少了)来进行
- 最后整个表就只有一列
将数组转换至表是为了更好地理解这算法,算法本身还是使用数组进行排序

希尔排序的实现

def shell_sort(alist):
    """希尔排序"""
    n = len(alist)
    gap = n // 2
    # gap变化到0之前，插入算法执行的次数
    while gap > 0:
        # 插入算法，与普通的插入算法的区别就是gap步长
        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__":
    li = [123, 4, 54, 34, 54, 23, 655]
    print(li)
    shell_sort(li)
    print(li)

6.归并排序

定义

归并排序是采用分治法的一个非常典型的应用.

归并排序的思想就是先递归分解数组,再合并数组.
思路

将数组分解最小之后,然后合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位.然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可.

归并排序实现

def merge_sort(alist):
    """归并排序"""
    n = len(alist)
    if n <= 1:
        return alist
    mid = n // 2
    # left，right采用归并排序后形成的新的列表
    left_ = merge_sort(alist[:mid])
    right_ = merge_sort(alist[mid:])

    # 将两个有序的序列，合并成一个整体
    left_pointer, right_pointer = 0, 0
    result = []
    while left_pointer < len(left_) and right_pointer < len(right_):
        if left_[left_pointer] <= right_[right_pointer]:
            result.append(left_[left_pointer])
            left_pointer += 1
        else:
            result.append(right_[right_pointer])
            right_pointer += 1
    result += left_[left_pointer:]
    result += right_[right_pointer:]
    return result

if __name__ == "__main__":
    li = [123, 4, 54, 34, 54, 23, 655]
    print(li)
    sorted_ = merge_sort(li)
    print(sorted_)

7.常见排序算法效率比较

8.搜索

搜索是在一个项目集合中找到一个特定项目的算法过程.

搜索通常的答案是真的或假的.

搜索的几种常见方法:顺序查找、二分法查找、二叉树查找、哈希查找

二分查找

定义

二分查找又称为折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难.

折半查找方式适用于不经常变动而查找频繁的有序列表.
原理

假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一字表,否则进一步查找后一子表.重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功.
图解

二分查找的实现

def binary_search(alist, item):
    """二分查找,递归版本"""
    n = len(alist)
    if n > 0:
        mid = n//2
        if alist[mid] == item:
            return True
        elif item < alist[mid]:
            return binary_search(alist[:mid], item)
        else:
            return binary_search(alist[mid+1:], item)
    return False

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 item > alist[mid]:
            first = mid+1
    return False


if __name__ == "__main__":
    li = [123, 4, 54, 34, 54, 23, 655]
    print(li)
    print(binary_search(li, 5))

六、树与树算法

1.树的概念

树(tree)是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合.

它是由n(n>=1)个有限节点组成一个具有层次关系的集合.把它叫做‘树’是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的.

树具有的特点:

1.每个节点有零个或多个子节点

2.没有父节点的节点称为根节点

3.每一个非根节点有且只有一个父节点

4.除了根节点外,每个子节点可以分为多个不相交的子树

2.树的术语

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

3.树的种类

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

4.树的存储与表示

顺序存储:将数据结构存储在固定的数组中,在遍历速度上有一定的优势,但因所占空间比较大,是非主流二叉树,二叉树通常以链式存储
链式存储

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

5.常见的一些树的应用场景

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

6.二叉树

二叉树的基本概念

二叉树是每个节点最多有两个子树的树结构,通常子树被称作‘左子树’(left subtree)和‘右子树’(right subtree)
二叉树的性质(特性)
- 性质1:在二叉树的第i层上至多有2**(i-1)个节点(i>0)
- 性质2:深度为k的二叉树至多有2**k-1个节点(k>0)
- 性质3:对于任意一棵二叉树,如果其叶节点树为N0,而度数为2的节点总数为N2,则N0=N2+1
- 性质4:具有n个节点的完全二叉树的深度必为log2(n+1)
- 性质5:对完全二叉树,若从上至下,从左至右编号,则编号为i的节点,其左孩子编号必为2i,其右孩子编号必为2i+1,其双亲的编号必为i/2(i=1时为根,除外)

二叉树的实现

class Node(object):

    def __init__(self, item):
        self.elem = item
        self.lchild = None
        self.rchild = None


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

    def add(self, item):
        node = Node(item)
        if self.root is None:
            self.root = node
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild = node
                return
            else:
                queue.append(cur_node.lchild)
            if cur_node.rchild is None:
                cur_node.rchild = Node
                return
            else:
                queue.append(cur_node.rchild)

广度优先遍历

class Node(object):

    def __init__(self, item):
        self.elem = item
        self.lchild = None
        self.rchild = None


class Tree(object):
    """二叉树"""

    def __init__(self):
        self.root = None

    def add(self, item):
        node = Node(item)
        if self.root is None:
            self.root = node
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild = node
                return
            else:
                queue.append(cur_node.lchild)
            if cur_node.rchild is None:
                cur_node.rchild = Node
                return
            else:
                queue.append(cur_node.rchild)

    def breadth_travel(self):
        """广度遍历"""
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            print(cur_node.elem)  # 打印当前节点的元素
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)


if __name__ == "__main__":
    tree = Tree()
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.breadth_travel()

深度优先遍历

对于一颗二叉树,深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点,尽可能深的搜索树的分支.

深度遍历有三种方法,这三种方法常被用于访问树的节点,它们之间的不同在于访问每个节点的次序不同:
- 先序遍历(preorder)
  
  在先序遍历中,先访问根节点,然后递归使用先序遍历访问左子树,再递归使用先序遍历访问右子树
  
  根节点->左子树->右子树
```
def preorder(self,root):
    """递归实现先序遍历"""
    if root is None:
        return
    print(root.elem)
    self.preorder(root.lchild)
    self.proorder(root.rchild)
```
- 中序遍历(inorder)
  
  在中序遍历中,递归使用中序遍历访问左子树,然后访问根节点,最后再递归使用中序遍历访问右子树
  
  左子树->根节点->右子树
```
def inorder(self, root):
    """递归实现中序遍历"""
    if root is None:
        return
    self.inorder(root.lchild)
	print(root.elem)
    self.inorder(root.rchild)
```
- 后序遍历(postorder)
  
  在后序遍历中,先递归使用后序遍历访问左子树和右子树,最后访问根节点
  
  左子树->右子树->根节点
```
def postorder(self, root):
    """递归实现后序遍历"""
    if root is None:
        return
    self.postorder(root.lchild)
    self.postorder(root.rchild)
    print(root.elem)
```
图解