1、尝试

先来看一道题：

如果 a+b+c = 1000, 且 a^2 + b^2= c^2 (a,b,c为自然数)，如何求出 a、b、c可能的合并？

一般采取最原始的方法（枚举法），将 a、b、c分别从0~1000取值，再逐一匹配。

import time
start_time = time.time()
for a in range(1001):
    for b in range(10001):
        for c in range(1001):
            if a+b+c == 1000 and a**2+b**2 == c**2:
                print('a, b, c:%d, %d, %d', a, b, c)
end_time = time.time()
print("times:%d", end_time-start_time)

输出结果：

a, b, c:0, 500, 500
a, b, c:200, 375, 425
a, b, c:375, 200, 425
a, b, c:500, 0, 500
times:1102

可以看到花费了 1102 s ，消耗的时间是非常长的，并且在这期间非常的消耗cpu（ps：笔记本估计风扇都会转。）但是他其实是一个很简单的计算，完全没有必要去耗费这些来计算他。因此，引入了算法。

2、算法的提出

1、算法的概念

算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后调用。

算法是独立存在的一种解决问题的方法和思想。

对于算法而言，实现的语言不重要，重要的是思想。
本系列以python为例进行说明。

2、算法的五大特性

1. 输入：算法具有0个或多个输入
2. 输出：算法至少有一个或多个输出
3. 有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一步骤可以在可接受的时间内完成
4. 确定性：算法中的每一步都有确定的含义，不会出现二义性
5. 可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成

3、改进

我们稍微改进下上面的例子：

start_time = time.time()
for a in range(1001):
    for b in range(10001):
        # 省去了对于c的循环遍历以及 a+b+c=1000的判断
        c = 1000 - a -b
        if a**2+b**2 == c**2:
            print('a, b, c:%d, %d, %d'% (a, b, c))
end_time = time.time()

print("times:%d"% (end_time-start_time))

运行结果：

a, b, c:0, 500, 500
a, b, c:200, 375, 425
a, b, c:375, 200, 425
a, b, c:500, 0, 500
times:7

可以看到消耗时间已经极大地有了缩短。

4、算法效率衡量

1、执行时间反应算法效率

对于同一个问题，我们给出了两种解决算法，在两种算法的实现中，我对于程序的执行的时间进行了测算，发现两段程序执行的时间相差悬殊（1102秒相比于7秒），由此我们可以得出结论：实现算法程序的执行时间可以反应出算法的效率，即算法的优劣。

2、单靠时间值绝对可信吗？

假设我们将第二种尝试的算法程序运行在一天配置古老、性能低下的计算机中，情况会如何？很可能运行的时间并不会比我们的电脑中运行算法一的 1102 秒快多少。

单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的。

程序的运行离不开计算机环境（包括硬件和操作系统），这些客观原因会影响程序运行的速度病反应程序的执行时间上。那么如何才能客观评判一个算法的优劣呢？

3、时间复杂度与“大O记法”

我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位，那么有多少个基本操作就代表会话费多少时间单位。算法对于不同的机器环境而言，确切的单位时间是不同的，但对于算法进行多少个基本操作（即话费多少单位时间）在规模数量级上确实相同的，由此可以忽略机器环境的影响而客观的反应算法的时间效率。

对于算法的时间效率，我们采用 “大O记法”来表示。

**“大O记法”：对于单调的整数函数f，如果存在一个整数g和实常熟c>0，使得对于充分大的n总有f(n) <= cg(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)

4、如何理解“大O记法”

对于算法进行特别具体的细致分析虽然很好，但在时间中的实际价值有限。对于算法的时间性质和空间性质，最重要的是其数量级和趋势，这些是分析算法效率的主要部分。而计量算法基本操作数量的规模函数中那些常量因子可以忽略不记。例如，可以认为 3n 和 100n 属于同一量级，如果两个算法处理同样规模实例的代价分别为这两个函数，就认为他们的效率“差不多”， 都是 n级。

5、最坏时间复杂度

分析算法时，存在几种可能的考虑：

1. 算法完成工作最少需要多少基本操作，即 最优时间复杂度
2. 算法完成工作最多需要多少基本操作，即 最坏时间复杂度
3. 算法完成工作平均需要多少基本操作，即 平均时间复杂度

6、时间复杂度的几条基本计算规则

1. 基本操作：即只有常数项，认为其时间复杂度为 O(1)
2. 顺序结构：时间复杂度按加法进行计算
3. 循环结构：时间复杂度按乘法进行计算
4. 分支结构：时间复杂度取最大值
5. 判断一个算法的效率时，旺旺只需要关注操作数量的最高次项，其他次要项和常数项可以忽略
6. 在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度

5、算法分析

那么我们来分析一下前面所用到的两种算法的时间复杂度
1、第一次：

for a in range(1001):
    for b in range(10001):
        for c in range(1001):
            if a+b+c == 1000 and a**2+b**2 == c**2:
                print('a, b, c:%d, %d, %d'% (a, b, c))

时间复杂度： T(n) = O(n_n_n) = O(n)

2、第二次：

for a in range(1001):
    for b in range(10001):
        c = 1000 - a -b
        if a**2+b**2 == c**2:
            print('a, b, c:%d, %d, %d'% (a, b, c))

时间复杂度： T(n) = O(nn(1+1)) = O(n*n) = O(n)

6、常见时间复杂度

注意：经常将logn（以2为底的对数）简写为 log n

常见时间复杂度之间的关系

所消耗的时间从小到大：

7、Python内置类型性能分析

1、timeit模块：

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

class timeit.Timer(stmt = 'pass', setup = 'pass', timer = <timer function>)

• Timer 是测量小段代码执行速度的类
• stmt 参数是要测试的代码语句
• setup 参数是运行代码时需要的设置
• timer 参数是一个定时器函数

timeit.Timer.timeit(number=1000000)

Timer类中测试语句执行速度的对象方法。number参数是测试代码时的测试次数，默认为 1000000 次。方法返回执行代码的平均耗时，一个 float 类型的秒数。
实例：
我们这里计算python的列表的各种操作的次数来演示这个函数的用法。

from timeit import Timer


def test1():
    li = []
    for i in range(10000):
        li.append(i)

