评判程序优劣的方法
消耗计算机资源和执行效率
计算算法执行的耗时
时间复杂度
时间复杂度
评判规则：量化算法执行的操作/执行步骤的数量
最重要的项：时间复杂度表达式中最有意义的项
大O记法：就是使用时间复杂度衡量算法好坏的表现形式
O（最重要的项）
常见的时间复杂度：O(1)<O(logn，底数是2)<O(nlogn)<O(n^3)<O(2^n)<O(n!)<O(n^n)
数据结构
概念：对于数据（基本类型的数据：（int,float,char））的组织方式就被称作为数据结构。数据结构解决的就是一组数据如何进行保存、保存形式是怎样的。
案例：需要存储一些学生的信息（name，score），那么这些数据应该如何组织呢？查询某一个具体的学生的时间复杂度是什么样的呢？
[{
'name':'xxx',
'score':'xxx'
},{
'name':'xxx',
'score':'xxx'
}]
[{'name': 'xxx', 'score': 'xxx'},
{'name': 'xxx', 'score': 'xxx'}]
{
'zhangsan':{'score':'xxx'},
'lisi':{'score':'xxx'}
}
{'zhangsan': {'score': 'xxx'}, 'lisi': {'score': 'xxx'}}
def test01(): alist = [] for i in range(1000): alist.append(i) return alist # 时间复杂度需要知道append的内部实现方式，或者直接计算程序运行时间 def test02(): alist = [] for i in range(1000): alist = alist + [i] return alist
def test03(): alist = [i for i in range(1000)] return alist
def test04(): alist = list(range(1000)) return alist
计算运行平均耗时
from timeit import Timer if __name__ == '__main__': timer1 = Timer(stmt='test01()',setup='from __main__ import test01') t1 = timer1.timeit(100) print(t1)
from timeit import Timer def test01(): alist = [] for i in range(1000): alist.append(i) return alist # 时间复杂度需要知道append的内部实现方式，或者直接计算程序运行时间 def test02(): alist = [] for i in range(1000): alist = alist + [i] return alist def test03(): alist = [i for i in range(1000)] return alist def test04(): alist = list(range(1000)) return alist if __name__ == '__main__': timer1 = Timer(stmt = 'test01()',setup="from __main__ import test01") t1 = timer1.timeit(100) timer2 = Timer(stmt = 'test02()',setup='from __main__ import test02') t2 = timer2.timeit(100) timer3 = Timer(stmt = 'test03()',setup='from __main__ import test03') t3 = timer3.timeit(100) timer4 = Timer(stmt = 'test04()',setup='from __main__ import test04') t4 = timer4.timeit(100) print(t1) print(t2) print(t3) print(t4)
0.008431599999999762 0.13526840000000107 0.002955000000000041 0.0009373999999997551
栈
栈的特性：先进后出
栈顶，栈底
从栈顶向栈底添加元素，从栈顶取元素
Stack()创建一个空的新栈。
push(item)将一个新项添加到栈的顶部，他需要item做参数并不返回任何内容。
pop()从栈中删除顶部项。它不需要参数并返回item。栈被修改。
peek()从栈返回顶部项，但不会删除它，不需要参数，不修改栈。
isEmpty()测试栈是否为空，不需要参数，返回布尔值。
size()返回栈中的item数量，不需要参数，并返回一个整数。
class Stack(): def __init__(self): # 构建一个空栈 self.items=[] def push(self,item): # 从栈顶添加到栈底 self.items.append(item) def pop(self): # 从栈顶向栈底取元素 return self.items.pop() def peek(self): # 返回栈顶元素下标 return len(self.items)-1 def isEmpty(self): return sel.items == [] def size(self): return len(self.items)
a = Stack() a.push(1) a.push(2) a.push(3) print(a.pop()) print(a.pop()) print(a.pop())
队列
先进先出
class Queue(): def __init__(self): self.items=[] def enqueue(self,item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def isEmpty(self): return self.items==[] def size(self): return len(self.items)
q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) print(q.dequeue()) print(q.dequeue()) print(q.dequeue())
案例：烫手山芋
6个孩子围成一圈，排列顺序孩子们自己决定，第一个孩子手里有一个烫手山芋，需要在计时器计时一秒后将山芋传递给下一个孩子，以此类推。规则是，在计时器每计时7秒时，手里有山芋的孩子退出游戏。该游戏直到剩下一个孩子时结束，最后的孩子获胜。请用队列实现该游戏策略，排在第几个位置最终会获胜。
分析：
在一轮游戏中山芋会被传递六次
山芋传递的次数不受孩子个数的影响
山芋传递六次后一轮游戏结束，淘汰一个孩子继续
队列：先进先出，只可以从队头取出元素，向队尾添加元素
准则：保证队头孩子手里有山芋（谁手里有山芋，谁作为对头）
方便删除元素。最终七秒到的时候需要将手里有山芋的孩子从队列中删除
# kids = ['A','B','C','D','E','F']
kids = [i for i in range(30)]
queue = Queue()
# 将6个孩子添加到队列中
for kid in kids:
queue.enqueue(kid)
while queue.size() > 1:
# 游戏开始，开始传递山芋
# 山芋传递的次数
for i in range(6):
# 让队头孩子出队列再入队列
kid = queue.dequeue()
queue.enqueue(kid)
# 当6次循环结束后，说明山芋被传递了6次，说明一轮游戏结束
# 一轮游戏结束后，将队头孩子淘汰
queue.dequeue()
# 当while循环结束后，游戏结束，队列中今生的孩子就是获胜者
print('获胜者：',queue.dequeue())
获胜者： 22
def Hot_Shanyu(n): kids = [i for i in range(1,n+1)] queue = Queue() # 将6个孩子添加到队列中 for kid in kids: queue.enqueue(kid) while queue.size() > 1: # 游戏开始，开始传递山芋 # 山芋传递的次数 for i in range(6): # 让队头孩子出队列再入队列 kid = queue.dequeue() queue.enqueue(kid) # 当6次循环结束后，说明山芋被传递了6次，说明一轮游戏结束 # 一轮游戏结束后，将队头孩子淘汰 queue.dequeue() # 当while循环结束后，游戏结束，队列中今生的孩子就是获胜者 return queue.dequeue()
Hot_Shanyu(30)
两个队列实现栈
items = [1,2,3,4,5] q1 = Queue() q2 = Queue() for item in items: q1.enqueue(item) while True: # 将q1中的n-1个元素出队列再加入到q2中 while q1.size() > 1: item = q1.dequeue() q2.enqueue(item) print(q1.dequeue()) q1,q2 = q2,q1 if q1.size() == 0: break
两个栈实现队列
s1 = Stack() s2 = Stack() items = [1,2,3,4,5] for item in items: s1.push(item) while True: while s1.size() > 0: item = s1.pop() s2.push(item) print(s2.pop()) if s2.size()==0: break
两个栈封装为队列
class Two_Stack_Queue(): def __init__(self): self.s1 = Stack() self.s2 = Stack() self.items=[] def enqueue(self,item): self.s1.push(item) def dequeue(self): while self.s1.size()>0: item = self.s1.pop() self.s2.push(item) return self.s2.pop()
def Two_Stack(): s1 = Stack() s2 = Stack() items = [1,2,3,4,5] for item in items: s1.push(item) while True: while s1.size() > 0: item = s1.pop() s2.push(item) s2.pop() if s2.size()==0: break
双端队列
同队列相比，有两个头部和尾部。可以在双端进行数据的插入和删除，提供了单数据结构中栈和队列的特性。
Deque()创建一个空的新deque。不需要参数并返回空的deque。
addFront（item）将一个新项添加到deque的首部。需要item参数并不返回任何内容。
addRear（item）将一个新项添加到deque的尾部。需要item参数，不返回任何内容。
removeFront（）从deque中删除首项。不需要参数并返回item。deque被修改。
removeRear（）从deque中删除尾项。不需要参数，返回item。的确被修改。
isEmpty（）测试deque是否为空。不需要参数，返回布尔值。
size（）返回deque中的项数。不需要参数，返回一个整数。
class Deque(): def __init__(self): self.items=[] def addFront(self,item): self.items.insert(0,item) def addRear(self,item): self.items.append(item) def removeFront(self): return self.items.pop(0) def removeRear(self): return self.items.pop() def isEmpty(self): return self.items==[] def size(self): return len(self.items)
dq = Deque() dq.addFront(3) dq.addFront(2) dq.addFront(1) dq.addRear(4) dq.addRear(5) dq.addRear(6) # 1,2,3,4,5,6
print(dq.removeFront()) print(dq.removeFront()) print(dq.removeFront()) print(dq.removeRear()) print(dq.removeRear()) print(dq.removeRear())
给相同的数据类型的数据开辟固有大小的内存空间
整型：4btyte
python可以根据数据大小自动填充内存，malloc函数
浮点型：单精度4byte，双精度8byte
字符型：1byte
字符串是由入肝字符型数据加'\0'组成，占(n+1)byte
import numpy as np
print(np.iinfo('int8'))
print(np.iinfo('int32'))
顺序表
数据结构中存储的元素是有顺序的，顺序表的结构可以分为两种形式：单数据类型（数组）和多数据类型（列表）。
python中的列表和元祖就属于多数据类型的顺序表。
顺序表弊端：顺序表的结构需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁。
链表：相对于顺序表，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理且进行扩充时不需要进新数据搬迁。
链表是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是每一个节点（数据存储单元）里存放下一个节点的信息（即地址）。
is_empty():链表是否为空
length（）：链表长度
travel（）：遍历整个链表
add(item)：链表头部添加元素
append(item)：链表尾部添加元素
insert(pos,item)：指定位置添加元素
remove(item)：删除节点
search(item)：查找节点是否存在
# 节点的封装 class Node(): def __init__(self,item): self.item = item self.next = None
# 链表封装 class Link(): def __init__(self): # 构架一个空链表 self._head = None # head永远要指向链表中的第一个节点，None表示链表中没有节点 def add(self,item): # 向链表的头部添加节点（insert（0，item）） # 实例化一个新的节点对象 node = Node(item) node.next = self._head self._head = node # 将_head指向当前节点 def travel(self): # print(self._head.item) # print(self._head.next.item) # print(self._head.next.next.item) # cur 指向了第一个节点 # _head要永远指向第一个节点，不要轻易改变_head的指向 cur = self._head while cur: print(cur.item) cur = cur.next # 判断链表是否为空 def is_empty(): return self._head == None # 返回链表长度 def length(self): # 返回链表节点的个数 cur = self._head count = 0 while cur: count+=1 cur = cur.next return count def append(self,item): # 向链表的尾部添加节点 node = Node(item) # 如果链表为空 if self._head == None: self._head == node return # 如果链表为非空 pre = None #pre是指向cur前面的一个节点 cur = self._head while cur: pre = cur cur = cur.next # 当while结束时，pre就指向了立案表中最后一个节点 pre.next = node def search(self,item): # 查找item对应的节点是否存在 cur = self._head find = False while cur: if cur.item == item: find = True break else: cur = cur.next return find def insert(self,pos,item): # 将item对应的节点插入到POS指定的位置中 node = Node(item) cur = self._head pre = None if pos == 0: node.next = self._head self._head = node return for i in range(pos): pre = cur cur = cur.next pre.next = node node.next = cur def remove(self,item): # 将item对应的节点删除 pre = None cur = self._head if item == self._head.item: # 要删除的节点恰好为第一个节点 self._head = self._head.next return while cur: pre = cur cur = cur.next if cur.item == item: pre.next = cur.next return # 链表倒置 def reverse(self): pre = self._head cur = pre.next next_node = cur.next pre.next = None # 链表倒置之后，pre是最后一个节点，最后一个节点的指向为空 while (1): cur.next = pre # 将pre、cur、next_node向后偏移 pre = cur cur = next_node if next_node != None: next_node = next_node.next else: break self._head = pre
link = Link() link.add(3) link.add(2) link.add(1) link.append(4) link.append(5) link.append(6) link.insert(6,88) link.travel() print(link.length()) print(link.search(5))
link.reverse() link.travel()
二叉树
根节点：树最上部的节点
左叶子节点
右叶子节点
子树
完整子树：一个根节点，左右叶子结点
不完整子树：
根节点、左叶子结点
根节点、右叶子节点
根节点
特点：每一个节点都可以作为某一个子树的根节点
class Node(): def __init__ (self,item): self.item = item self.left = None # 指向该节点的左叶子节点 self.right = None # 指向该节点的右叶子节点 class Tree(): def __init__(self): self.root = None # 永远指向二叉树中的根节点 # 自上到下从左到右的顺序插入节点 def insert(self,item): # 向树中插入一个节点 node = Node(item) # 如果输为空 if self.root == None: self.root = node return # 如果树为非空 cur = self.root q = [cur] while True: n = q.pop(0) # 取出根节点 if n.left != None: q.append(n.left) else: n.left = node break if n.right != None: q.append(n.right) else: n.right = node break # 遍历节点 def travel(self): cur = self.root q = [cur] while q: n = q.pop(0) print(n.item) if n.left != None: q.append(n.left) if n.right != None: q.append(n.right) # 前序遍历 # 参数root表示子树的根节点，需要给递归调用的forward传入不同子树的根节点 def forward(self,root): # 根左右 if root == None: return print(root.item) # print(self.root.left.item) self.forward(root.left) # print(self.root.righr.item) self.forward(root.right) # 中序遍历 def middle(self,root): # 左根右 if root == None: return self.middle(root.left) print(root.item) self.middle(root.right) # 后序遍历 def back(self,root): # 左右根 if root == None: return self.back(root.left) self.back(root.right) print(root.item)
tree = Tree()
tree.insert(1)
tree.insert(2)
tree.insert(3)
tree.insert(4)
tree.insert(5)
tree.insert(6)
tree.travel()
tree.forward(tree.root)
print('-'*50)
tree.middle(tree.root)
print('-'*50)
tree.back(tree.root)
二叉树遍历
广度遍历：
上述代码中的遍历就是广度遍历，自上到下逐行遍历叫做广度遍历
深度遍历（纵向遍历。前中后序遍历需要做用到子树中。前中后序中的前中后指的是子树中根节点的位置）：
前序：根-左-右。先遍历子树的根节点，再遍历子树的左节点然后是右节点。
中序：左-根-右
后序：左-右-根
深度遍历实现思路：
深度遍历是需要作用到每一棵子树中。
子树和子树之间的的区体现在跟节点中。
如果写一个函数，该函数可以将一个字书中的节点进行遍历，则将该函数作用到其他子树中就可以将整棵树进行深度遍历。
排序二叉树
需要从新封装二叉树
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) if self.root == None: # 树为空的情况 self.root = node return cur = self.root while True: # 树为非空 if cur.item > item: # 说明插入的节点值小于根节点，该节点需要插入到根节点的左侧 if cur.left == None: # 如果左节点为空则直接插入 cur.left = node break else: # 左节点为非空 cur = cur.left else: # 插入节点的值大于等于根节点，该节点需要插入到根节点的右侧 if cur.right == None: cur.right = node break else: cur = cur.right # 中序遍历 def middle(self,root): # 左根右 if root == None: return self.middle(root.left) print(root.item) self.middle(root.right)
alist = [3,8,5,7,6,2,1] tree = SortTree() for item in alist: tree.add(item) tree.middle(tree.root)
二分查找
二分查找只能做用于有序序列中
def find(alist,item): # alist是一个有序序列,item是alist中要查找的元素 low = 0 high = len(alist)-1 find = False while low <= high: mid = (low+high)//2 # 中间元素下标 if item < alist[mid]: # 查找的元素小于中间元素，查找的元素在中间元素左侧 # 将中间元素左侧的序列作为一个新的序列，再基于item和当前新序列的中间值进行大小比较 high = mid - 1 # low和high就可以表示新序列的范围 elif item > alist[mid]: # 查找的元素在中间元素的右边 low = mid + 1 # low和high就可以表示中间元素右侧的子序列 else: # 查找的元素就是中间元素 find = True break return find def fff(alist,item): find = False for i in alist: if i == item: find = True break return find
l = [1,2,3,4,5,6,7,8] print(find(l,4)) print(fff(l,4))
True True
冒泡排序
1、将乱序序列中的最大值找出，逐一移动到序列最后的位置
2、将步骤一的操作作用n-1次
# 1、将乱序序列中的最大值找出，逐一移动到序列最后的位置 alist = [3,8,5,7,4] def sort(alist): # 找最大值的方式是通过对列表中的元素进行两两比较，值大的元素逐步向后移动 # 序列中有n个元素，两两比较的话，需要比较n-1次 for i in range(len(alist)-1): # 循环n-1次,控制两两比较的次数 if alist[i] > alist[i+1]: # 前面的元素大雨后面的元素，交换两元素的位置 alist[i],alist[i+1] = alist[i+1],alist[i] else: # 如果后面的元素大于前面的元素则不做操作 pass return alist print(sort(alist))
[3, 5, 7, 4, 8]
发现上述代码已经可以将序列中的最大值放到合适的位置，然后我们就可以将上述操作继续作用到n-1个元素对应的新序列，则就可以将n-1个元素对应的最大值放置到了n-1个元素的最后位置。
结论：如果将上述的操作逐步作用n-1次就可以将整个序列变成有序的。
# 1、将乱序序列中的最大值找出，逐一移动到序列最后的位置 # 2、将步骤一的操作作用n-1次 alist = [3,8,5,7,4] def Pop_Sort(alist): for j in range(len(alist)-1): # 外层循环次数递增，内次循环次数递减 # 找最大值的方式是通过对列表中的元素进行两两比较，值大的元素逐步向后移动 # 序列中有n个元素，两两比较的话，需要比较n-1次 for i in range(len(alist)-1-j): # 循环n-1次,控制两两比较的次数 if alist[i] > alist[i+1]: # 前面的元素大雨后面的元素，交换两元素的位置 alist[i],alist[i+1] = alist[i+1],alist[i] else: # 如果后面的元素大于前面的元素则不做操作 pass return alist print(sort(alist))
[3, 5, 7, 4, 8]
选择排序
# 1、将乱序序列中的元素两两比较，找出最大值，直接将最大值放置到序列的最后位置（冒泡排序是逐步移到最后） # 将最大值直接和最后一个元素交换位置 alist = [3,8,5,7,6,2,4] def sort(alist): max_index = 0 # 最大值元素的下标，一开始假设下表为0的元素为最大值 for i in range(len(alist)-1): if alist[max_index] < alist[i+1]: max_index = i+1 # 循环结束后max_index就一定是最大值的下标 alist[len(alist)-1],alist[max_index] = alist[max_index],alist[len(alist)-1] return alist
print(sort(alist))
# 2、将步骤一继续作用n-1次 alist = [3,8,5,7,6,2,4] def Choice_Sort(alist): for j in range(len(alist)-1): max_index = 0 # 最大值元素的下标，一开始假设下表为0的元素为最大值 for i in range(len(alist)-1-j): if alist[max_index] < alist[i+1]: max_index = i+1 # 循环结束后max_index就一定是最大值的下标 alist[len(alist)-1-j],alist[max_index] = alist[max_index],alist[len(alist)-1-j] return alist
print(sort(alist))
[3, 4, 5, 7, 6, 2, 8]
import numpy as np demo = np.random.randint(0,100,50) Pop_Sort(demo)
插入排序
需要将原始序列分成两部分，一部分叫有序部分，一部分叫无序部分
将无序部分中的元素逐一插入到有序部分中
注意：初始情况下，有序部分为乱序序列的第一个元素，无序部分为乱序序列的n-1个元素
乱序序列：[3,8,5,7,6]
[3,,,8,5,7,6] 3就是初始的的有序部分，8,5,7,6就是初始的无序部分
[3,8,,,5,7,6]
[3,5,8,,,7,6]
[3,5,7,8,,,6]
[3,5,6,7,8]
定义一个变量i，i表示的是有序部分的个数&&无序部分第一个元素下标
# step1： # [31, 8,5,7,6] i = 1 # i就是有序部分元素的个数&&无序部分第一个元素下标 #alist[i-1]:有序部分最后一个元素下标 #alist[i]:无序部分第一个元素下标 if alist[i-1] > alist[i]: alist[i],alist[i-1] = alist[i-1],alist[i] # [8,31, 5,7,6]
#step2: i = 2 while i>0: if alist[i-1] > alist[i]: # 循环第一次 alist[i-1],alist[i] = alist[i],alist[i-1] # [8,5,31, 7,6] i -= 1 # 循环继续执行 # [5,8,31, 7,6] else: break
for i in range(1,len(alist)): while i>0: if alist[i-1] > alist[i]: # 循环第一次 alist[i-1],alist[i] = alist[i],alist[i-1] # [8,5,31, 7,6] i -= 1 # 循环继续执行 # [5,8,31, 7,6] else: break
# 完整代码 alsit = [3,8,5,7,6] def Insert_Sort(alist): for i in range(1,len(alist)): while i>0: if alist[i-1] > alist[i]: alist[i-1],alist[i] = alist[i],alist[i-1] i -= 1 else: break return alist
print(Insert_Sort(demo))
[ 3 4 6 7 7 8 10 16 16 16 18 27 27 28 30 30 31 32 33 35 36 39 39 42 43 46 49 55 56 56 56 60 61 64 64 68 68 69 70 71 75 76 84 87 87 88 90 91 93 96]
希尔排序
关键变量：增量gap
gap：初始值为length//2
1、表示分组的组数
2、每一组数据之间按的间隔
插入排序就是增量为1的希尔排序
# 1、写出插入排序 def Insert_Sort(alist): for i in range(1,len(alist)): while i>0: if alist[i-1] > alist[i]: alist[i-1],alist[i] = alist[i],alist[i-1] i -= 1 else: break return alist
# 2、在插入排序中加入锃亮的概念 def Insert_Sort(alist): gap = len(alist)//2 # 插入排序是增量为1的希尔排序 # 下述代码是增量为1，下述代码中的1表示的是增量 # for i in range(1,len(alist)): # while i>0: # if alist[i-1] > alist[i]: # alist[i-1],alist[i] = alist[i],alist[i-1] # i -= 1 # else: # break # 将插入排序中的增量1都换成GAP # 有增量为1变成了增量为GAP for i in range(gap,len(alist)): while i>0: if alist[i-gap] > alist[i]: alist[i-gap],alist[i] = alist[i],alist[i-gap] i -= gap else: break return alist
# 3、在步骤二中进行增量的缩减 def Insert_Sort(alist): gap = len(alist)//2 while gap: for i in range(gap,len(alist)): while i>0: if alist[i-gap] > alist[i]: alist[i-gap],alist[i] = alist[i],alist[i-gap] i -= gap else: break gap //= 2 # 增量缩减 return alist
# 完整代码 def Shell_Sort(alist): gap = len(alist)//2 while gap: for i in range(gap,len(alist)): while i>0: if alist[i-gap] > alist[i]: alist[i-gap],alist[i] = alist[i],alist[i-gap] i -= gap else: break gap //= 2 # 增量缩减 return alist
alist = [3,8,5,7,6] print(Shell_Sort(alist))
[3, 5, 6, 7, 8]
快速排序
基数：默认值是序列中的的一个元素值
核心功能：将乱序序列中比基数小的数值放置到基数左侧，比基数大的数值放置到基数的右侧。基数是存在最中间的数值。
alist = [6,1,2,9,3,4,5,1,10,8]
# 1、核心操作，将基数mid放置到序列中间，使序列左边都是比基数小的，右边都是比基数大的 def Sort(alist): low = 0 # 第一个元素下标 high = len(alist)-1 # 最后一个元素下标 mid = alist[low] # 基数：初始值为序列中的一个数值 while low!=high: # 先偏移high while low<high: if mid<alist[high]: # 向左偏移high high = high - 1 else: # 将high指向的数值放置到左侧的空位 alist[low] = alist[high] break # 向右偏移low while low<high: if mid >alist[low]: low += 1 else: alist[high] = alist[low] break alist[low] = mid return alist
# 2、将步骤一的核心操作递归作用到基数的左右两侧的子序列中 # 如何区分根据基数拆分出的左右序列？可以根据low和high的指向区分不同子序列 # 1、核心操作，将基数mid放置到序列中间，使序列左边都是比基数小的，右边都是比基数大的 def Fast_Sort(alist,left,right): low = left # 第一个元素下标 high = right # 最后一个元素下标 # 结束递归的条件 if low > high: return mid = alist[low] # 基数：初始值为序列中的一个数值 while low != high: # 先偏移high while low < high: if mid <= alist[high]: # 向左偏移high high = high - 1 else: # 将high指向的数值放置到左侧的空位 alist[low] = alist[high] break # 向右偏移low while low < high: if mid >= alist[low]: low += 1 else: alist[high] = alist[low] break alist[low] = mid # 上述操作位核心操作 Fast_Sort(alist,left,low-1) Fast_Sort(alist,high+1,right) return alist
a = [6,2,9,3,4,5,1,10,8] print(Fast_Sort(a,0,len(a)-1))
[1, 2, 3, 4, 5, 6, 8, 9, 10]
def Fast_Sort(alist,left,right): low = left # 第一个元素下标 high = right # 最后一个元素下标 # 结束递归的条件 if low > high: return mid = alist[low] # 基数：初始值为序列中的一个数值 while low != high: # 先偏移high while low < high: if mid <= alist[high]: # 向左偏移high high = high - 1 else: # 将high指向的数值放置到左侧的空位 alist[low] = alist[high] break # 向右偏移low while low < high: if mid >= alist[low]: low += 1 else: alist[high] = alist[low] break alist[low] = mid # 上述操作位核心操作 Fast_Sort(alist,left,low-1) Fast_Sort(alist,high+1,right) return alist import numpy as np alist = np.random.randint(0,100,10) alist = [5,2,3,4,6,2,7] print(Fast_Sort(alist,0,len(alist)-1))
[2, 2, 3, 4, 5, 6, 7]
def squareroot(n):
root = n/2
for i in range(20):
root = (1/2)*(root + (n/root))
return root
squareroot(49999999)
from timeit import Timer
timer1 = Timer('squareroot(4999999)','from __main__ import squareroot')
print(timer1.timeit(1000))
0.0016348999999991065
def kaifang(n):
import math
res = math.sqrt(n)
return res
timer1 = Timer('kaifang(4999999)','from __main__ import kaifang')
print(timer1.timeit(1000))