python 中排序算法有哪些

# 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]
  

  两者均使用Timsort算法（结合归并排序和插入排序的混合算法），时间复杂度为O(n log n)。

---

2. 基于比较的排序算法

冒泡排序 (Bubble Sort)

原理：重复比较相邻元素，将较大值逐步”冒泡”到右侧。

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]

• 时间复杂度：O(n²)（最坏/平均）
• 空间复杂度：O(1)
• 稳定性：稳定

选择排序 (Selection Sort)

原理：每次选择未排序部分的最小值放到已排序末尾。

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]

• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定性：不稳定

插入排序 (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[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

• 时间复杂度：O(n²)（最坏/平均），最好O(n)（已排序情况）
• 空间复杂度：O(1)
• 稳定性：稳定

快速排序 (Quick Sort)

原理：分治法策略，选取基准值(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)

• 时间复杂度：平均O(n log n)，最坏O(n²)（当数组已排序）
• 空间复杂度：O(log n)（递归栈）
• 稳定性：不稳定

归并排序 (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

• 时间复杂度：O(n log n)
• 空间复杂度：O(n)
• 稳定性：稳定

堆排序 (Heap Sort)

原理：利用堆数据结构（完全二叉树）进行排序。

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)

• 时间复杂度：O(n log n)
• 空间复杂度：O(1)
• 稳定性：不稳定

---

3. 非比较排序算法

计数排序 (Counting Sort)

适用场景：元素范围有限的整数排序。

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

• 时间复杂度：O(n+k)（k为数值范围）
• 空间复杂度：O(k)

桶排序 (Bucket Sort)

原理：将数据分到有限数量的桶里，每个桶再单独排序。

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)]

• 时间复杂度：平均O(n+k)，最坏O(n²)
• 空间复杂度：O(n+k)

基数排序 (Radix Sort)

原理：按位数逐位排序（从低位到高位）。

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(nk)（k为最大数字的位数）
• 空间复杂度：O(n+k)

---

4. 算法对比与选择建议

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	适用场景
冒泡排序	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() - 需要稳定性：归并排序、计数排序 - 内存敏感：堆排序 - 数据范围已知：非比较排序（计数/桶/基数）

---

5. 总结

Python提供了丰富的排序算法选择，从简单的O(n²)算法到高效的O(n log n)算法，再到特殊场景下的线性排序算法。理解这些算法的原理和特性有助于在实际开发中做出合理选择。对于绝大多数应用场景，Python内置的Timsort已经足够高效，但在特定需求下（如稳定性要求、内存限制等），自定义排序算法的实现仍然具有重要意义。 “`

注：本文实际约2300字，核心内容已完整覆盖。如需扩展至2500字，可增加以下内容： 1. 各算法的具体示例步骤图解 2. Python中functools.cmp_to_key的用法 3. 更多优化变种（如三路快排、希尔排序等） 4. 实际性能测试对比数据