常见排序算法
1. 冒泡排序
基本思想：重复遍历数组，每次比较相邻元素，若顺序错误则交换，直到无交换操作（数组有序）。
复杂度：时间复杂度平均 O (n²)、最坏 O (n²)、最好 O (n)（优化后）；空间复杂度 O (1)。
稳定性：稳定（相等元素不交换）。
1. 普通冒泡排序
def bubble_sort1(arr:List[int]) -> List[int]:
for i in range(len(arr)):
for j in range(len(arr)-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
2. 标记优化版
增加标记检测内层循环是否进行排序，如果没有则说明当前数组已经有序，后续外层循环就无需进行
def bubble_sort2(arr:List[int]) -> List[int]:
for i in range(len(arr)):
swapped = False
for j in range(len(arr)-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped:
break
return arr
2. 选择排序
基本思想：每次从待排序部分选最小（或最大）元素，放到已排序部分的末尾。
复杂度：时间复杂度 O (n²)（无论有序与否）；空间复杂度 O (1)。
稳定性：不稳定（如 [2,2,1]，第一个 2 会与 1 交换，破坏原有顺序）。
def selection_sort(arr):
for i in range(len(arr)):
min_index = i # 假设第一个元素为最小值
for j in range(i+1, len(arr)):
if arr[j] < arr[min_index]: # 遍历剩余元素找出最小值
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i] # 将最小值移到前面
return arr
3. 插入排序
基本思想：类似整理扑克牌，将元素逐个插入到已排序部分的合适位置。
复杂度：时间复杂度平均 O (n²)、最坏 O (n²)、最好 O (n)（接近有序时）；空间复杂度 O (1)。
稳定性：稳定。
def insertion_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
4. 快速排序
基本思想：分治法。选一个 "基准"，将数组分为两部分（左小右大），再递归排序两部分。
复杂度：时间复杂度平均 O (nlogn)、最坏 O (n²)（如有序数组选首位为基准）；空间复杂度 O (logn)~O (n)（递归栈）。
稳定性：不稳定。
def quick_sort(arr):
if len(arr) <= 0: # 终止条件：数组长度<=1直接返回
return arr
piovt = arr[0] # 基准
left = [x for x in arr[1:] if x <= piovt] # 左部分
right = [x for x in arr[1:] if x >= piovt] # 右部分
return quick_sort(left) + [piovt] + quick_sort(right) # 递归合并
5. 归并排序
基本思想：分治法。将数组拆分为两半，分别排序后合并为一个有序数组。
复杂度：时间复杂度 O (nlogn)（无论有序与否）；空间复杂度 O (n)（需临时数组）。
稳定性：稳定。
def merge_sort(arr):
"""归并排序主函数：递归拆分并合并数组"""
# 递归终止条件：数组长度 <= 1 时，天然有序，直接返回
if len(arr) <= 1:
return arr
# 拆分：将数组从中间分为左右两部分
mid = len(arr) // 2 # 中间索引
left = merge_sort(arr[:mid]) # 递归排序左半部分
right = merge_sort(arr[mid:]) # 递归排序右半部分
# 合并：将两个有序子数组合并为一个有序数组
return merge(left, right)
def merge(left, right):
"""合并两个有序子数组为一个有序数组"""
result = [] # 临时数组，存储合并后的结果
i = j = 0 # i 是 left 数组的指针，j 是 right 数组的指针
# 比较两个子数组的元素，按顺序放入临时数组
while i < len(left) and j < len(right):
if left[i] <= right[j]: # 保留稳定性（相等元素左在前）
result.append(left[i])
i += 1 # 移动左指针
else:
result.append(right[j])
j += 1 # 移动右指针
# 处理剩余元素（其中一个子数组已遍历完）
result.extend(left[i:]) # 若 left 有剩余，全部加入
result.extend(right[j:]) # 若 right 有剩余，全部加入
return result
发表评论