1. 排序算法
1.1 冒泡排序
冒泡排序是一种基本的排序算法,它的思想是从序列的一端开始比较,并且将小的数逐渐交换到该段序列的头部。排序的过程中,每次将未排序的数列中的最大值交换到数列的最后。下面是冒泡排序的Python代码实现:
def bubble_sort(nums):
for i in range(len(nums)):
for j in range(len(nums)-1-i):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
return nums
在上述代码中,我们使用了嵌套的for循环,外层的循环用于控制需要比较的轮数,内层循环则用于对当前未确定位置值的序列从前往后进行两两比较,把较大的值往后移,遍历完成后,最大值就移动到最后,然后再对前两个数进行比较,以此类推,知道整个序列有序。
1.2 快速排序
快速排序是一种排序算法的高级表现,它采用分治法来实现。基本思路是选择一个基准元素,将数组分成两个子数组,比基准值小的元素放到左边的子数组中,比基准值大的元素放到右边的子数组中。然后递归地对两个子数组进行排序,直到整个序列有序。下面是快速排序的实现:
def quick_sort(nums):
if len(nums) <= 1:
return nums
pivot = nums[len(nums)//2]
left = [x for x in nums if x < pivot]
middle = [x for x in nums if x == pivot]
right = [x for x in nums if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
在快速排序中,我们首先设定基准值pivot,然后将整个数列分成了小于等于pivot和大于pivot的两个部分。然后递归地对两个子数组进行排序。
2. 查找算法
2.1 二分查找
二分查找又称为折半查找,是一种十分高效的查找算法。它采取的是不断缩小查找范围的方法,从而提高查找效率。二分查找要求序列必须有序,可以针对有序数组或链表进行操作。下面是二分查找的Python实现代码:
def binary_search(nums, target):
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
high = mid - 1
else:
low = mid + 1
return -1
上述代码中通过逐步将查找范围缩小的方法,将整个数组划分成左右两个部分,在每一轮比较中,向中间靠拢,最终找到目标元素。
2.2 哈希查找
哈希查找也称为散列查找,是一种通过哈希函数的计算快速定位到散列表中的数据集合的方法,通常情况下可以做到O(1)的时间复杂度。下面是哈希查找的Python代码实现:
def hash_table(data):
hash_table = [None]*1000
for item in data:
index = hash(item) % 1000
if hash_table[index]:
hash_table[index].append(item)
else:
hash_table[index] = [item]
return hash_table
def hash_search(data, target):
hash_table_data = hash_table(data)
index = hash(target) % 1000
if hash_table_data[index]:
return target in hash_table_data[index]
else:
return False
在上述代码中,我们定义了一个散列函数,将字符串数据转换为整型数据,用散列表存储数据,然后在查找的时候,使用散列函数得到目标元素的索引值,根据索引值查找散列表中的元素,最终得到查找结果。
3. 图论算法
3.1 最短路径算法
最短路径算法是一类图论算法,用于求解两个顶点之间的最短路径。Dijkstra算法和A*算法是常用的最短路径算法。下面是Dijkstra算法的Python实现代码:
def dijkstra(graph, start, end):
shortest_distance = {}
predecessor = {}
unseenNodes = graph
infinity = float('inf')
path = []
for node in unseenNodes:
shortest_distance[node] = infinity
shortest_distance[start] = 0
while unseenNodes:
currentNode = None
for node in unseenNodes:
if currentNode == None:
currentNode = node
elif shortest_distance[node] < shortest_distance[currentNode]:
currentNode = node
for childNode, weight in graph[currentNode].items():
if weight + shortest_distance[currentNode] < shortest_distance[childNode]:
shortest_distance[childNode] = weight + shortest_distance[currentNode]
predecessor[childNode] = currentNode
unseenNodes.pop(currentNode)
currentNode = end
while currentNode != start:
try:
path.insert(0, currentNode)
currentNode = predecessor[currentNode]
except KeyError:
break
path.insert(0, start)
if shortest_distance[end] != infinity:
return shortest_distance[end], path
else:
return "No path"
在Dijkstra算法中,我们首先将所有的顶点标记为未访问,然后从起点开始,在未访问的顶点中选出距离起点最近的顶点,然后以该顶点为中间点对边进行松弛操作,即更新与该顶点相邻顶点的距离,直到更新所有的顶点。最后按照访问的顺序记录下路径信息。
3.2 最小生成树算法
最小生成树算法是一类用于在带权连通图中找到与所有顶点相连的边权值最小的生成树的算法。Prim算法和Kruskal算法是常用的最小生成树算法。下面是Prim算法的Python实现代码:
def prim(graph, start):
visited = set()
unvisited = set(graph.keys())
unvisited.remove(start)
path = []
current_node = start
while unvisited:
all_edges = []
for destination, weight in graph[current_node].items():
if destination in unvisited:
all_edges.append((current_node, destination, weight))
min_edge = sorted(all_edges, key=lambda x: x[2])[0]
unvisited.remove(min_edge[1])
visited.add(current_node)
path.append(min_edge)
current_node = min_edge[1]
return path
在Prim算法中,我们将图分成已访问和未访问两部分,然后从任意一个起点开始,将他加入已访问的部分中,然后再取出与已访问部分相连的未访问顶点的权值最小的边,加入到已访问部分,并维护下一次需要比较的边的候选项,重复这个过程直到所有的边都遍历后结束,在整个过程中维护边权值最小的情况。