def test2():
    li = []
    for i in range(10000):
        li += [i]

def test3():
    li = [i for i in range(10000)]

def test4():
    li = list(range(10000))

def test5():
    li = []
    for i in range(10000):
        li.extend([i])


t1 = Timer('test1()', 'from __main__ import test1')
print('append' ,t1.timeit(number=1000), "seconds")
t2 = Timer('test2()', 'from __main__ import test2')
print('+' ,t2.timeit(number=1000), "seconds")
t3 = Timer('test3()', 'from __main__ import test3')
print('[i for i in range(1000)]' ,t3.timeit(number=1000), "seconds")
t4 = Timer('test4()', 'from __main__ import test4')
print('list' ,t4.timeit(number=1000), "seconds")
t5 = Timer('test5()', 'from __main__ import test5')
print('extend' ,t5.timeit(number=1000), "seconds")

输出结果：

append 0.6194634630010114 seconds
+ 0.6978286960002151 seconds
[i for i in range(1000)] 0.3362328119983431 seconds
list 0.2075852699999814 seconds
extend 0.8540526190045057 seconds

我们可以清楚地看出每个程序运行1000次所消耗的时间

2、list内置操作的时间复杂度

3、dict内置操作的时间复杂度

8、数据结构

1、概念

数据是一个抽象的概念，将其进行分类后得到程序设计语言中的基本类型，如：int、float、char等。数据元素之间不是独立的，存在特定的关系，这些关系便是结构。数据结构指数据对象那个中数据元素之间的关系。

python给我们提供了很多现成的数据结构类型，这些系统自己定义好的，不需要我们自己去定义的数据结构叫做 python的内置数据结构，比如列表、元祖、字典。而有些数据组织方式，python 系统里面没有直接定义，需要我们自己去定义实现这些数据的组织方式，这些数据组织方式成为 python的扩展数据结构，比如栈、队列等。

2、算法与数据结构的区别

数据结构只是静态的描述了数据元素之间的关系。
高效的程序需要在数据结构的基础上设计和选择算法。
程序 = 数据结构 + 算法

总结：算法是为了解决实际问题而设计的，数据结构是算法需要处理的问题载体

3、抽象数据类型（Abstract Data Type）

数据抽象类型（ADT）的含义是指一个数据模型以及定义在此数学模型上的一组操作。即把数据类型和数据类型上的运算捆在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上的运算的实现与这些数据类型和运算在程序中的引用隔开，使他们相互独立。
五种最常用的数据运算：

• 插入
• 删除
• 修改
• 查找
• 排序

二、线性表（顺序表、链表）

在程序中，经常需要将一组（通常是同为某个类型的）数据元素作为整体管理和使用，需要创建这种元素组，用变量记录他们传进传出函数等。一组数据中包含的元素个数可能发生变化。

对于这种需求，最简单的解决方案就是将这样一组元素看成一个序列，用元素在序列里的位置和顺序，表示实际应用中的某种有意义的信息，或者表示数据之间的某种关系。

这样的一组序列元素的组织形式，我们可以将其抽象为线性表。一个线性表是某类元素的一个集合，还记录这元素之间的一种顺序关系。线性表是最基本的数据结构之一，在实际程序中应用非常广泛，他经常被用作更复杂的数据结构的实现基础。

根据线性表的实际存储方式，分为两种实现模型：

• 顺序表：将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由他们的存储顺序自然表示。
• 链表：将元素存放在通过链接构造起来的一系列存储块中。

三、顺序表

1、顺序表的基本表现形式

图(a)表示的是顺序表的基本形式，数据元素本身连续存储，每个元素所占的存储单元大小固定相同，元素的下标是其逻辑地址，而元素存储的物理地址（实际内存地址）可以通过存储区的起始地址Loc(e)加上逻辑地址（第i个元素）与存储单元大小（c）的乘积计算而得，即：

**Loc(e) = Loc(e) + ci

故，访问指定元素时无需从头便利，通过计算便可获得对应地址，其时间复杂度为 O(1)。

如果元素的大小不同意，则需采用图(b)的元素外置的形式，将实际数据元素另行存储，而顺序表中个单元位置保存对应元素的地址信息（即链接）。由于每个链接所需的存储量相同，通过上述公式，可以计算出元素链接的存储位置，而后顺着链接找到实际存储的数据元素。
注意：图(b)中的c不再是数据元素的大小，而是存储一个链接地址所需的存储量，这个量通常很小。

图(b)这样的顺序表也被称为对实际数据的索引，这是最简单的索引结构。

2、顺序表的结构与实现

①顺序表的结构

一个顺序表的完整信息包括两部分，一部分是表中的元素集合，另一部分是为海鲜正确操作而需记录的信息，即有关表的整体情况，这部分信息主要包括元素存储区的容量和当前表中已有的元素个数两项。

②顺序表的两种基本实现方式

图(a)为一体式结构，存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。
一体式结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。

图(b)为分离式结构，表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。

③元素存储区替换

一体式结构由于顺序表信息区与数据区连续存储在一起，所以若想更换数据区，则只能整体搬迁，即整个顺序表对象（指存储顺序表的结构信息的区域）改变了。

分离式结构若想更换数据区，只需将表信息区中的数据区链接地址更新即可，而该顺序表对象不变。

④元素存储区的扩充

采用分离式结构的顺序表，若将数据区更换为存储空间更大的区域，则可以在不改变表对象的前提下对其数据存储区进行扩充，所有使用这个表的地方都不必修改。只要程序的运行环境（计算机系统）还有空闲存储。这种表结构就不会因为满了而导致操作无法进行。人们把采用这种技术实现的顺序表成为动态顺序表，因为其容量可以在使用中动态变化。

扩充的两种策略：

• 每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略可称为 线性增长
  特点：节省空间，但是扩充操作频繁，操作次数多。
• 每次扩充容量加倍，如每次扩充增加一倍存储空间。
  特点：减少了扩充操作的执行次数，但可能会浪费空间资源。以空间换时间（推荐的方式）

3、顺序表的操作

①增加元素

a、尾端加入元素，时间复杂度为 O(1)
b、非保序的加入元素（不常见），时间复杂度为 O(1)
c、保序的元素加入，时间复杂度为 O(n)

