算法基础

• 算法的定义和特征

# 一个计算过程,解决问题的方法
- 解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制,
能够对一定规范的输入，在有限时间内获得所要求的输出,如果一个算法有缺陷，或不适合于某个问题，执行这个算法
将不会解决这个问题,不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量.
# 特征
- 有穷性：算法的有穷性是指算法必须能在执行有限个步骤之后终止
- 确切性：算法的每一步骤必须有确切的定义
- 输入项：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件
- 输出项：一个算法有一个或多个输出，以反映对输入数据加工后的结果，没有输出的算法是毫无意义的；
- 可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。

• 算法设计的要求

- 确定性: 指的是算法至少应该有输入,输出和加工处理无歧义性，能正确反映问题的需求,能够得到问题的正确答案。
- 确定性大体分为四个层次:
    1.算法程序无语法错误;
    2.算法程序对于合法的输入产生满足要求的输出;
    3.对于非法输入能够产生满足规格的说明;
    4.算法程序对于故意刁难的测试输入都有满足要求的输出结果。

- 可读性: 程序便于阅读,理解交流。
- 健壮性: 当输入数据不合法时,算法也能作出相关处理，而不是产生异常,崩溃或者莫名其妙的结果。时间效率高和存储量低

• 算法的时间复杂度

# 定义
- 在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级.
- 算法的时间复杂度，也就是算法的时间量度，记作：T(n)=0(f(n))
- 它表示随问题规模n的增大，算法执行时间的埔长率和 f(n)的埔长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。
其中f( n)是问题规横n的某个函数.

# 求解算法的时间复杂度的具体步骤
- 找出算法中的基本语句 (算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体)
- 计算基本语句的执行次数的数量级(只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，
可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率)
- 用大Ο记号表示算法的时间性能(将基本语句执行次数的数量级放入大Ο记号中)

# 推导大o阶的基本的推导方法：
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中，只保留最髙阶项。
- 如果最高阶项存在且不是1,则去除与这个项相乘的常数。简单的说，就是保留求出次数的最高次幂，并且把系数去掉。 如T(n)=n2+n+1 =O(n2)

#复杂度O(1) print("this is wd") 
#复杂度O(n) for i in range(n): print(i) 
#复杂度O(n2) for i in range(n): for j in range(n): print(j) 
#复杂度O(n3) for i in range(n): for j in range(n): for k in range(n): print('wd') 
#复杂度O(log2n) while n > 1: print(n) n = n // 2

#  常见的复杂度按效率排序：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(2nlogn)<O(n2) 

• 算法空间复杂度

# 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度(三个方面)
- 包括存储算法本身所占用的存储空间(存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法)
- 算法的输入输出数据所占用的存储空间(算法的输入输出数据所占用的存储空间是由要解决的问题决定的，
是通过参数表由调用函数传递而来的，它不随本算法的不同而改变)
- 算法在运行过程中临时占用的存储空间(算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只
需要占用少量的临时工作单元，而且不随问题规模的大小而改变，这种算法是节省存储的算法；有的算法需要
占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元)
- 具体表述
    1.当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；
    2.当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(log2n)；
    3.当一个算法的空间复杂度与n成线性比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实
    4.参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地
    5.址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。

排序二叉树

# 使用二叉树 alist = [3,8,5,7,6,2,9,4,1] 进行排序
乱序数据的插入的时候，需要遵从一个准则：
- 插入的第一个数值作为树的根节点
- 后序插入的数值，如果比根节点小，插入根节点的左侧，否则插入到根节点的右侧
- 使用深度优先中序遍历

# 代码
class Node():
    def __init__(self,item):
        self.item = item
        self.left = None
        self.right = None  
class SortTree():
    def __init__(self):
        self.root = None
    def add(self,item):
        node = Node(item)
        cur = self.root
        if self.root == None:
            self.root = node
            return
        while cur:
            #向右侧插入
            if item > cur.item:
                if cur.right == None:
                    cur.right = node
                    break
                else:
                    cur = cur.right

            else:#向左插入
                if cur.left == None:
                    cur.left = node
                    break
                else:
                    cur = cur.left
                    
    def middle(self,root):#中序:左根右
        if root == None:
            return
        self.middle(root.left)
        print(root.item)
        self.middle(root.right)
        
