1. 排序算法概述排序是计算机科学中最基础且重要的算法之一它将一组数据按照特定顺序升序或降序重新排列。Python作为一门高级编程语言提供了多种内置的排序方法同时也支持各种经典排序算法的实现。2. Python内置排序方法2.1 list.sort()方法list.sort()方法会直接修改原列表默认按升序排序numbers [3, 1, 4, 1, 5, 9, 2, 6] numbers.sort() print(numbers) # 输出[1, 1, 2, 3, 4, 5, 6, 9]2.2 sorted()函数sorted()函数返回一个新的排序列表不修改原列表numbers [3, 1, 4, 1, 5, 9, 2, 6] sorted_numbers sorted(numbers) print(sorted_numbers) # 输出[1, 1, 2, 3, 4, 5, 6, 9] print(numbers) # 输出[3, 1, 4, 1, 5, 9, 2, 6]原列表不变2.3 自定义排序规则通过key参数可以指定排序依据# 按字符串长度排序 words [apple, banana, cherry, date] words.sort(keylen) print(words) # 输出[date, apple, banana, cherry] 按元组第二个元素排序 pairs [(1, 9), (2, 7), (3, 5), (4, 3)] pairs.sort(keylambda x: x[1]) print(pairs) # 输出[(4, 3), (3, 5), (2, 7), (1, 9)]2.4 降序排序使用reverseTrue参数进行降序排序numbers [3, 1, 4, 1, 5, 9, 2, 6] numbers.sort(reverseTrue) print(numbers) # 输出[9, 6, 5, 4, 3, 2, 1, 1]3. 经典排序算法实现3.1 冒泡排序Bubble Sort冒泡排序通过重复遍历列表比较相邻元素并交换位置来实现排序def bubble_sort(arr): n len(arr) for i in range(n): # 最后i个元素已经排好序 for j in range(0, n-i-1): if arr[j] arr[j1]: arr[j], arr[j1] arr[j1], arr[j] return arr 测试 arr [64, 34, 25, 12, 22, 11, 90] print(排序前:, arr) print(排序后:, bubble_sort(arr.copy()))时间复杂度O(n²)空间复杂度O(1)3.2 选择排序Selection Sort选择排序每次从未排序部分选择最小或最大元素放到已排序部分的末尾def selection_sort(arr): n len(arr) for i in range(n): min_idx i for j in range(i1, n): if arr[j] arr[min_idx]: min_idx j arr[i], arr[min_idx] arr[min_idx], arr[i] return arr 测试 arr [64, 25, 12, 22, 11] print(排序前:, arr) print(排序后:, selection_sort(arr.copy()))时间复杂度O(n²)空间复杂度O(1)3.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[j1] arr[j] j - 1 arr[j1] key return arr 测试 arr [12, 11, 13, 5, 6] print(排序前:, arr) print(排序后:, insertion_sort(arr.copy()))时间复杂度O(n²)空间复杂度O(1)3.4 快速排序Quick Sort快速排序使用分治策略选择一个基准元素将数组分为两部分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) 测试 arr [10, 7, 8, 9, 1, 5] print(排序前:, arr) print(排序后:, quick_sort(arr.copy()))时间复杂度平均O(n log n)最坏O(n²)空间复杂度O(log n)3.5 归并排序Merge Sort归并排序采用分治思想将数组递归分成两半然后合并排序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 测试 arr [38, 27, 43, 3, 9, 82, 10] print(排序前:, arr) print(排序后:, merge_sort(arr.copy()))时间复杂度O(n log n)空间复杂度O(n)4. 排序算法性能比较算法平均时间复杂度最坏时间复杂度空间复杂度稳定性适用场景冒泡排序O(n²)O(n²)O(1)稳定教学示例小规模数据选择排序O(n²)O(n²)O(1)不稳定小规模数据交换次数少插入排序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)稳定大规模数据需要稳定性5. 实际应用建议小规模数据n 100使用Python内置的sort()或sorted()即可底层采用TimSort算法性能优秀大规模数据优先使用内置排序Python的TimSort在大多数情况下表现优异需要稳定性选择归并排序或TimSortPython内置排序是稳定的内存受限考虑堆排序或原地快速排序特殊数据结构对于链表插入排序和归并排序更合适6. 总结Python提供了强大且高效的排序功能通过内置的sort()和sorted()函数可以满足大多数排序需求。理解经典排序算法的原理有助于在特殊场景下选择合适的排序策略。在实际开发中建议优先使用Python内置排序方法只有在特定需求如教学、算法研究或特殊数据结构时才考虑手动实现排序算法。