In [ ]:
# 工作分配
from pandas import DataFrame
import numpy as np
data = np.array([[1, 2, 3, 4], [4, 5, 6, 7], [7, 8, 9, 10]])
print(data)
n1 = np.random.randint(10, size=5)
print(n1)
list = []
for i in range(5):
list.append(np.random.randint(10, size=5))
print(list)
data = np.array(list)
print(data)
# print(np.max(data[1]))
In [5]:
# 快速排序 版本一
def swap(L, a, b):
tmp = L[a]
L[a]= L[b]
L[b] = tmp
def quick_sort(L, low, high):
if low >= high:
return
tmp = L[low];
left = low
right = high
while left < right:
while right > left and L[right] >= tmp:
right -= 1
while left < right and L[left] <= tmp:
left += 1
if left < right:
swap(L, left, right)
if low != left:
swap(L, left, low)
quick_sort(L, low, left-1)
quick_sort(L, left+1, high)
if __name__ == "__main__":
# 读取n个数
n = int(input())
# 输入列表
L = list(map(int, input().split()))
print("排序前:")
print(L)
print("\n")
quick_sort(L, 0, n-1)
print("排序后:")
print(L)
print("\n")
In [22]:
# 快速排序 版本二
def quick_sort(arr):
if len(arr) < 2:
return arr
else:
pivot = arr[0]
less = [i for i in arr[1:] if i <= pivot] # 由所有小于基准值的元素组成的子数组
greater = [i for i in arr[1:] if i > pivot] # 由所有大于基准值的元素组成的子数组
return quick_sort(less) + [pivot] + quick_sort(greater)
print(quick_sort([1, 8, 5, 33, 2, 3, 5, 7]))
In [41]:
# 堆排序
def swap(L, a, b):
tmp = L[a]
L[a]= L[b]
L[b] = tmp
# 向下调整结点
def sift_down(L, n, i):
t = i;
flag = 0
# 左右结点的判断
while i <= n/2 and flag == 0:
if L[i] > L[i*2]:
t = i*2
else:
t = i
if 2*i+1 <= n:
if L[t] > L[i*2+1]:
t = i*2+1
if i != t:
swap(L, i, t)
i = t;
else:
flag = 1
# 向上调整结点
def sift_up(L, i):
k = i
flag = 0
if i == 1:
return
# 叶子结点和根结点的判断
while k > 1 and flag == 0:
if L[k] > L[k/2]:
swap(L, k, k/2)
k = k/2
else:
flag = 1
def create_heap(L, n):
i = int(n/2)
while i >=1:
sift_down(L, n, i)
i -= 1
def heap_sort(L, n):
k = n
while k > 0:
swap(L, 1, k)
k -= 1
sift_down(L, k, 1)
if __name__ == "__main__":
k = 0
# 读取n个数
n = int(input())
# 输入列表
input_L = list(map(int, input().split()))
L = [""] + input_L
# 创建堆序列
create_heap(L, n)
print("排序前:")
print(L)
print("\n")
heap_sort(L, n)
print("排序后:")
print(L)
print("\n")
In [ ]:
#队列
class PQueue(object):
def __init__(self):
self.list = []
self.front = 0;
self.rear = 0;
self.lengthSize = 0;
def deqeue(self):
In [97]:
# 类结构的堆排序
class DLinkHeap(object):
def __init__(self, list=None, N = 0):
self.dList = list
self.lengthSize = N
# 插入数据
def insert_heap(self, data):
self.dList.append(data)
self.lengthSize += 1
# 初始化堆结构
def init_heap(self):
n = self.lengthSize
for i in range(n):
self.sift_down(i)
# 交换数据
def swap(self, a, b):
tmp = self.dList[a]
self.dList[a] = self.dList[b]
self.dList[b] = tmp
# 向下调整节点
def sift_down(self, size):
n = size
t = 0
tmp_pos = 0
# 注意python的/运算，是取浮点数
while t < int(n/2):
if self.dList[t] > self.dList[2*t+1]:
tmp_pos = 2*t+1
else:
tmp_pos = t
if 2*t+2 < n:
if self.dList[tmp_pos] > self.dList[2*t+2]:
tmp_pos = 2*t+2
if t != tmp_pos:
self.swap(tmp_pos, t)
t = tmp_pos
else:
break
# 向上调整节点
def sift_up(self, size):
n = size
i = n - 1
flag = 0
while i > 0 and flag == 0:
parent_i = int(i/2)
if self.dList[i] < self.dList[parent_i]:
self.swap(i, parent_i)
i = parent_i
else:
flag = 1
# 堆排序
def heap_sort(self):
n = self.lengthSize
while n > 0:
self.swap(0, n-1)
n -= 1
self.sift_down(n)
# 打印堆数据
def print_heap(self, size):
for idx in range(size):
print(self.dList[idx], end=" ")
print()
if __name__ == "__main__":
k = 0
# 读取n个数
n = int(input())
# 输入列表
input_L = list(map(int, input().split()))
L = input_L
dLinkHeap = DLinkHeap(L, n)
dLinkHeap.init_heap()
dLinkHeap.print_heap(n)
print("-----after sort-----")
dLinkHeap.heap_sort()
dLinkHeap.print_heap(n)
In [5]:
# enum.Enum 枚举类型
from collections import namedtuple
from enum import Enum
class Species(Enum):
cat = 1
dog = 2
horse = 3
aardvark = 4
butterfly = 5
owl = 6
platypus = 7
dragon = 8
unicorn = 9
kitten = 1
puppy = 2
cat = Species.cat
dog = Species.dog
print(cat.value)
print(dog.value)
In [13]:
# 随机数生成
import random
for i in range(40):
print(random.randrange(0,100), end=" ")
In [18]:
# 选择排序
# 比较慢的排序
def find_smallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
def selection_sort(arr):
newArr = []
for i in range(len(arr)-1, -1, -1):
smallest = find_smallest(arr)
newArr.append(arr.pop(smallest))
return newArr
print(selection_sort([5,3,6,2,10]))
In [ ]:
def count_down(i):
if i <= 0: # 基线条件
return
else: # 递归条件
count_down(i-1)
In [ ]:
# 寻找芒果销售商
graph = {}
graph['you'] = ['alice', 'bob', 'claire']
graph['bob'] = ['anuj', 'peggy']
graph['alice'] = ['peggy']
graph['claire'] = ['thom', 'jonny']
graph['anuj'] = []
graph['peggy'] = []
graph['thom'] = []
graph['jonny'] = []
from collections import deque
def person_is_seller(name):
return name[-1] == 'm'
def search(name):
searchQueue = deque() # 创建一个队列
searchQueue += graph[name] # 将你的邻居都加入到这个搜索队列中
searched = []
while searchQueue:
person = searchQueue.popleft() # 就取出其中的第一个人
if person not in searched:
if person_is_seller(person): # 检查这个人是否是芒果销售商
print(person + ' is a mango seller!')
return True
else:
searchQueue += graph[person] # 不是芒果销售商，将这个人的朋友都加入到搜索队列
searched.append(person) # 将这个人标记为检查过
return False # 如果到达这里，说明队列中没有芒果销售商
search('you')
In [52]:
# 寻找拓扑图测试
graph = {}
graph['起床'] = ['锻炼', '刷牙', '打包午餐']
graph['锻炼'] = ['洗澡']
graph['洗澡'] = ['穿衣服']
graph['刷牙'] = ['吃早餐']
graph['吃早餐'] = []
graph['打包午餐'] = []
graph['穿衣服'] = []
from collections import deque
def person_is_seller(name):
if len(graph[name]) == 0:
return True
return False
def search(name):
searchQueue = deque() # 创建一个队列
searchQueue += graph[name] # 将你的邻居都加入到这个搜索队列中
searched = []
while searchQueue:
person = searchQueue.popleft() # 就取出其中的第一个人
if person not in searched:
if person_is_seller(person): # 检查这个人是否是芒果销售商
print(person + ' is a mango seller!')
#return True
else:
searchQueue += graph[person] # 不是芒果销售商，将这个人的朋友都加入到搜索队列
searched.append(person) # 将这个人标记为检查过
return False # 如果到达这里，说明队列中没有芒果销售商
search('起床')
Out[52]:
In [55]:
# Dijkstra算法
# 图表
graph = {}
graph['start'] = {}
graph['start']['a'] = 6
graph['start']['b'] = 2
graph['a'] = {}
graph['a']['fin'] = 1
graph['b'] = {}
graph['b']['a'] = 3
graph['b']['fin'] = 5
graph['fin'] = {} # 终点没有任何邻居
print(graph['start'].keys())
# 开销表
infinity = float("inf")
costs = {}
costs['a'] = 6
costs['b'] = 2
costs['fin'] = infinity
# 散列表
parents = {}
parents['a'] = 'start'
parents['b'] = 'start'
parents['fin'] = None
processed = []
def find_lowest_cost_node(costs):
lowestCost = float('inf')
lowestCostNode = None
for node in costs: # 遍历所有的节点
cost = costs[node]
if cost < lowestCost and node not in processed: # 如果当前节点的开销更低且未处理过，
lowestCost = cost # 将其视为开销最低的节点
lowestCostNode = node
return lowestCostNode
node = find_lowest_cost_node(costs) # 在末处理的节点中找出开销最小的节点
while node is not None:
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys(): # 遍历当前节点的所有邻居
newCost = cost + neighbors[n]
if costs[n] > newCost: # 如果当前节点前往该邻居更近
costs[n] = newCost # 更新该邻居的开销
parents[n] = node # 同时将该邻居的父节点设置为当前节点
processed.append(node) # 将当前节点标记为处理过
node = find_lowest_cost_node(costs) # 找出接下来要处理的节点，并循环
In [ ]: