十大经典排序算法全解析：原理、实现与优化指南

排序算法是计算机科学的核心基础之一，其效率直接影响数据处理、搜索优化、数据库查询等场景的性能。本文将系统梳理十大经典排序算法，从原理、实现到优化策略进行全方位解析，帮助开发者根据业务需求选择最优方案。

一、基础排序算法：简单但低效

1. 冒泡排序（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]  # 交换

优化点：

增加标志位swapped，若某一轮未发生交换，则提前终止。
时间复杂度：最优O(n)（已排序），最差O(n²)。
适用场景：小规模数据或教学演示。

2. 选择排序（Selection Sort）

原理：每次选择未排序部分的最小值，与当前位置交换。
实现：

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]  # 交换

特点：

交换次数少（最多n-1次），但比较次数多。
时间复杂度：始终O(n²)。
适用场景：交换成本高的场景（如链表）。

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[j+1] = arr[j]  # 元素后移
            j -= 1
        arr[j+1] = key  # 插入

优化点：

二分查找优化插入位置（减少比较次数）。
时间复杂度：最优O(n)，最差O(n²)。
适用场景：部分有序或小规模数据。

二、高效排序算法：分治与递归

4. 归并排序（Merge Sort）

原理：采用分治法，将数组递归拆分为两半，分别排序后合并。
实现：

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        merge_sort(left)  # 递归左半
        merge_sort(right)  # 递归右半
        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1
        # 处理剩余元素
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

特点：

稳定排序，适合链表或外部排序（如大数据处理）。
时间复杂度：始终O(n log n)。
空间复杂度：O(n)（需额外存储）。

5. 快速排序（Quick Sort）

原理：选择基准值（pivot），将数组分为小于和大于基准的两部分，递归排序。
实现：

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)  # 获取分区点
        quick_sort(arr, low, pi-1)  # 递归左半
        quick_sort(arr, pi+1, high)  # 递归右半
def partition(arr, low, high):
    pivot = arr[high]  # 选择最后一个元素为基准
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # 交换
    arr[i+1], arr[high] = arr[high], arr[i+1]  # 基准归位
    return i + 1

优化点：

三数取中法选择基准，避免最坏情况。
小规模数据切换为插入排序。
时间复杂度：平均O(n log n)，最差O(n²)。
适用场景：大规模随机数据。

三、特殊场景优化算法

6. 堆排序（Heap Sort）

原理：利用最大堆（或最小堆）进行排序，每次取出堆顶元素并调整堆。
实现：

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    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(1)。
时间复杂度：始终O(n log n)。
适用场景：内存受限的嵌入式系统。

7. 希尔排序（Shell Sort）

原理：通过分组插入排序逐步缩小间隔，最终完成整体排序。
实现：

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j-gap] > temp:
                arr[j] = arr[j-gap]
                j -= gap
            arr[j] = temp
        gap //= 2  # 缩小间隔

特点：

插入排序的改进版，时间复杂度介于O(n)和O(n²)之间。
适用场景：中等规模数据。

四、非比较排序算法

8. 计数排序（Counting Sort）

原理：统计每个元素的出现次数，按顺序输出。
实现：

def counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    # 重建有序数组
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    return sorted_arr

特点：

仅适用于整数且范围较小的数据。
时间复杂度：O(n + k)（k为数据范围）。
适用场景：年龄、分数等有限范围数据。

9. 桶排序（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:
        index = (num - min_val) // bucket_size
        buckets[index].append(num)
    # 对每个桶排序（此处用内置排序）
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(sorted(bucket))
    return sorted_arr

特点：

依赖桶的均匀分布，否则效率下降。
时间复杂度：平均O(n + k)。
适用场景：均匀分布的浮点数。

10. 基数排序（Radix Sort）

原理：按位数从低位到高位依次排序（可用计数排序实现）。
实现：

def counting_sort_for_radix(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    # 统计当前位数字
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1
    # 计算累计位置
    for i in range(1, 10):
        count[i] += count[i-1]
    # 反向填充输出数组
    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1
    # 复制回原数组
    for i in range(n):
        arr[i] = output[i]
def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10

特点：

仅适用于整数或固定长度的字符串。
时间复杂度：O(d(n + k))（d为最大位数）。
适用场景：电话号码、ID等固定位数数据。

五、算法选择指南

小规模数据：插入排序或选择排序。
大规模随机数据：快速排序（优化后）。
稳定排序需求：归并排序或计数排序。
内存受限场景：堆排序。
有限范围整数：计数排序或基数排序。

通过理解算法原理与适用场景，开发者可针对具体问题设计高效的数据处理流程，提升系统整体性能。