②删除元素

a、尾端加入元素，时间复杂度为 O(1)
b、非保序的加入元素（不常见），时间复杂度为 O(1)
c、保序的元素加入，时间复杂度为 O(n)

3、python中的顺序表

python中的 list 和 tuple 两种类型采用了顺序表的实现技术。

tuple 是不可变类型，即不变的顺序表，因此不支持改变其内部状态的任何操作，而其他方面，则与list的性质类型类似。

①list的基本实现技术

python标准类型 list 就是一种元素个数可变的线性表，可以加入和删除元素，并且在各种操作中维持已有元素的顺序（即保序），而且还具有以下特征：

1.元素有位置下标，以索引就可以直接取到元素 —> 连续的存储空间，以偏移量计算取得元素，不必遍历所有元素，时间复杂度为O(1)，顺序表

2.元素无论如何改变，表对象不变，也就是其id不变 —> 分离式结构，表头和元素内容分开储存，这样在更改list时，表对象始终是同一个，只是其指向的地址不同

3.元素可以是任意类型 —> 既要要求是连续存储，又可以存储不同类型的数据，那么其用的就是元素外置的方式，存储的只是地址的引用

4.可以任意添加新元素 —> 要能不断地添加新元素，其使用了动态扩充的策略

在python的官方实现中， list 就是一种采用分离式技术实现的元素外置的动态顺序表 。这就是为什么用 list.append(x)（或者 list.insert(len(list), x)）比在指定位置插入元素效率高的原因。

在python的官方实现中，list实现采用了如下策略：在建立空表（很小的表）时，系统分配一块能容纳8个元素的存储区；在执行插入操作（insert或append）时，如果元素存储区满就换一块4倍大的存储区。但如果此时的表已经很大（目前的阈值为 50000），则改变策略，采用加一倍的方法。引入这种改变策略的方法，是为了避免出现过多空闲的存储位置。

四、链表

链表引入：

为什么需要链表？

顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来并不是很灵活。

链表的定义

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

1、单项链表

单向链表也叫单链表，是链表中最简单的一种形式，他的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。

• 表元素域elem用来存放具体的数据
• 链接域next用来存放下一个节点的位置（python中的标识）
• 变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点。

节点和单链表的实现

操作：

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

# 构造节点
class Node():
    def __init__(self, elem):
        self.elem = elem
        self.next = None


# 构造链表
class SingleLinkList():
    # 初始化链表（默认为空链表）
    def __init__(self, node=None):
        self.__head = node

    def is_empty(self):
        """链表是否为空"""
        return self.__head == None

    def length(self):
        """链表的长度"""
        # cur游标，用来移动遍历节点
        cur = self.__head
        # 记录数量
        count = 0
        while cur != None:
            count += 1
            # 将游标赋给下一个
            cur = cur.next
        return count

    def travel(self):
        """遍历整个链表"""
        cur = self.__head
        while cur != None:
            # 打印游标指向的节点
            print(cur.elem, end=" ")
            cur = cur.next
        print("")

    def add(self, item):
        """链表头部增加元素"""
        node = Node(item)
        # 先将新节点的next区域指向第一个节点的值
        node.next = self.__head
        # 再将__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 != None:
                # 移动游标，当下一个为None，退出循环，当前的cur为最后一个节点
                cur = cur.next
            cur.next = node

    def insert(self,pos, item):
        """指定位置插入元素
        :param pos 从0开始
        """
        # 空链表
        if pos <= 0:
            self.add(item)
        # 插入值的位置大于链表长度-1，证明在链表末尾
        elif pos > (self.length()-1):
            self.append(item)
        else:
            pre = self.__head
            count =0
            # 当循环的次数小于插入指定位置的参数-1，那么当前为要插入位置的前一个位置
            while count < (pos-1):
                count += 1
                pre = pre.next
            node = Node(item)
            # 将目标数的next区域指向下一个的值
            node.next = pre.next
            # 将前一个位置的next指向插入值
            pre.next = node

    def remove(self, item):
        """删除节点"""
        cur = self.__head
        # 被删除元素位置的前一个节点
        pre = None
        while cur != None:
            if cur.elem == item:
                # 判断此节点是否为头节点
                if cur == self.__head:
                    self.__head = cur.next
                else:
                    # 将前一个的next指向当前游标的next的指向（即下一个值）
                    pre.next = cur.next
                break
            else:
                pre = cur
                cur = cur.next

    def search(self, item):
        """查找节点是否存在"""
        cur = self.__head
        while cur != 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(1)

    print(ll.is_empty())
    print(ll.length())

    ll.add(8)
    ll.append(2)
    ll.append(3)
    ll.append(4)
    ll.travel()

    ll.insert(7, 10)
    ll.travel()

    ll.remove(1)
    ll.travel()

运行结果：

True
0
False
1
8 1 2 3 4 
8 1 2 3 4 10 
8 2 3 4 10

链表与顺序表的对比

链表失去了顺序表随机读取的优点，同时链表由于增加了节点的指针域，空间开销比较大，但对存储空间的使用要相对灵活。

链表与顺序表的各种操作复杂度如下：

注意：虽然表面看起来复杂度都是 O(n)，但是链表和顺序表在插入和删除时都进行的是完全不同的操作，链表的主要耗时操作是遍历查找，删除和掺入操作本身的复杂度是 O(1)。顺序表查找很快，主要耗时的操作是拷贝覆盖。因为除了目标元素在尾部的特殊情况，顺序表进行插入和删除时需要对操作点之后的所有元素进行前后移位操作，只能通过拷贝和覆盖的方法进行。

2、双向链表

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当次节点为第一个节点时，指向空值；而另一个指向下一个节点，当次节点为最后一个节点时，指向空值。

节点和双链表的实现

操作：

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

# 构造节点
class Node():
    def __init__(self, elem):
        self.elem = elem
        # 前驱节点
        self.prev = None
        # 后继节点
        self.next = None


