1. 冒泡排序 (Bubble Sort)

def bubble_sort(arr):n = len(arr)# 遍历数组中的每个元素for i in range(n):# 内层循环，从数组的第一个元素到倒数第 i + 1 个元素for j in range(0, n - i - 1):# 如果当前元素比下一个元素大，则交换if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]return arr

2. 选择排序 (Selection Sort)

def selection_sort(arr):n = len(arr)# 遍历数组中的每个元素for i in range(n):# 假设当前元素是最小值min_idx = i# 通过内层循环找到最小值的索引for j in range(i + 1, n):if arr[j] < arr[min_idx]:min_idx = j# 交换当前元素和找到的最小值arr[i], arr[min_idx] = arr[min_idx], arr[i]return arr

3. 插入排序 (Insertion Sort)

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 -= 1arr[j + 1] = keyreturn arr

4. 归并排序 (Merge Sort)

def merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2  # 找到数组的中间点L = arr[:mid]        # 将数组分成两部分R = arr[mid:]merge_sort(L)  # 递归排序左半部分merge_sort(R)  # 递归排序右半部分i = j = k = 0# 合并两个已排序的子数组while i < len(L) and j < len(R):if L[i] < R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1# 检查是否还有剩余的元素while i < len(L):arr[k] = L[i]i += 1k += 1while j < len(R):arr[k] = R[j]j += 1k += 1return arr

5. 快速排序 (Quick Sort)

def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]  # 选择数组的中间元素作为基准left = [x for x in arr if x < pivot]  # 所有小于基准的元素middle = [x for x in arr if x == pivot]  # 所有等于基准的元素right = [x for x in arr if x > pivot]  # 所有大于基准的元素return quick_sort(left) + middle + quick_sort(right)

6. 堆排序 (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[i], arr[0] = arr[0], arr[i]  # 交换heapify(arr, i, 0)return arr

7. 希尔排序 (Shell Sort)

def shell_sort(arr):n = len(arr)gap = n // 2while gap > 0:for i in range(gap, n):temp = arr[i]j = i# 插入排序while j >= gap and arr[j - gap] > temp:arr[j] = arr[j - gap]j -= gaparr[j] = tempgap //= 2return arr

8. 计数排序 (Counting Sort)

def counting_sort(arr):max_val = max(arr)m = max_val + 1count = [0] * m# 统计每个元素的个数for a in arr:count[a] += 1i = 0for a in range(m):for c in range(count[a]):arr[i] = ai += 1return arr

9. 基数排序 (Radix Sort)

def counting_sort_for_radix(arr, exp):n = len(arr)output = [0] * ncount = [0] * 10# 统计每个基数的个数for i in range(n):index = arr[i] // expcount[index % 10] += 1for i in range(1, 10):count[i] += count[i - 1]i = n - 1while i >= 0:index = arr[i] // expoutput[count[index % 10] - 1] = arr[i]count[index % 10] -= 1i -= 1for i in range(n):arr[i] = output[i]def radix_sort(arr):max_val = max(arr)exp = 1while max_val // exp > 0:counting_sort_for_radix(arr, exp)exp *= 10return arr

10. 桶排序 (Bucket Sort)

def bucket_sort(arr):if len(arr) == 0:return arrbucket = []slot_num = 10  # 桶的数量for i in range(slot_num):bucket.append([])# 将元素分配到不同的桶中for j in arr:index = int(slot_num * j)bucket[index].append(j)# 对每个桶中的元素进行排序for i in range(slot_num):bucket[i] = insertion_sort(bucket[i])k = 0for i in range(slot_num):for j in range(len(bucket[i])):arr[k] = bucket[i][j]k += 1return arr

11. Tim Sort (Tim Sort)

MIN_MERGE = 32def calc_min_run(n):r = 0while n >= MIN_MERGE:r |= n & 1n >>= 1return n + rdef insertion_sort_for_timsort(arr, left, right):for i in range(left + 1, right + 1):temp = arr[i]j = i - 1while j >= left and arr[j] > temp:arr[j + 1] = arr[j]j -= 1arr[j + 1] = tempdef merge_for_timsort(arr, l, m, r):len1, len2 = m - l + 1, r - mleft, right = [], []for i in range(0, len1):left.append(arr[l + i])for i in range(0, len2):right.append(arr[m + 1 + i])i, j,