### Python 常用排序算法及内置排序方法 #### 一、内置排序方法 Python 提供了一种高效且易于使用的内置排序功能，主要通过 `sort()` 方法和独立函数 `sorted()` 实现。这些方法底层基于 Timsort 算法，这是一种混合稳定排序算法，结合了归并排序和插入排序的优点[^1]。 `list.sort()` 是列表对象的一个原地排序方法，它会修改原始列表而不返回新列表；而 `sorted(iterable)` 则接受任何可迭代对象作为输入，并返回一个新的已排序列表[^2]。 示例代码如下： ```python # 使用 list.sort() lst = [3, 1, 4, 1, 5, 9] lst.sort() print(lst) # 输出: [1, 1, 3, 4, 5, 9] # 使用 sorted() new_lst = sorted([3, 1, 4, 1, 5, 9]) print(new_lst) # 输出: [1, 1, 3, 4, 5, 9] ``` #### 二、手写经典排序算法 除了使用内置排序外，还可以手动实现一些经典的排序算法来加深理解。以下是几个常见的例子： ##### 1. 冒泡排序 冒泡排序是一种简单的排序算法，其核心思想是比较相邻的两个元素并将较大的值向右移动。该过程重复多次直到整个数组有序[^3]。 ```python def bubble_sort(lst): n = len(lst) for j in range(n - 1): for i in range(n - 1 - j): if lst[i] > lst[i + 1]: lst[i], lst[i + 1] = lst[i + 1], lst[i] return lst ``` ##### 2. 插入排序 插入排序的工作机制类似于整理扑克牌的过程——每次取出一张牌并将其插入到合适的位置中。 ```python def insertion_sort(lst): for i in range(1, len(lst)): key = lst[i] j = i - 1 while j >= 0 and lst[j] > key: lst[j + 1] = lst[j] j -= 1 lst[j + 1] = key return lst ``` ##### 3. 快速排序 快速排序采用分治策略，选取一个基准值将数据划分为两部分，递归处理这两部分直至完成排序[^4]。 ```python def quick_sort(arr): if len(arr) <= 1: return arr else: 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) ``` ##### 4. 基数排序 基数排序适用于整数类型的排序问题，按照每一位上的数字依次进行分配与收集操作，最终得到完全有序的结果。 ```python def radix_sort(nums): max_digit = max(len(str(abs(num))) for num in nums) for d in range(max_digit): buckets = [[] for _ in range(10)] for num in nums: digit = abs(num) // (10 ** d) % 10 buckets[digit].append(num) nums = [num for bucket in buckets for num in bucket] return nums ``` #### 性能对比 不同场景下适合不同的排序算法。对于大数据量或者需要稳定性的情况，推荐优先考虑内置的 Timsort 排序方法。而对于学习目的或特殊需求，则可以选择其他经典算法加以实践[^5]。 ---