# 构造链表
class SingleLinkList():
    # 初始化链表（默认为空链表）
    def __init__(self, node=None):
        self.__head = node

    def is_empty(self):
        """链表是否为空"""
        return self.__head == None

    def length(self):
        """链表的长度"""
        # cur游标，用来移动遍历节点
        cur = self.__head
        # 记录数量
        count = 0
        while cur != None:
            count += 1
            # 将游标赋给下一个
            cur = cur.next
        return count

    def travel(self):
        """遍历整个链表"""
        cur = self.__head
        while cur != None:
            # 打印游标指向的节点
            print(cur.elem, end=" ")
            cur = cur.next
        print("")

    def add(self, item):
        """链表头部增加元素"""
        node = Node(item)
        # 先将新节点的next区域指向第一个节点的值
        node.next = self.__head
        # 再将__head指向新节点
        self.__head = node
        # 将第一个节点(node.next)的prev指向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 != None:
                # 移动游标，当下一个为None，退出循环，当前的cur为最后一个节点
                cur = cur.next
            cur.next = node
            node.prev = cur

    def insert(self,pos, item):
        """指定位置插入元素
        :param pos 从0开始
        """
        # 空链表
        if pos <= 0:
            self.add(item)
        # 插入值的位置大于链表长度-1，证明在链表末尾
        elif pos > (self.length()-1):
            self.append(item)
        else:
            cur = self.__head
            count = 0
            while count < pos:
                count += 1
                cur = cur.next
            # 当循环退出时，cur指向pos位置
            node = Node(item)
            # node的next指向cur所在位置，即插入值的下一个值
            node.next = cur
            # node的prev指向node的前一个值
            node.prev = cur.prev
            # node的前一个值的next指向node
            cur.prev.next = node
            # 插入值的下一个值的prev指向node
            cur.prev = node

    def remove(self, item):
        """删除节点"""
        cur = self.__head
        # 被删除元素位置的前一个节点
        pre = None
        while cur != None:
            if cur.elem == item:
                # 判断此节点是否为头节点
                if cur == self.__head:
                    self.__head = cur.next
                    # 如果头节点不是None
                    if cur.next:
                        # 判断该链表是否只有一个节点
                        cur.next.prev = None
                else:
                    # 目标值的前一个节点的next指向后一个节点
                    cur.prev.next = cur.next
                    if cur.next:
                        # 目标值的后一个节点的prev指向前一个节点
                        cur.next.prev = cur.prev
                break
            else:
                cur = cur.next

    def search(self, item):
        """查找节点是否存在"""
        cur = self.__head
        while cur != 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(1)

    print(ll.is_empty())
    print(ll.length())

    ll.add(8)
    ll.append(2)
    ll.append(3)
    ll.append(4)
    ll.travel()

    ll.insert(7, 10)
    ll.travel()

    ll.remove(1)
    ll.travel()

运行结果：

True
0
False
1
8 1 2 3 4 
8 1 2 3 4 10 
8 2 3 4 10

3、单向循环链表

单链表的一个变形是单项循环链表，链表最后一个节点的next域不再为 None ，而是指向链表的头节点。

节点和单项循环列表的实现

操作：

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

# 构造节点
class Node():
    def __init__(self, elem):
        self.elem = elem
        self.next = None


# 构造链表
class SingleLinkList():
    # 初始化链表（默认为空链表）
    def __init__(self, node=None):
        self.__head = node
        # 如果是只有一个节点，需要next区域指向他自身
        if node:
            node.next = node

    def is_empty(self):
        """链表是否为空"""
        return self.__head == None

    def length(self):
        """链表的长度"""
        if self.is_empty():
            return 0
        # cur游标，用来移动遍历节点
        cur = self.__head
        # 记录数量
        count = 1
        while cur.next != self.__head:
            count += 1
            # 将游标赋给下一个
            cur = cur.next
        return count

    def travel(self):
        """遍历整个链表"""
        cur = self.__head
        if self.is_empty():
            return
        while cur.next != self.__head:
            # 打印游标指向的节点
            print(cur.elem, end=" ")
            cur = cur.next
        # 退出循环， cur指向尾节点，但尾节点没有打印
        print(cur.elem)

    def add(self, item):
        """链表头部增加元素"""
        node = Node(item)
        if self.is_empty():
            # 空链表，头部指向node
            self.__head = node
            # next区域指向自身
            node.next = node
        else:
            cur = self.__head
            while cur.next != self.__head:
                cur = cur.next
            # 退出循环，cur指向尾节点
            # node的next指向下一个值
            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
            node.next = self.__head
            cur.next = node


    def insert(self,pos, item):
        """指定位置插入元素
        :param pos 从0开始
        """
        # 空链表
        if pos <= 0:
            self.add(item)
        # 插入值的位置大于链表长度-1，证明在链表末尾
        elif pos > (self.length()-1):
            self.append(item)
        else:
            pre = self.__head
            count =0
            # 当循环的次数小于插入指定位置的参数-1，那么当前为要插入位置的前一个位置
            while count < (pos-1):
                count += 1
                pre = pre.next
            node = Node(item)
            # 将目标数的next区域指向下一个的值
            node.next = pre.next
            # 将前一个位置的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:
                    # 将前一个的next指向当前游标的next的指向（即下一个值）
                    pre.next = cur.next
                return
            else:
                pre = cur
                cur = cur.next
        # 退出循环，cur指向尾节点
        if cur.elem == item:
            pre.next = cur.next

    def search(self, item):
        """查找节点是否存在"""
        if self.is_empty():
            return False
        cur = self.__head
        while cur != 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(1)

    print(ll.is_empty())
    print(ll.length())

    ll.add(8)
    ll.append(2)
    ll.append(3)
    ll.append(4)
    ll.travel()

    ll.insert(7, 10)
    ll.travel()

    ll.remove(1)
    ll.travel()

运行结果：

True
0
False
1
8 1 2 3 4
8 1 2 3 4 10
8 2 3 4 10

五、栈和队列

1、栈

栈（stack），有些地方成为堆栈，是一种容器，可存入数据元素，访问元素，删除元素，他的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（top）和输出数据（pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。

由于栈数据结构只允许在一端就行操作，因而按照后进先出（LIFO，Last In First Out）的原理运作。

栈结构的实现

• push(item)（入栈）
• pop()（出栈）
• peek()（返回栈顶元素）
• is_empty()（判断栈是否为空）
• size()（返回栈元素个数）

