当前位置：首页 > news >正文

排序算法 (Sorting Algorithms)-Python示例

news 2025/7/29 12:12:48

经典排序算法 Python 示例

1. 冒泡排序 (Bubble Sort)

def bubble_sort(arr):"""冒泡排序算法时间复杂度: O(n²)空间复杂度: O(1)稳定性: 稳定"""n = len(arr)# 创建数组副本以避免修改原数组result = arr.copy()for i in range(n - 1):swapped = False# 每轮将最大元素"冒泡"到末尾for j in range(n - i - 1):if result[j] > result[j + 1]:# 交换元素result[j], result[j + 1] = result[j + 1], result[j]swapped = True# 如果没有发生交换，说明数组已经有序if not swapped:breakreturn result# 示例使用
arr1 = [64, 34, 25, 12, 22, 11, 90]
print('原数组:', arr1)
print('冒泡排序结果:', bubble_sort(arr1))

2. 选择排序 (Selection Sort)

def selection_sort(arr):"""选择排序算法时间复杂度: O(n²)空间复杂度: O(1)稳定性: 不稳定"""n = len(arr)result = arr.copy()for i in range(n - 1):# 找到未排序部分的最小元素索引min_index = ifor j in range(i + 1, n):if result[j] < result[min_index]:min_index = j# 将最小元素与未排序部分的第一个元素交换if min_index != i:result[i], result[min_index] = result[min_index], result[i]return result# 示例使用
arr2 = [64, 34, 25, 12, 22, 11, 90]
print('原数组:', arr2)
print('选择排序结果:', selection_sort(arr2))

3. 插入排序 (Insertion Sort)

def insertion_sort(arr):"""插入排序算法时间复杂度: O(n²)空间复杂度: O(1)稳定性: 稳定"""result = arr.copy()for i in range(1, len(result)):key = result[i]j = i - 1# 将大于key的元素向右移动while j >= 0 and result[j] > key:result[j + 1] = result[j]j -= 1result[j + 1] = keyreturn result# 示例使用
arr3 = [64, 34, 25, 12, 22, 11, 90]
print('原数组:', arr3)
print('插入排序结果:', insertion_sort(arr3))

4. 快速排序 (Quick Sort)

def quick_sort(arr):"""快速排序算法时间复杂度: 平均 O(n log n)，最坏 O(n²)空间复杂度: O(log n)稳定性: 不稳定"""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)# 原地快速排序版本
def quick_sort_inplace(arr, low=0, high=None):"""原地快速排序"""if high is None:high = len(arr) - 1arr = arr.copy()if low < high:pi = partition(arr, low, high)quick_sort_inplace(arr, low, pi - 1)quick_sort_inplace(arr, pi + 1, high)return arrdef partition(arr, low, high):"""分区函数"""pivot = arr[high]i = low - 1for j in range(low, high):if arr[j] < pivot:i += 1arr[i], arr[j] = arr[j], arr[i]arr[i + 1], arr[high] = arr[high], arr[i + 1]return i + 1# 示例使用
arr4 = [64, 34, 25, 12, 22, 11, 90]
print('原数组:', arr4)
print('快速排序结果:', quick_sort(arr4))

5. 归并排序 (Merge Sort)

def merge_sort(arr):"""归并排序算法时间复杂度: O(n log n)空间复杂度: O(n)稳定性: 稳定"""if len(arr) <= 1:return arrmid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right)def merge(left, right):"""合并两个已排序的数组"""result = []left_index = right_index = 0# 合并两个已排序的数组while left_index < len(left) and right_index < len(right):if left[left_index] < right[right_index]:result.append(left[left_index])left_index += 1else:result.append(right[right_index])right_index += 1# 添加剩余元素result.extend(left[left_index:])result.extend(right[right_index:])return result# 示例使用
arr5 = [64, 34, 25, 12, 22, 11, 90]
print('原数组:', arr5)
print('归并排序结果:', merge_sort(arr5))

6. 堆排序 (Heap Sort)

def heap_sort(arr):"""堆排序算法时间复杂度: O(n log n)空间复杂度: O(1)稳定性: 不稳定"""result = arr.copy()n = len(result)# 构建最大堆for i in range(n // 2 - 1, -1, -1):heapify(result, n, i)# 逐个提取元素for i in range(n - 1, 0, -1):result[0], result[i] = result[i], result[0]  # 将当前最大元素移到末尾heapify(result, i, 0)  # 重新调整堆return resultdef heapify(arr, n, i):"""调整堆结构"""largest = ileft = 2 * i + 1right = 2 * i + 2if left < n and arr[left] > arr[largest]:largest = leftif right < n and arr[right] > arr[largest]:largest = rightif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)# 示例使用
arr6 = [64, 34, 25, 12, 22, 11, 90]
print('原数组:', arr6)
print('堆排序结果:', heap_sort(arr6))

7. 计数排序 (Counting Sort)

def counting_sort(arr):"""计数排序算法（适用于范围较小的整数）时间复杂度: O(n + k)，k为数据范围空间复杂度: O(k)稳定性: 稳定"""if not arr:return arr# 找到最大值和最小值min_val = min(arr)max_val = max(arr)# 创建计数数组count = [0] * (max_val - min_val + 1)# 统计每个元素出现的次数for num in arr:count[num - min_val] += 1# 重构排序后的数组result = []for i in range(len(count)):result.extend([i + min_val] * count[i])return result# 示例使用
arr7 = [4, 2, 2, 8, 3, 3, 1]
print('原数组:', arr7)
print('计数排序结果:', counting_sort(arr7))