Python 排序算法
基本排序算法
冒泡排序 (Bubble Sort)
冒泡排序是最简单的排序算法之一，它重复地遍历要排序的列表，比较相邻的元素并交换它们的位置。
1def bubble_sort(arr): 2 n = len(arr) 3 for i in range(n): 4 # 每次遍历后，最大的元素会"冒泡"到最后 5 for j in range(0, n-i-1): 6 if arr[j] > arr[j+1]: 7 arr[j], arr[j+1] = arr[j+1], arr[j] 8 return arr
时间复杂度：O(n²) 最坏和平均情况，O(n) 最好情况（当列表已经有序时）
选择排序 (Selection Sort)
选择排序每次找到最小元素，并将其放在已排序部分的末尾。
1def selection_sort(arr): 2 for i in range(len(arr)): 3 min_idx = i 4 for j in range(i+1, len(arr)): 5 if arr[j] < arr[min_idx]: 6 min_idx = j 7 arr[i], arr[min_idx] = arr[min_idx], arr[i] 8 return arr
时间复杂度：O(n²) 所有情况
插入排序 (Insertion Sort)
插入排序构建最终排序列表，每次将一个元素插入到已排序列表中的适当位置。
1def insertion_sort(arr): 2 for i in range(1, len(arr)): 3 key = arr[i] 4 j = i-1 5 while j >= 0 and key < arr[j]: 6 arr[j+1] = arr[j] 7 j -= 1 8 arr[j+1] = key 9 return arr
时间复杂度：O(n²) 最坏和平均情况，O(n) 最好情况
高级排序算法
快速排序 (Quick Sort)
快速排序使用分治法策略，选择一个"基准"元素，将列表分为两部分，然后递归排序。
1def quick_sort(arr): 2 if len(arr) <= 1: 3 return arr 4 pivot = arr[len(arr) // 2] 5 left = [x for x in arr if x < pivot] 6 middle = [x for x in arr if x == pivot] 7 right = [x for x in arr if x > pivot] 8 return quick_sort(left) + middle + quick_sort(right)
时间复杂度：O(n log n) 平均情况，O(n²) 最坏情况（当列表已经有序或逆序时）
归并排序 (Merge Sort)
归并排序也是一种分治算法，将列表分成两半，分别排序，然后合并结果。
1def merge_sort(arr): 2 if len(arr) <= 1: 3 return arr 4 5 mid = len(arr) // 2 6 left = merge_sort(arr[:mid]) 7 right = merge_sort(arr[mid:]) 8 9 return merge(left, right) 10 11def merge(left, right): 12 result = [] 13 i = j = 0 14 15 while i < len(left) and j < len(right): 16 if left[i] < right[j]: 17 result.append(left[i]) 18 i += 1 19 else: 20 result.append(right[j]) 21 j += 1 22 23 result.extend(left[i:]) 24 result.extend(right[j:]) 25 return result
时间复杂度：O(n log n) 所有情况
堆排序 (Heap Sort)
堆排序利用堆数据结构进行排序，首先构建最大堆，然后逐个提取最大元素。
1def heapify(arr, n, i): 2 largest = i 3 l = 2 * i + 1 4 r = 2 * i + 2 5 6 if l < n and arr[l] > arr[largest]: 7 largest = l 8 if r < n and arr[r] > arr[largest]: 9 largest = r 10 if largest != i: 11 arr[i], arr[largest] = arr[largest], arr[i] 12 heapify(arr, n, largest) 13 14def heap_sort(arr): 15 n = len(arr) 16 17 # 构建最大堆 18 for i in range(n//2 - 1, -1, -1): 19 heapify(arr, n, i) 20 21 # 逐个提取元素 22 for i in range(n-1, 0, -1): 23 arr[i], arr[0] = arr[0], arr[i] 24 heapify(arr, i, 0) 25 26 return arr
时间复杂度：O(n log n) 所有情况
Python 内置排序
Python 提供了内置的 sorted() 函数和列表的 sort() 方法：
1# 使用 sorted() 函数 2numbers = [5, 2, 9, 1, 5, 6] 3sorted_numbers = sorted(numbers) # 返回新列表 4 5# 使用 list.sort() 方法 6numbers.sort() # 原地排序
Python 的 Timsort 算法（归并排序和插入排序的混合）：
- 时间复杂度：O(n log n) 最坏情况
- 空间复杂度：O(n)
- 稳定排序（相等元素的相对位置不变）
算法选择建议
- 小数据集：插入排序通常表现良好
- 大数据集：快速排序、归并排序或堆排序
- 需要稳定排序：归并排序或 Timsort
- 内存受限：堆排序（原地排序）
- 几乎有序的数据：插入排序或冒泡排序
性能比较示例
1import timeit 2import random 3 4# 生成随机列表 5test_list = random.sample(range(10000), 1000) 6 7# 测试各种排序算法 8print("冒泡排序:", timeit.timeit(lambda: bubble_sort(test_list.copy()), number=1)) 9print("选择排序:", timeit.timeit(lambda: selection_sort(test_list.copy()), number=1)) 10print("插入排序:", timeit.timeit(lambda: insertion_sort(test_list.copy()), number=1)) 11print("快速排序:", timeit.timeit(lambda: quick_sort(test_list.copy()), number=1)) 12print("归并排序:", timeit.timeit(lambda: merge_sort(test_list.copy()), number=1)) 13print("堆排序:", timeit.timeit(lambda: heap_sort(test_list.copy()), number=1)) 14print("内置排序:", timeit.timeit(lambda: sorted(test_list.copy()), number=1))
典型结果（1000个元素）：
- 冒泡排序：约 0.2 秒
- 选择排序：约 0.1 秒
- 插入排序：约 0.05 秒
- 快速排序：约 0.002 秒
- 归并排序：约 0.003 秒
- 堆排序：约 0.004 秒
- 内置排序：约 0.0002 秒