class Stack():
    """栈"""
    # 新定义一个私有列表作为容器
    def __init__(self):
        self.__list = []

    # 由于尾部插入的时间复杂度为O(1)，头部为O(n)，所以在尾部插入
    def push(self, item):
        """添加一个新的元素到栈顶"""
        self.__list.append(item)

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

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

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

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


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

运行结果：

True
3
2
1

2、队列

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是 q=(a1, a2, ……. , an )，那么a1就是对头元素，而an是队尾元素。这样我们就可以在删除时，总是从a1开始，而插入时，总在队列最后，这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的排在队伍最后。

队列结构的实现

class Queue():
    """队列"""
    def __init__(self):
        self.__list = []

# 由于队列是先进先出，所以实际操作中，需要考虑进的多，还是出的多。
# 根据这个，来选择针对列表的插入和查询的时间复杂度
    def enqueue(self, item):
        """往队列尾部中插入一个元素"""
        self.__list.append(item)

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

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

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


if __name__ == '__main__':
    s = Queue()
    s.enqueue(1)
    s.enqueue(2)
    s.enqueue(3)
    print(s.dequeue())
    print(s.dequeue())
    print(s.dequeue())

运行结果：

1
2
3

3、双端队列

双端队列（deque，全名 double-ended queue），是一种具有队列和栈的性质的数据结构。

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

双队列结构的实现

class Deque():
    """双端队列"""
    def __init__(self):
        self.__list = []

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

    def add_rear(self, 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)


if __name__ == '__main__':
    s = Deque()
    s.add_front(1)
    s.add_front(2)
    s.add_front(3)
    print(s.pop_front())
    print(s.pop_front())
    print(s.pop_front())

运行结果：

3
2
1

六、冒泡排序及实现

1、冒泡排序

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

冒泡排序算法的运作如下：

• 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 针对所有的元素，重复以上步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

交换过程示意图（第一次）：

那么我们需要进行 n-1次冒泡过程，每次对应的比较次数如下图所示：

2、python实现

def bubble_sort(alist):
    n = len(alist)
    # 控制走多少次
    for j in range(0, n- 1):
        count = 0
        # 控制从头走到尾的距离
        for i in range(0, n - 1 - j):
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
                count += 1
        if 0 == count:
            return

解读：外层for循环控制将整个列表排序出来需要循环多少次，里层for循环控制每次循环交换两个数值的次数，也就是交换几次数值。因为，每循环一次里层的for循环都会因为已经排序过的数值不再需要排序，而降低了交换数值的次数。
由于存在一个最优解（当前目标列表已经为排序好的，即不再需要排序），那么在进入一次循环后，即可确认该列表已经排序好了，这里使用 count 作为标记。当第一次进入外层循环后开始执行内层循环，内层走过 n-1 次数值交换后，让 count 自增一次。但是由于此时列表已经排序好了，所以if的判断条件不成立，因此count不会自增。直接退出循环。

3、时间复杂度

• 最优时间复杂度：O(n)
  （表示遍历一次返现没有任何可以交换的元素，排序结束）
• 最坏时间复杂度：O(n)
  （表示两次for循环全部执行，一个for循环为n）
• 稳定性：稳定

4、冒泡排序的演示

七、选择排序及实现

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

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则他不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n 个元素的表进行排序总共进行至多 n-1 次交换。在所有的完全依靠交换区移动元素的排序方法中，选择排序属于非常好的一种。

1、选择排序分析

排序过程

2、python代码实现

"""选择排序"""
def select_sort(alist):
    n = len(alist)
    # 需要进行 n-1 次操作
    for j in range(0, n-1):
        # 记录最小的位置
        min_index = j
        # 从 j+1 到末尾，选出最小的数字
        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]

解读：外层循环控制循环次数（n-1）次，当最开始为0时，即 min_index（最小的位置），进入内层循环，循环范围为（j+1, n），因为每次进行对比后，将最小的数字放在最前面，那就意味着，前面排好序的数字不再需要进行比较。当最小的索引对应的数字大于遍历数组时的某一个索引（i）对应的数字，那么就将 min_index = i ，这样对比一次完整的数组，然后当前的 min_indx 即为最小值对应的索引值，将 j（0 ~ n-1） 的索引值与最小的的进行交换。这样，就将最小的值放到了最前面。以此继续执行外层循环。

3、时间复杂度

• 最优时间复杂度：O(n)
• 最坏时间复杂度：O(n)
• 稳定性：不稳定（考虑升序每次选择最大的情况）

4、选择排序演示

八、插入排序与实现

插入排序（Insertion Sort）是一种简单直观的排序算法。他的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

1、插入排序分析

2、python代码实现

"""插入排序"""
def insert_sort(alist):
    n = len(alist)
    # 从第二个位置开始，即下标0，到n-1
    for i in range(1, n):
        # i, i-1, i-2 ,..., 1
        for j in range(i, 0, -1):
            if alist[j] < alist[j-1]:
                alist[j-1], alist[j] = alist[j], alist[j-1]
            # 最优解，即 目标列表已经排好序
            else:
                break

解读：外层循环的范围为 从第二个数值到倒数第二个数值，内从循环的范围为 i, i-1, i -2, …, 1 ，当进入第一次循环时，将第二个位置上的数字与第一个位置进行比较，如果小于，将两者进行交换。当进入第二次循环时，第一个位置为已经排好序的数值，所以外层循环从第三个位置开始，内层循环 与前面排好序的数值挨个对比，然后插入到排好序的列表中正确的位置。

之前面试的时候，被要求使用一个for循环来完成对于列表的排序，所以在这提供另一种写法。

"""插入排序"""
def insert_sort(alist):
  n = len(alist)
  # 从第二个位置开始，即下标0，到n-1
  for i in range(1, n):
      # i, i-1, i-2 ,..., 1
      j = i
      while j > 0:
          if alist[j] < alist[j-1]:
              alist[j-1], alist[j] = alist[j], alist[j-1]
              j -= 1
          # 最优解，即 目标列表已经排好序
          else:
              break


l = [22, 44, 11, 22, 3, 14, 20]
print(l)
insert_sort(l)
print(l)

