1. 冒泡排序 (Bubble Sort)
def bubble_sort(arr):
"""
冒泡排序：重复遍历数组，比较相邻元素，将较大的元素向后移动
时间复杂度：O(n²)，空间复杂度：O(1)
"""
n = len(arr)
arr_copy = arr.copy() # 避免修改原数组
for i in range(n):
# 优化：如果某次遍历没有发生交换，说明已经有序
swapped = False
for j in range(0, n - i - 1):
if arr_copy[j] > arr_copy[j + 1]:
arr_copy[j], arr_copy[j + 1] = arr_copy[j + 1], arr_copy[j]
swapped = True
if not swapped:
break
return arr_copy2. 选择排序 (Selection Sort)
def selection_sort(arr):
"""
选择排序：每次从未排序部分选择最小元素放到已排序部分末尾
时间复杂度：O(n²)，空间复杂度：O(1)
"""
n = len(arr)
arr_copy = arr.copy()
for i in range(n):
# 找到未排序部分的最小元素索引
min_idx = i
for j in range(i + 1, n):
if arr_copy[j] < arr_copy[min_idx]:
min_idx = j
# 交换到已排序部分末尾
arr_copy[i], arr_copy[min_idx] = arr_copy[min_idx], arr_copy[i]
return arr_copy3. 插入排序 (Insertion Sort)
def insertion_sort(arr):
"""
插入排序：将每个元素插入到已排序部分的适当位置
时间复杂度：O(n²)，空间复杂度：O(1)
适用于小规模数据或基本有序的数据
"""
n = len(arr)
arr_copy = arr.copy()
for i in range(1, n):
key = arr_copy[i]
j = i - 1
# 将大于key的元素向后移动
while j >= 0 and arr_copy[j] > key:
arr_copy[j + 1] = arr_copy[j]
j -= 1
arr_copy[j + 1] = key
return arr_copy4. 希尔排序 (Shell Sort)
def shell_sort(arr):
"""
希尔排序：插入排序的改进版，使用增量序列分组排序
时间复杂度：O(n log² n)，空间复杂度：O(1)
"""
n = len(arr)
arr_copy = arr.copy()
gap = n // 2
while gap > 0:
# 对每个子序列进行插入排序
for i in range(gap, n):
temp = arr_copy[i]
j = i
while j >= gap and arr_copy[j - gap] > temp:
arr_copy[j] = arr_copy[j - gap]
j -= gap
arr_copy[j] = temp
gap //= 2
return arr_copy5. 归并排序 (Merge Sort)
def merge_sort(arr):
"""
归并排序：分治法，将数组分成两半分别排序，再合并
时间复杂度：O(n log n)，空间复杂度：O(n)
"""
if len(arr) <= 1:
return arr.copy()
# 分割
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
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:])
result.extend(right[j:])
return result6. 快速排序 (Quick Sort)
def quick_sort(arr):
"""
快速排序：选择基准元素，将小于基准的放左边，大于的放右边，递归排序
时间复杂度：平均O(n log n)，最坏O(n²)，空间复杂度：O(log n)
"""
if len(arr) <= 1:
return arr.copy()
arr_copy = arr.copy()
_quick_sort_recursive(arr_copy, 0, len(arr_copy) - 1)
return arr_copy
def _quick_sort_recursive(arr, low, high):
"""快速排序的递归实现"""
if low < high:
# 分区操作，返回基准元素的位置
pi = _partition(arr, low, high)
# 递归排序左右两部分
_quick_sort_recursive(arr, low, pi - 1)
_quick_sort_recursive(arr, pi + 1, high)
def _partition(arr, low, high):
"""分区函数：选择最后一个元素作为基准"""
pivot = arr[high]
i = low - 1 # 小于基准的元素的边界
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
# 将基准放到正确位置
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 17. 堆排序 (Heap Sort)
def heap_sort(arr):
"""
堆排序：利用堆数据结构进行排序
时间复杂度：O(n log n)，空间复杂度：O(1)
"""
n = len(arr)
arr_copy = arr.copy()
# 构建最大堆
for i in range(n // 2 - 1, -1, -1):
_heapify(arr_copy, n, i)
# 逐个提取元素
for i in range(n - 1, 0, -1):
# 将当前最大值（堆顶）移到末尾
arr_copy[0], arr_copy[i] = arr_copy[i], arr_copy[0]
# 调整剩余元素为最大堆
_heapify(arr_copy, i, 0)
return arr_copy
def _heapify(arr, n, i):
"""维护堆的性质"""
largest = i # 初始化最大元素索引
left = 2 * i + 1
right = 2 * i + 2
# 左子节点存在且大于根节点
if left < n and arr[left] > arr[largest]:
largest = left
# 右子节点存在且大于当前最大值
if right < n and arr[right] > arr[largest]:
largest = right
# 如果最大值不是根节点
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
_heapify(arr, n, largest)8. 计数排序 (Counting Sort)
def counting_sort(arr):
"""
计数排序：统计每个值出现的次数，适用于整数且范围不大
时间复杂度：O(n + k)，k为值范围，空间复杂度：O(k)
"""
if not arr:
return []
arr_copy = arr.copy()
# 找到数组中的最大值和最小值
max_val = max(arr_copy)
min_val = min(arr_copy)
range_size = max_val - min_val + 1
# 计数数组
count = [0] * range_size
output = [0] * len(arr_copy)
# 统计每个值出现的次数
for num in arr_copy:
count[num - min_val] += 1
# 计算累积计数
for i in range(1, len(count)):
count[i] += count[i - 1]
# 构建输出数组（稳定排序）
for num in reversed(arr_copy):
idx = count[num - min_val] - 1
output[idx] = num
count[num - min_val] -= 1
return output9. 桶排序 (Bucket Sort)
def bucket_sort(arr, bucket_size=5):
"""
桶排序：将元素分配到多个桶中，每个桶单独排序
时间复杂度：平均O(n + k)，空间复杂度：O(n * k)
"""
if not arr:
return []
arr_copy = arr.copy()
min_val = min(arr_copy)
max_val = max(arr_copy)
# 计算桶的数量
bucket_count = (max_val - min_val) // bucket_size + 1
buckets = [[] for _ in range(bucket_count)]
# 将元素分配到桶中
for num in arr_copy:
idx = (num - min_val) // bucket_size
buckets[idx].append(num)
# 对每个桶进行排序
result = []
for bucket in buckets:
result.extend(sorted(bucket)) # 可以使用其他排序算法
return result10. 基数排序 (Radix Sort)
def radix_sort(arr):
"""
基数排序：按位排序（从最低位到最高位）
时间复杂度：O(d * (n + k))，d为位数，空间复杂度：O(n + k)
"""
if not arr:
return []
arr_copy = arr.copy()
# 找到最大数的位数
max_num = max(arr_copy)
max_digits = len(str(max_num))
# 从最低位到最高位进行排序
for digit in range(max_digits):
arr_copy = _counting_sort_by_digit(arr_copy, digit)
return arr_copy
def _counting_sort_by_digit(arr, digit):
"""根据指定位数进行计数排序"""
n = len(arr)
output = [0] * n
count = [0] * 10 # 0-9
# 统计当前位数的出现次数
for num in arr:
digit_val = (num // (10 ** digit)) % 10
count[digit_val] += 1
# 计算累积计数
for i in range(1, 10):
count[i] += count[i - 1]
# 构建输出数组
for num in reversed(arr):
digit_val = (num // (10 ** digit)) % 10
idx = count[digit_val] - 1
output[idx] = num
count[digit_val] -= 1
return output测试代码
def test_sorting_algorithms():
"""测试所有排序算法"""
import random
# 测试数据
test_cases = [
[], # 空数组
[1], # 单个元素
[5, 2, 8, 1, 9, 3], # 普通数组
[1, 2, 3, 4, 5], # 已排序
[5, 4, 3, 2, 1], # 逆序
[3, 3, 1, 2, 3, 1], # 重复元素
[random.randint(1, 100) for _ in range(20)] # 随机数组
]
algorithms = [
("冒泡排序", bubble_sort),
("选择排序", selection_sort),
("插入排序", insertion_sort),
("希尔排序", shell_sort),
("归并排序", merge_sort),
("快速排序", quick_sort),
("堆排序", heap_sort),
("计数排序", counting_sort),
("桶排序", bucket_sort),
("基数排序", radix_sort)
]
for test_case in test_cases:
print(f"\n原数组: {test_case}")
for name, algo in algorithms:
try:
# 计数排序和基数排序只适用于非负整数
if name in ["计数排序", "桶排序", "基数排序"] and test_case and min(test_case) < 0:
continue
result = algo(test_case)
print(f"{name}: {result}")
# 验证排序是否正确
assert result == sorted(test_case), f"{name} 排序错误"
except Exception as e:
print(f"{name}: 错误 - {e}")
print("-" * 50)
# 运行测试
if __name__ == "__main__":
test_sorting_algorithms()算法对比总结
这些算法各有特点，您可以根据具体场景选择使用。