tree = SortTree()
alist = [3,8,5,7,6,2,9,4,1]
for i in alist:
    tree.add(i)
tree.middle(tree.root)  
# 执行结果
1
2
3
4
5
6
7
8
9

二分查找

# 一定是基于有序集合的查找
- 有序列表对于我们的实现搜索是很有用的。在顺序查找中，当我们与第一个元素进行比较时，
如果第一个元素不是我们要查找的，则最多还有 n-1 个元素需要进行比较。 二分查找则是从中间元素开始，
而不是按顺序查找列表。 如果该元素是我们正在寻找的元素，我们就完成了查找。 如果它不是，我们可以
使用列表的有序性质来消除剩余元素的一半。如果我们正在查找的元素大于中间元素，就可以消除中间元素
以及比中间元素小的一半元素。如果该元素在列表中，肯定在大的那半部分。然后我们可以用大的半部分重复该过程，
继续从中间元素开始，将其与我们正在寻找的内容进行比较。

# 二分查找原理
- 随便想一个1～100的数字。
你的目标是以最少的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。
从50 开始,小了，但排除了一半的数字！至此，你知道1～50都小了。接下来，你猜75。大了，那余下的数字又排除了一半！
使用二分查找时，你猜测的是中间的数字，从而每次都将余下的数字排除一半。

#  需要搜索的元素越多,二分查找的速度比普通遍历查找就快得多。
#  二分查找O(log n) 比普通遍历查找O(n)时间复杂度低。

# 代码
def find(alist,item):
    find = False
    first = 0
    last = len(alist)-1
    
    while first <= last:
        mid_index = (first + last) // 2
        
        if alist[mid_index] < item:#去中间元素的右侧继续去寻找
            first = mid_index + 1
        elif alist[mid_index] > item:
            last = mid_index - 1
        else:
            find = True
            break
    return find,mid_index

alist = [1,2,3,4,5,6,7,8,9]
print(find(alist,1))
# 执行结果
True

冒泡排序

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

# 代码

#列表元素两两比较，大的值逐渐向后移动
def sort(alist):
    for i in range(len(alist)-1):
        if alist[i] > alist[i+1]:
            alist[i],alist[i+1] = alist[i+1],alist[i]
    return alist
alist = [3,8,5,7,6]
print(sort(alist))
# 执行结果 [3, 5, 7, 6, 8]

# 逐渐将乱序序列的最大值找出放置在乱序序列的尾部
def sort(alist):
    for j in range(len(alist)-1):
        for i in range(len(alist)-1-j):
            if alist[i] > alist[i+1]:
                alist[i],alist[i+1] = alist[i+1],alist[i]
    return alist

alist = [3,8,5,7,6]
print(sort(alist))   

# 执行结果 [3, 5, 6, 7, 8]

# 什么时候最快
当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。

# 什么时候最慢
当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。

选择排序

# 原理
- 选择排序,可以理解为改进了冒泡排序，每次遍历列表只做一次交换。为了做到这一点，一个选择排序在他遍历时寻找最大的值(最小值)，
并在完成遍历后，将其放置在正确的位置(小的在前,大的在后)。直到所有元素均排序完毕。

# 代码
# 将乱序中的最大值找出，跟最后一个元素交换位置
def sort(alist):
    max_index = 0 #最大值的下标
    for i in range(1,len(alist)):
        if alist[max_index] < alist[i]:
            max_index = i
    alist[len(alist)-1],alist[max_index] = alist[max_index],alist[len(alist)-1]
    return alist
# 执行结果 [3, 6, 5, 7, 8]