3、时间复杂度

• 最优时间复杂度：O(n) （升序排列，序列已经处于升序状态，也就是每一次内层循环发现后面数值已经比前面大了，那么就认为该列表已经排序好了）
• 最坏时间复杂度：O(n)
• 稳定性：稳定

4、插入排序演示

九、快速排序及实现

快速排序（Quicksort），又称 划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割为独立的两部分。其中一部分的所有数据都比另外一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，一次达到整个数据变成有序序列。

步骤为：

1. 从数列中挑出一个元素，成为“基准”（pivot）
2. 重新排序数列，所有元素比基准小的摆放在基准面，所有元素比基准值大的摆在基准的后面（相同的数可以放到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个成为 分区 （partition）操作。
3. 递归地（recursive）把小于基准值元素的子序列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是 0 或 1，也就是永远都已经被排序好。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（interation）中，它至少会把一个元素摆到它最后面的位置去。

1、快速排序的分析

2、python代码的实现

"""快速排序"""
def quick_sort(alist, start, end):
    # 如果 小数值游标 大于等于 大数值游标 ，退出
    if start >= end:
        return
    # 假设中间值，为列表的开始值
    mid_value = alist[start]
    low = start
    high = end

    while low < high:
        # 如果 low<high 并且 大游标的值 大于等于 中间值，那么符合要求。-1 游标往下走
        # 如果 大游标的值 小于 中间值时，while不成立，此时大游标对应的值 附给 小游标的值
        while low < high and alist[high] >= mid_value:
            high -= 1
        alist[low] = alist[high]

        while low < high and alist[low] < mid_value:
            low += 1
        alist[high] = alist[low]

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

    # 对 mid_value 的左边（low）进行排序
    quick_sort(alist, low + 1, end)
    # 对 mid_vaue 的右边（high）进行排序
    quick_sort(alist, start, high - 1)


l = [22, 44, 11, 22, 3, 14, 20]
print(l)
quick_sort(l, 0, len(l) - 1)
print(l)

解读：首先，第一次，选取初始值作为参考值，记为 x ，通过一次排序，即 low 从左向右查找是否有大于 x 的值，如果有，附给high区；high从右向左查找是否是小于 x 的值，如果有，附给low区。当 low 和 high 相等的时候，则证明分别从两端查找完毕，此时 x 就在该列表中合适的位置。然后以 x 为基准点，分为左边的low区，右边的high区。两边再次分别执行排序，以此递归进行。

3、时间复杂度

• 最优时间复杂度： O(nlogn)
• 最坏时间复杂度: O(n)
• 稳定性：不稳定

从一开始快速排序平均需要花费 O(n log n)时间的描述并不明显。但是不难观察到的是分区运算，数组的元素都会在每次循环中走访一遍，使用 O(n) 的时间。

在最好的情况，每次我们运行一次分区，我们会把一个数列分为两个近乎相等的片段。这个意思就是每次递归调用处理一般大小的数列。因此，在到达大小为 1 的数列之前，我们只要作 log n次嵌套的调用。这个意思就是 调用树 的深度是 O(log n) ，但是在同一层次结构的两个程序调用中，不会处理到原来数列的相同部分，一次，程序调用的每一层结构总共全部仅需要 O(n) 的时间（每个调用有某些共同的额外耗费），但是因为在每一次层次结构仅仅只有 O(n) 个调用，这些被归纳在 O(n) 系数中）。结果是这个算法仅需要 O(n log n) 时间。

4、快速排序演示

十、希尔排序及实现

希尔排序（Shell Sort）是插入排序的一种。也称缩小增量排序，值直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分为一组，算法终止。

1、希尔排序过程

希尔排序的基本思想是：将数组在一个表中并对列进行插入排序，重复这个过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只剩一列了。将数组转换至表是为了更好地理解这算法，算法本身还是使用数组进行排序。

例如：假设有这样一组数 [13 14 93 33 82 25 59 94 65 23 45 27 73 25 39 10] ，如果我们以步长为 5 开始进行排序，我们可以通过将这列表放在有 5 列的表中来更好地描述算法，这样他们就应该看起来是这样的（竖着的元素是步长组成的）

13  14  94  33  82
25  59  94  65  23
45  27  73  25  39
10

然后我们对每列进行排序：

10  14  73  25  23
13  27  94  33  39
25  59  94  65  82
45

将上述四行数字，依序接在一起时，得到：[10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]
这时10已经移至正确位置了，然后再以3为步长进行排序：

 10  14  73
 25  23  13
 27  94  33
 39  25  59
 45

排序之后变为：

10  14  13
25  23  33
27  25  59
39  65  73
45  94  82
94

最后以 1 步长进行排序（此时就是简单的插入排序）

2、希尔排序的分析

3、python代码实现

"""希尔排序"""


def shell_sort(alist):
    n = len(alist)
    # 初始步长
    gap = n // 2

    while gap > 0:
        # 插入算法，与普通的插入算法在于步长不一样
        for i in range(gap, n):
            j = i
            while j > 0:
                if alist[j] < alist[j - gap]:
                    alist[j], alist[j - gap] = alist[j - gap], alist[j]
                    j -= gap
                else:
                    break
        gap = gap // 2

解读：初始步长为列表长度整除2后的值。当步长大于0，循环从 （步长 ～ n），将这个值 附给 j ，当 j 大于0时，进入循环，即插入排序。这样每次for循环就会将根据步长所产生的几组数据从第一组到最后一组里面的数字进行排序。这个时候，当for循环执行完毕后，就拿到了第一次以2为步长取出的列表的排序。然后再次根据步长取值，再次排序，以此类推。一直到步长为1，排序完毕。

4、时间复杂度

• 最优时间复杂度：根据步长序列的不同而不同
• 最坏时间复杂度： O(n)
• 稳定性： 不稳定

5、希尔排序演示

十一、归并排序及实现

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。

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

1、归并排序的分析

2、python代码实现

