（一）排序算法
简述：
在 Python 中，有多种常用的排序算法，下面为你详细介绍几种常见的排序算法及其原理、实现代码、时间复杂度以及稳定性等特点，并对比它们适用的场景。
冒泡排序（Bubble Sort）
- 原理：它重复地遍历要排序的数列，一次比较两个相邻元素，如果它们的顺序错误（比如在升序排序中，前面的元素比后面的大）就把它们交换过来。遍历数列的工作是重复进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢 “浮” 到数列的顶端，就如同水底的气泡逐渐向上冒一样。例如，第一轮排序从第一个元素开始，比较相邻的两个元素，如果第一个比第二个大（升序排序），则交换它们两个；对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，这步做完后，最后的元素会是最大的数。然后进行第二轮排序，对所有的元素（除了最后一个）重复以上的步骤，持续每轮次的操作，每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
- 实现代码：
| def bubble_sort(arr): n = len(arr) # 遍历所有数组元素 for i in range(n): # Last i elements are already in place for j in range(0, n - i - 1): # 遍历数组从0到n-i-1 # 交换如果元素找到的元素比下一个大 if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr |
- 时间复杂度：平均和最坏情况都是，其中是数组的长度，最好情况（数组本身已经有序）时间复杂度为。不过通常我们关注的是平均和最坏情况，这使得它在处理大数据量排序时效率相对较低。
- 稳定性：冒泡排序是稳定的排序算法，即相等的元素在排序后仍然保持原有的顺序。
- 适用场景：适用于小规模数据集，因为其简单性和易于实现；也适合在教学和学习中使用，帮助初学者掌握排序的基本概念；当排序算法需要是稳定的（即相等元素的相对顺序在排序前后不变）时，冒泡排序是一个很好的选择。
插入排序（Insertion Sort）
- 原理：以列表的第一个数为基数，随机抽取剩余数中一个作为随机数，与基数进行比较排序，再随机抽取剩余数中的一个作为随机数，与前面的小列表进行插入排序，依次类推。简单来说，就是将未排序数据项中选择一个数据项插入到已排序数据项中合适的位置，不断重复这个过程直到所有数据被排好序。比如，在一个已经有部分元素有序的列表中，要插入一个新元素，就从后往前依次比较已排序的元素，找到合适的位置插入新元素，使得插入后这部分仍然有序。
- 实现代码：
| def insert_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr |
- 时间复杂度：最坏情况下（数组完全逆序），时间复杂度为；最好情况下（数组已经是有序的），时间复杂度为。
- 稳定性：插入排序是稳定的排序算法。
- 适用场景：对于基本有序的数据集合，插入排序的效率相对较高，因为它每次只需要比较和移动较少的数据；同样也适用于小规模数据排序的情况。
选择排序（Selection Sort）：
- 原理：以列表的第一个位置的数为基数，与剩余的数中最小的数进行比较，如果基数比最小的数要大，那么交换两个数的位置，否则位置不变。然后再以第二个位置的数为基数，与无序区中的最小数进行比较，如果基数比最小的数要大，那么交换两个数的位置，否则位置不变，以此类推。也就是从个未排序的数据项中选出最小数（这里假设按照升序排列），再从剩下的个未排序的数据项中选出最小数，不断重复此过程，直到所有数被排好序为止。
- 实现代码：
| def selection_sort(arr): for i in range(len(arr) - 1): min_id = i for j in range(i + 1, len(arr)): if arr[j] < arr[min_id]: min_id = j arr[i], arr[min_id] = arr[min_id], arr[i] return arr |
- 时间复杂度：无论最好、平均还是最坏情况，时间复杂度均为。
- 稳定性：选择排序是不稳定的排序算法，例如在排序过程中相等元素的相对顺序可能会改变。
- 适用场景：虽然其时间复杂度较高，但实现相对简单，在对数据规模较小且对稳定性要求不高的情况下可以使用。
快速排序（Quick Sort）
- 原理：是一种分治的排序算法。它将一个数组分成两个子数组，先随意地取数组中的一个元素（通常取第一个或最后一个元素等作为基准元素，这里以第一个元素为例）作为切分元素（即那个将会被排定的元素），然后从数组的左端开始向右扫描直到找到一个大于等于它的元素，再从数组的右端开始向左扫描直到找到一个小于等于它的元素，这两个元素是没有排定的，因此交换它们的位置，如此继续，当两个指针相遇时，将切分元素和左子元素最右侧的元素交换然后返回这个位置索引，这样就把数组分成了两部分，左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素，然后递归地对这两部分进行排序，最终合并得到有序数组。
- 实现代码：
| def quick_sort(arr, left, right): if left < right: pivot = arr[left] i = left j = right while i < j: while i < j and arr[j] >= pivot: j -= 1 arr[i] = arr[j] while i < j and arr[i] <= pivot: i += 1 arr[j] = arr[i] arr[i] = pivot quick_sort(arr, left, i - 1) quick_sort(arr, i + 1, right) return arr |
- 时间复杂度：平均时间复杂度为，但在最坏情况下（例如数组已经有序，每次选取的基准元素导致划分极度不平衡），时间复杂度会退化为。
- 稳定性：快速排序是不稳定的排序算法。
- 适用场景：适用于处理大型数据集，其分治思想和原地排序特性使得在实践中通常比较快速，是实际应用中较为常用的高效排序算法之一。
归并排序（Merge Sort）：
- 原理：体现的是一种分治思想（Divide and conquer）。将数组一分为二，对每部分进行递归式地排序，然后合并两个部分。具体来说，先把原数组不断二分直至单个元素，再进行合并排序。在合并过程中，给出原数组，比较划分后的两部分子数组（这两部分子数组各自是有序的）的首元素，将较小值赋到新的合并数组对应位置，然后对相应的下标进行递增，重复这个过程，直到比较完全部元素，最终得到有序数组。
- 实现代码：
| def merge_sort(arr): if len(arr) > 1: mid = len(arr) // 2 left_half = arr[:mid] right_half = arr[mid:] merge_sort(left_half) merge_sort(right_half) i = j = k = 0 while i < len(left_half) and j < len(right_half): if left_half[i] < right_half[j]: arr[k] = left_half[i] i += 1 else: arr[k] = right_half[j] j += 1 k += 1 while i < len(left_half): arr[k] = left_half[i] i += 1 k += 1 while j < len(right_half): arr[k] = right_half[j] j += 1 k += 1 return arr |
- 时间复杂度：时间复杂度稳定为。
- 稳定性：归并排序是稳定的排序算法。
- 适用场景：适合对稳定性要求较高的情况，因为它能保持相同元素在排序前后的相对位置不变；虽然时间复杂度稳定，但需要额外的内存空间来存储子数组，所以更适用于对内存占用有限制要求不是特别苛刻的场景下对数据进行排序。
堆排序（Heap Sort）
- 原理：利用了二叉堆这种数据结构的特性来进行排序。首先将数组构建成一个最大堆（对于升序排序而言，最大堆就是每个节点的值都大于或等于其子节点的值；如果是降序排序则构建最小堆），然后把堆顶元素（最大值）与堆的最后一个元素交换，此时最大元素就到了数组的末尾，接着对剩下的元素重新调整为最大堆，重复这个过程，直到整个数组有序。
- 实现代码：
| def heapify(arr, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr[i] < arr[l]: largest = l if r < n and arr[largest] < arr[r]: largest = r if largest!= i: arr[i], arr[largest] = arr[largest], arr[i] heapify(arr, n, largest) def heap_sort(arr): n = len(arr) for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] heapify(arr, i, 0) return arr |
- 时间复杂度：时间复杂度为，无论是最好、平均还是最坏情况，时间复杂度都比较稳定。
- 稳定性：堆排序是不稳定的排序算法。
- 适用场景：它是一种高效的原地排序算法，不需要额外的大量空间来辅助排序，适用于对空间复杂度有一定要求，同时希望能有较稳定时间复杂度表现的数据排序场景。
对比不同排序算法适用的场景：
- 对于小规模数据集，像冒泡排序、插入排序、选择排序这类简单的排序算法都可以胜任，它们实现简单，易于理解和调试。其中如果需要稳定排序，冒泡排序和插入排序更合适；若对稳定性没有要求，选择排序也可考虑。
- 当处理大规模数据集时，如果对稳定性有要求，归并排序是不错的选择；若更注重平均时间复杂度，希望排序速度较快且对稳定性要求不高，快速排序通常表现良好；而堆排序则在对空间复杂度有一定限制，同时又希望有稳定时间复杂度保障的情况下可以优先使用。
（二）搜索算法
简述：
在 Python 中，常见的搜索算法有线性搜索、二分搜索、深度优先搜索、广度优先搜索等，下面将为你讲解各算法的思路、实现代码、复杂度分析，以及它们在不同数据结构及应用场景中的使用情况。
线性搜索（Linear Search）：
- 思路：也叫顺序搜索，是一种最简单的搜索算法。它从数据结构（比如数组、列表等）的第一个元素开始，逐个比较元素与要查找的目标元素是否相等，直到找到目标元素或者遍历完整个数据结构为止。例如，在一个包含多个整数的列表中查找特定的整数，就按顺序依次查看每个元素是否是要找的那个数。
- 实现代码：
| def linear_search(arr, target): for index, element in enumerate(arr): if element == target: return index return -1 |
- 复杂度分析：时间复杂度在最好情况下（要查找的元素恰好在第一个位置）为，但平均和最坏情况下（要查找的元素在最后一个位置或者不存在于数据结构中）时间复杂度为，其中是数据结构中元素的个数。空间复杂度为，因为它只需要有限的额外空间来进行操作。
- 使用情况：适用于数据结构没有特定顺序，或者数据规模较小的情况。比如在一个无序的小型列表中查找元素时可以使用线性搜索。
二分搜索（Binary Search）：
- 思路：又称折半查找，这种算法适用于有序数组中的查找操作。首先确定整个查找区间的中间位置，然后将待查找的值与数组中中间位置的值进行比较，如果目标值小于中间位置的值，则在数组的左半部分继续查找，即新的查找区间是左半区间；如果目标值大于中间位置的值，则在数组的右半部分继续查找，即新的查找区间是右半区间；如果目标值等于中间位置的值，则查找成功，返回该位置的下标；如果查找区间为空，则说明查找失败，返回 -1。例如，在一个已经从小到大排好序的整数数组中查找特定整数，通过不断缩小查找范围来定位目标元素。
- 实现代码：
| def binary_search(arr, left, right, target): if left > right: return -1 mid = (left + right) // 2 if arr[mid] == target: return mid elif target < arr[mid]: return binary_search(arr, left, mid - 1, target) else: return binary_search(arr, mid + 1, right, target) |
- 复杂度分析：时间复杂度为，因为每次比较都能将查找区间缩小一半，效率相对较高。空间复杂度为（递归实现时，递归栈的深度取决于树的高度，即），如果采用非递归实现，空间复杂度可以优化到。
- 使用情况：要求数据结构（通常是数组）必须是有序的，常用于查找有序数据集中的元素，比如在有序的数据库索引或者排好序的列表中查找特定值时非常高效。
深度优先搜索（Depth First Search， DFS）：
- 思路：是一种递归的图遍历算法（当然也可以用于树等其他类似的数据结构遍历），其基本思想是从起始节点开始，沿着一条路径访问图中的节点，直到无法继续访问为止（比如遇到没有未访问过的邻接点了），然后回溯到上一个节点，继续访问其他的路径，直到遍历完所有节点。例如在一个表示地图的图结构中，从某个地点出发，一直沿着一条路走，走到头了再返回上一个岔路口去走其他没走过的路，以此类推，直到走过所有能到达的地点。
- 实现代码：
| def dfs(graph, node, visited): if node not in visited: visited.append(node) for neighbor in graph[node]: dfs(graph, neighbor, visited) return visited |
这里的 graph 通常用字典来表示，键表示节点，值表示该节点的邻接点列表；node 是起始节点，visited 是一个列表用来记录已经访问过的节点。
- 复杂度分析：时间复杂度取决于图的节点数 V 和边数 E，对于邻接表表示的图，时间复杂度为；对于邻接矩阵表示的图，时间复杂度为。空间复杂度为，因为在最坏情况下需要记录所有的节点（递归栈的深度最多为节点个数）。
- 使用情况：常用于查找图中两个节点之间是否存在路径、查找图中的连通分量、判断图中是否存在环等场景。比如在分析网络拓扑结构中节点的连通性，或者在游戏地图中寻找从一个地点到另一个地点的可行路径（不要求是最短路径）等情况。
广度优先搜索（Breadth First Search， BFS）：
- 思路：是一种非递归的图遍历算法，其基本思想是从起始节点开始，依次访问其所有邻居节点，然后再访问邻居节点的邻居节点，也就是一层一层地向外扩展访问，直到遍历完所有节点为止。形象地说，就好比在一个迷宫中，从起点开始，先把起点周围一圈的通道都探索一遍，再去探索这些通道对应的下一圈通道，以此类推，直到走遍整个迷宫。
- 实现代码：
| from collections import deque def bfs(graph, start): visited = [] queue = deque([start]) while queue: node = queue.popleft() if node not in visited: visited.append |