# 依次将乱序中的最大值找出，跟最后一个元素交换位置
def sort(alist):
    for j in range(0,len(alist)-1):
        max_index = 0 # 最大值的下标
        for i in range(1,len(alist)-j):
            if alist[max_index] < alist[i]:
                max_index = i
        alist[len(alist)-1-j],alist[max_index] = alist[max_index],alist[len(alist)-1-j]
    return alist

alist = [3,8,5,7,6]
print(sort(alist))
# 执行结果 [3, 5, 6, 7, 8]

# 选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，
数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

插入排序

# 原理
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列，
将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

# i有序子集中元素的个数,还可以表示下标
# alist[i]乱序子集中的第一个元素
# alist[i-1]有序子集中的最后一个元素

# 实现思路
i = 1 
if alist[i] < alist[i-1]:# 乱序子集中的第一个元素值小于有序子集中的最后一个元素的值,交换位置
    alist[i],alist[i-1] = alist[i-1],alist[i]
else:
    pass
i += 1

i = 2
while i > 0: # 有序子集个数大于0时,执行循环 
    if alist[i] < alist[i-1]: 
        alist[i],alist[i-1] = alist[i-1],alist[i]
        i -= 1
    else:
        break
        
# 完整代码
def sort(alist):
    for i in range(1,len(alist)): # 控制遍历次数,(len(alist)-1)就可以完成排序
        while i > 0:
            if alist[i] < alist[i-1]:
                alist[i],alist[i-1] = alist[i-1],alist[i]
                i -= 1
            else:
                break
    return alist

alist = [3,8,5,7,6]
print(sort(alist))

# 执行结果 [3, 5, 6, 7, 8]

希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本,
该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量（gap）”的元素组成的）
分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，
再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，
因此希尔排序在时间效率比直接插入排序有较大提高。

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
- 希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
2.但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
  希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，
待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。    

# 代码
def sort(alist):
    gap = len(alist)//2 #初始gap
    
    while gap >= 1:
        for i in range(gap,len(alist)):
            while i > 0:
                if alist[i] < alist[i-gap]:
                    alist[i],alist[i-gap] = alist[i-gap],alist[i]
                    i -= gap
                else:
                    break
        gap //= 2
    return alist
alist = [3,8,5,7,6]
print(sort(alist))
# 执行结果 [3, 5, 6, 7, 8]

快速排序

# 原理
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

# 实现流程
    - 将列表中第一个元素设定为基准数字，赋值给mid变量，然后将整个列表中比基准小的数值放在基准的左侧，
比基准到的数字放在基准右侧。然后将基准数字左右两侧的序列在根据此方法进行排放。
    - 定义两个指针，low指向最左侧，high指向最右侧
    - 然后对最右侧指针进行向左移动，移动法则是，如果指针指向的数值比基准小，则将指针指向的数字移动到基准数字原始的位置，
否则继续移动指针。
    - 如果最右侧指针指向的数值移动到基准位置时，开始移动最左侧指针，将其向右移动，如果该指针指向的数值大于基准则将该数值
移动到最右侧指针指向的位置，然后停止移动。
    - 如果左右侧指针重复则，将基准放入左右指针重复的位置，则基准左侧为比其小的数值，右侧为比其大的数值。

def sort(alist,start,end):
    #基数
    low = start
    high = end 
    
    if low > high:
        return
    
    mid = alist[start]
    while low < high:
        #偏移high
        while low < high:
            if alist[high] >= mid:
                #向左偏移high
                high -= 1
            else:
                alist[low] = alist[high]
                break
        #偏移low
        while low < high:
            if alist[low] <= mid:
                low += 1
            else:
                alist[high] = alist[low]
                break
        if low == high:
            alist[low] = mid
            break
    #作用到左侧
    sort(alist,start,high-1)
    #左右到右侧
    sort(alist,low+1,end)
    return alist

alist = [6,1,2,7,9,3,4,5,10,6,1,8]
print(sort(alist,0,len(alist)-1))

# 执行结果
[1, 1, 2, 3, 4, 5, 6, 6, 7, 8, 9, 10]