"""归并排序"""
def merge_sort(alist):
    n = len(alist)
    if n <= 1:
        return alist
    mid = n // 2
    # 左侧 采用归并排序后形成的新列表
    left_li = merge_sort(alist[:mid])
    right_li = merge_sort(alist[mid:])

    left_pointer, right_pointer = 0, 0
    result = []
    # 当左侧指针 < 左侧列表长度  and 右侧指针  < 右侧列表长度
    while left_pointer < len(left_li) and right_pointer < len(right_li):
        # 左侧指针对应的值 < 右侧指针对应的值
        if left_li[left_pointer] < right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1

    # 将排序最终剩余的直接加进来，即最后一个
    result += left_li[left_pointer:]
    result += right_li[right_pointer:]

    return result

解读：该排序算法还是采取了递归的方法，通过每次整除2得到的值以及不断执行 merge_sort() 得来拆分数组，最终得到每个包含一个元素的数组，在将两个数组进行排序、合并，得到排好序的包含两个元素的数组，再将两个已经排好序的包含两个元素的数组再进行排序、合并。以此类推。

3、时间复杂度

• 最优时间复杂度： O(nlogn)
• 最坏时间复杂度： O(nlogn)
• 稳定性： 稳定

4、归并排序演示

十二、排序与搜索

1、排序算法

排序算法（Sorting algorithm） 是一种能将一串数据依照特定顺序进行排列的一种算法。

2、排序算法的稳定性

稳定性： 稳定排序算法会让原本有相等键值的记录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的记录 R 和 S ，且在原本的列表中 R 出现在 S 之前，在排序过的列表中 R 也将会是在 S 之前。

当相等的元素是无法分辨的，比如像是 整数，稳定性并不是一个问题。然而，假设一下的数对将要以他们的第一个数来排序。

(4, 1) (3, 1) (3, 7) (5, 6)

在这种状况下，有可能产生两种不同的结果，一个是让相等键值的记录维持相对的次序，而另外一个则没有：

(3, 1) (3, 7) (4, 1) (5, 6)     (维持次序)
(3, 7) (3, 1) (4, 1) (5, 6)     (次序被改变)

不稳定排序算法可能会在相等的键值中改变记录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同减至的两个对象之间比较，（比如上面的比较中加入第二个标准：第二个键值的大小）就会被决定使用在原先数据次序中的条目，当做一个同分决赛。然而，要记住这种次序通常牵扯到额外的空间负担。

十三、二分查找及时间复杂度

1、搜索

搜索是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真或假，因为该项目是否存在。搜索的几种常见方法：顺序查找、二分法查找、二叉树查找、哈希查找。

2、二分法查找

二分法查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中的元素是按升序排序，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分为前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，知道找到满足条件的记录。使查找成功，或直到子表不存在为止，此时查找不成功。

3、python代码实现

3.1、递归方式

def binary_search(alist, item):
    """二分查找——递归"""
    n = len(alist)

    mid = n // 2
    if n > 0:
        # 如果存在元素，返回 True
        if alist[mid] == item:
            return True
        # 如果 目标元素 小于 alist的中间值索引对应的索引
        elif item < alist[mid]:
            return binary_search(alist[:mid], item)
        # 否则，就在右边
        else:
            return binary_search(alist[mid+1:], item)
    return False

3.2、非递归

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
        # 如果 目标值 在右侧，将last等于中间值的左侧第一个
        elif item < alist[mid]:
            last = mid - 1
        # 如果在左侧，将first等于中间值右边第一个
        else:
            first = mid + 1
    return False

4、时间复杂度

• 最优时间复杂度： O(1)
• 最坏时间复杂度： O(nlogn)

十四、树的基本概念及分类

1、树的概念

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

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

2、树的术语

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

3、树的种类

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

4、树的存储与表示

(1)顺序存储：将数据结构存储在固定的数组中，在遍历速度上有一定的有事，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。

(2)链式存储：

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

1. xml、html等，那么编写这些东西的解析器的时候，不可避免用到树
2. 路由协议就是使用了树的算法
3. mysql数据库索引
4. 文件系统的目录结构
5. 很多经典的 AI 算法都是树搜索

6、python构造一颗树

class Node():

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


class Tree():
    """二叉树"""
    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)
            # 如果左节点的子节点为None，就赋值给他；否则 末尾追加
            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)

十五、二叉树及相关遍历操作

1、基本概念

二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）

2、性质（特性）

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

（1）完全二叉树：若设二叉树的高度为 h ，除第 h 层外，其他各层（1～h-1）的节点数都达到最大个数，第 h 层有叶子节点，并且叶子节点都是从左到有一次排布。

（2）满二叉树：除了叶节点外每一个节点都有左右叶子且叶子节点都处在最底层的二叉树。

3、二叉树的遍历

树的遍历是树的一种重要的运算。所谓遍历是指对树中所有节点的信息的访问，即依次对树中每个结点访问一次且仅访问一次，我们把这种对所有节点的访问称为 遍历（traversal）。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历，深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。

3.1、深度优先遍历

对于一颗二叉树，深度优先搜索（Depth First Search）是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
那么深度遍历有重要的三种方法。这三种方式常被用于访问树的节点，他们之间的不同在于访问每个节点的次序不同。这三种遍历分别叫做 先序遍历（preorder），中序遍历（inorder）和后序遍历（postorder）。下面来依次说明。

• 先序遍历：在先序遍历中，我们先访问根节点，然后递归使用先序遍历访问左子树，再递归使用先序遍历访问右子树

根节点 ——> 左子树 ——> 右子树

python代码实现：

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

• 中序遍历：在中序遍历中，我们递归使用中序遍历访问左子树，然后访问根节点，最后再递归使用中序遍历访问右子树。

左子树 ——> 根节点 ——> 右子树

python代码实现：

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

• 后序遍历：在后序遍历中，我们先递归使用后序遍历访问左子树和右子树，最后访问根节点

左子树 ——> 右子树 ——> 根节点

python代码实现

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

3.2、广度优先遍历（层次遍历）

从根的 root 开始，从上到下，从左到有遍历整个树的节点

def breath_travel(self):
    """广度遍历"""
    if self.root is 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)

4、完整代码

class Node():

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


class Tree():
    """二叉树"""
    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)
            # 如果左节点的子节点为None，就赋值给他；否则 末尾追加
            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 breath_travel(self):
        """广度遍历"""
        if self.root is 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)

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

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

    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.breath_travel()
    print(" ")
    tree.preorder(tree.root)
    print(" ")
    tree.inorder(tree.root)
    print(" ")
    tree.postorder(tree.root)

