# Python 中排序算法有哪些 排序算法是计算机科学中最基础且重要的算法类别之一，Python作为一门广泛应用的高级语言，内置了高效的排序函数，同时也支持开发者实现各类经典排序算法。本文将系统介绍Python中常见的排序算法，包括原理、实现代码及复杂度分析。 --- ## 目录 1. [内置排序函数](#1-内置排序函数) 2. [基于比较的排序算法](#2-基于比较的排序算法) - 冒泡排序 - 选择排序 - 插入排序 - 快速排序 - 归并排序 - 堆排序 3. [非比较排序算法](#3-非比较排序算法) - 计数排序 - 桶排序 - 基数排序 4. [算法对比与选择建议](#4-算法对比与选择建议) 5. [总结](#5-总结) --- ## 1. 内置排序函数 Python提供了两个内置排序方法： - `sorted()`: 返回新排序列表，不改变原数据 ```python nums = [3, 1, 4, 2] sorted_nums = sorted(nums) # [1, 2, 3, 4] list.sort(): 原地排序（修改原列表） nums.sort() # nums变为[1, 2, 3, 4] 原理：重复比较相邻元素，将较大值逐步”冒泡”到右侧。
def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] 原理：每次选择未排序部分的最小值放到已排序末尾。
def selection_sort(arr): for i in range(len(arr)): min_idx = i for j in range(i+1, len(arr)): if arr[j] < arr[min_idx]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] 原理：将未排序元素逐个插入到已排序部分的正确位置。
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 原理：分治法策略，选取基准值(pivot)将数组分为两部分递归排序。
def quick_sort(arr): if len(arr) <= 1: return arr pivot = 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 merge_sort(arr): 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 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 result 原理：利用堆数据结构（完全二叉树）进行排序。
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) 适用场景：元素范围有限的整数排序。
def counting_sort(arr): max_val = max(arr) count = [0] * (max_val+1) for num in arr: count[num] += 1 output = [] for i in range(len(count)): output.extend([i]*count[i]) return output 原理：将数据分到有限数量的桶里，每个桶再单独排序。
def bucket_sort(arr, bucket_size=5): min_val, max_val = min(arr), max(arr) bucket_count = (max_val - min_val) // bucket_size + 1 buckets = [[] for _ in range(bucket_count)] for num in arr: buckets[(num - min_val) // bucket_size].append(num) return [num for bucket in buckets for num in sorted(bucket)] 原理：按位数逐位排序（从低位到高位）。
def radix_sort(arr): max_num = max(arr) exp = 1 while max_num // exp > 0: counting_sort_by_digit(arr, exp) exp *= 10 def counting_sort_by_digit(arr, exp): output = [0] * len(arr) count = [0] * 10 for num in arr: digit = (num // exp) % 10 count[digit] += 1 for i in range(1, 10): count[i] += count[i-1] for num in reversed(arr): digit = (num // exp) % 10 output[count[digit]-1] = num count[digit] -= 1 for i in range(len(arr)): arr[i] = output[i] | 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 | 教学用途 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 | 通用排序（默认选择） |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 | 链表排序/外部排序 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 | 内存受限场景 |
| 计数排序 | O(n+k) | O(n+k) | O(k) | 稳定 | 小范围整数 |
| 基数排序 | O(nk) | O(nk) | O(n+k) | 稳定 | 多位数排序（如手机号） |
选择建议： - 一般情况：优先使用内置sorted() - 需要稳定性：归并排序、计数排序 - 内存敏感：堆排序 - 数据范围已知：非比较排序（计数/桶/基数）
Python提供了丰富的排序算法选择，从简单的O(n²)算法到高效的O(n log n)算法，再到特殊场景下的线性排序算法。理解这些算法的原理和特性有助于在实际开发中做出合理选择。对于绝大多数应用场景，Python内置的Timsort已经足够高效，但在特定需求下（如稳定性要求、内存限制等），自定义排序算法的实现仍然具有重要意义。 “`
注：本文实际约2300字，核心内容已完整覆盖。如需扩展至2500字，可增加以下内容： 1. 各算法的具体示例步骤图解 2. Python中functools.cmp_to_key的用法 3. 更多优化变种（如三路快排、希尔排序等） 4. 实际性能测试对比数据
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
