一、插入排序（Insertion Sort）
实现思路：
插入排序的核心思想是：将数组分为「已排序区间」和「未排序区间」，初始时已排序区间只有第一个元素。然后依次从未排序区间中取出元素，插入到已排序区间的合适位置（保证已排序区间始终有序），重复此过程直到未排序区间为空。
类比生活中整理扑克牌：抓牌时，每抓一张就按大小插入到手中已有序的牌堆里。
`
def insertion_sort(arr):
遍历未排序区间（从第二个元素开始，索引1到末尾）
for i in range(1, len(arr)):# 当前要插入的元素（未排序区间的第一个元素）current = arr[i]# 已排序区间的末尾索引（初始为i-1）j = i - 1# 在已排序区间中找到current的插入位置# 若j >=0且已排序元素大于current，将其右移一位while j >= 0 and arr[j] > current:arr[j + 1] = arr[j] # 元素右移j -= 1# 将current插入到正确位置（j+1是插入索引）arr[j + 1] = current
return arr
`
代码详解：
外层循环 for i in range(1, len(arr))：从索引 1 开始（第一个元素默认有序），依次处理未排序区间的元素。
current = arr[i]：记录当前要插入的元素（避免后续移位时被覆盖）。
内层循环 while j >= 0 and arr[j] > current：从已排序区间的末尾向前遍历，若元素大于current，则将其右移一位（为current腾出位置）。
arr[j + 1] = current：当找到小于等于current的元素（或已遍历完已排序区间），将current插入到该元素的右侧（j+1位置）。
特点：稳定排序（相等元素相对位置不变），
时间复杂度 O(n^2)（最坏 / 平均），
空间复杂度 O(1)（原地排序）。
二、冒泡排序（Bubble Sort）
实现思路：
冒泡排序的核心思想是：重复遍历数组，每次比较相邻的两个元素，若顺序错误则交换它们。每一轮遍历会将最大的元素 “冒泡” 到数组末尾（如同水中气泡上浮），重复n-1轮后数组有序。
优化点：若某一轮遍历中没有发生交换，说明数组已完全有序，可提前退出。
def bubble_sort(arr): n = len(arr) # 外层循环控制需要多少轮（最多n-1轮） for i in range(n - 1): swapped = False # 标记本轮是否发生交换 # 内层循环比较相邻元素（每轮后最大元素已到位，无需再比较） for j in range(n - 1 - i): # 若前一个元素大于后一个，交换它们 if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True # 若本轮无交换，说明数组已有序，提前退出 if not swapped: break return arr
代码详解：
外层循环 for i in range(n - 1)：最多需要n-1轮（每轮确定一个最大元素的位置）。
swapped 标记：用于优化，若某轮未交换元素，说明数组已有序，直接退出。
内层循环 for j in range(n - 1 - i)：每轮比较范围随i增大而减小（因为末尾i个元素已排好序）。
交换操作 arr[j], arr[j + 1] = ...：相邻元素逆序时交换，确保大元素 “上浮” 到右侧。
特点：稳定排序，时间复杂度 (O(n^2))（最坏 / 平均）、(O(n))（最好，已排序时），空间复杂度 (O(1))（原地排序）。
三、选择排序（Selection Sort）
实现思路
选择排序的核心思想是：将数组分为「已排序区间」和「未排序区间」，初始时已排序区间为空。每一轮从未排序区间中找到最小元素，将其与未排序区间的第一个元素交换，此时该元素加入已排序区间，重复n-1轮后数组有序。
类比生活中挑苹果：每次从一堆苹果里挑出最小的，放到已选好的一堆的末尾。
def selection_sort(arr): n = len(arr) # 外层循环控制已排序区间的末尾（最多到n-2，最后一个元素自动有序） for i in range(n - 1): # 记录未排序区间中最小元素的索引（初始假设第一个元素最小） min_index = i # 遍历未排序区间，找到真正的最小元素索引 for j in range(i + 1, n): if arr[j] < arr[min_index]: min_index = j # 将最小元素与未排序区间的第一个元素交换 arr[i], arr[min_index] = arr[min_index], arr[i] return arr
代码详解：
外层循环 for i in range(n - 1)：i 是已排序区间的末尾索引（初始为 0，每轮扩展 1 位）。min_index = i：假设未排序区间的第一个元素（arr[i]）是最小的。
内层循环 for j in range(i + 1, n)：遍历未排序区间的剩余元素，更新min_index为真正的最小元素索引。
交换操作 arr[i], arr[min_index] = ...：将最小元素放到已排序区间的末尾（i位置）。
特点：不稳定排序（相等元素可能因交换改变相对位置），时间复杂度 (O(n^2))（所有情况），空间复杂度 (O(1))（原地排序）。