输出结果：

0 1 2 3 4 5 6 7 8 9  
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、算法概述

0.1 算法分类

十种常见排序算法可以分为两大类：

比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

0.2 算法复杂度

0.3 相关概念

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

1、冒泡排序（Bubble Sort）

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

1.1 算法描述
比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。
1.2 动图演示

1.3 代码实现

def bubble_sort(alist):
    n = len(alist)
    # 控制走多少次
    for j in range(0, n- 1):
        count = 0
        # 控制从头走到尾的距离
        for i in range(0, n - 1 - j):
            if alist[i] > alist[i + 1]:
                alist[i], alist[i + 1] = alist[i + 1], alist[i]
                count += 1

1.4、算法分析

• 最优时间复杂度：O(n)
  （表示遍历一次返现没有任何可以交换的元素，排序结束）
• 最坏时间复杂度：O(n)
  （表示两次for循环全部执行，一个for循环为n）
• 稳定性：稳定

2、选择排序（Selection Sort）

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

2.1 算法描述
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

初始状态：无序区为R[1..n]，有序区为空；
第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
n-1趟结束，数组有序化了。
2.2 动图演示

2.3 代码实现

"""选择排序"""
def select_sort(alist):
    n = len(alist)
    # 需要进行 n-1 次操作
    for j in range(0, n-1):
        # 记录最小的位置
        min_index = j
        # 从 j+1 到末尾，选出最小的数字
        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]

2.4 算法分析

• 最优时间复杂度：O(n)
• 最坏时间复杂度：O(n)
• 稳定性：不稳定（考虑升序每次选择最大的情况）

3、插入排序（Insertion Sort）

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

3.1 算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2~5。
3.2 动图演示

3.2 代码实现

"""插入排序"""
def insert_sort(alist):
    n = len(alist)
    # 从第二个位置开始，即下标0，到n-1
    for i in range(1, n):
        # i, i-1, i-2 ,..., 1
        for j in range(i, 0, -1):
            if alist[j] < alist[j-1]:
                alist[j-1], alist[j] = alist[j], alist[j-1]

3.4 算法分析

• 最优时间复杂度：O(n)
• 最坏时间复杂度：O(n)
• 稳定性：稳定

4、希尔排序（Shell Sort）

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

4.1 算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
4.2 动图演示

4.3 代码实现

"""希尔排序"""


def shell_sort(alist):
    n = len(alist)
    # 初始步长
    gap = n // 2

    while gap > 0:
        # 插入算法，与普通的插入算法在于步长不一样
        for i in range(gap, n):
            j = i
            while j > 0:
                if alist[j] < alist[j - gap]:
                    alist[j], alist[j - gap] = alist[j - gap], alist[j]
                    j -= gap
                else:
                    break
        gap = gap // 2

4.4 算法分析
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。

• 最优时间复杂度：根据步长序列的不同而不同 O(n logn) ～ O(n)
• 最坏时间复杂度： O(n)
• 稳定性： 不稳定

5、归并排序（Merge Sort）

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

5.1 算法描述
把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。
5.2 动图演示

5.3 代码实现

"""归并排序"""
def merge_sort(alist):
    n = len(alist)
    if n <= 1:
        return alist
    mid = n // 2
    # 左侧 采用归并排序后形成的新列表
    left_li = merge_sort(alist[:mid])
    right_li = merge_sort(alist[mid:])

    left_pointer, right_pointer = 0, 0
    result = []
    # 当左侧指针 < 左侧列表长度  and 右侧指针  < 右侧列表长度
    while left_pointer < len(left_li) and right_pointer < len(right_li):
        # 左侧指针对应的值 < 右侧指针对应的值
        if left_li[left_pointer] < right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1

    # 将排序最终剩余的直接加进来，即最后一个
    result += left_li[left_pointer:]
    result += right_li[right_pointer:]

    return result

5.4 算法分析
归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

• 最优时间复杂度： O(nlogn)
• 最坏时间复杂度： O(nlogn)
• 稳定性： 稳定

6、快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

6.1 算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
6.2 动图演示

6.3 代码实现

"""快速排序"""
def quick_sort(alist, start, end):
    # 如果 小数值游标 大于等于 大数值游标 ，退出
    if start >= end:
        return
    # 假设中间值，为列表的开始值
    mid_value = alist[start]
    low = start
    high = end

    while low < high:
        # 如果 low<high 并且 大游标的值 大于等于 中间值，那么符合要求。-1 游标往下走
        # 如果 大游标的值 小于 中间值时，while不成立，此时大游标对应的值 附给 小游标的值
        while low < high and alist[high] >= mid_value:
            high -= 1
        alist[low] = alist[high]

        while low < high and alist[low] < mid_value:
            low += 1
        alist[high] = alist[low]

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

    # 对 mid_value 的左边（low）进行排序
    quick_sort(alist, low + 1, end)
    # 对 mid_vaue 的右边（high）进行排序
    quick_sort(alist, start, high - 1)

6.4、算法分析

• 最优时间复杂度： O(nlogn)
• 最坏时间复杂度: O(n)
• 稳定性：不稳定

7、堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

7.1 算法描述
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
7.2 动图演示

7.3、算法分析

• 最优时间复杂度：
• 最坏时间复杂度：
• 稳定性：

8、计数排序（Counting Sort）

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

8.1 算法描述
找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
8.2 动图演示

8.4 算法分析
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

9、桶排序（Bucket Sort）

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

9.1 算法描述
设置一个定量的数组当作空桶；
遍历输入数据，并且把数据一个一个放到对应的桶里去；
对每个不是空的桶进行排序；
从不是空的桶里把排好序的数据拼接起来。
9.2 图片演示

9.3 算法分析
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

10、基数排序（Radix Sort）

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

10.1 算法描述
取得数组中的最大数，并取得位数；
arr为原始数组，从最低位开始取每个位组成radix数组；
对radix进行计数排序（利用计数排序适用于小范围数的特点）；
10.2 动图演示

10.4 算法分析
基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。

基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。