十大经典排序算法深度解析与实践指南

作者：热心市民鹿先生2025.12.15 19:05浏览量：0

简介：本文系统梳理十大经典排序算法的原理、实现与性能特征，涵盖比较类与非比较类排序，通过时间复杂度对比、稳定性分析及代码示例，帮助开发者掌握算法选型策略与优化方法，适用于面试准备、算法设计及性能调优场景。

一、排序算法分类与核心指标

排序算法可分为比较类排序与非比较类排序两大类，其性能评估主要关注以下指标：

时间复杂度：最坏/平均/最好情况下的比较与交换次数
空间复杂度：额外内存消耗（原地排序仅需O(1)）
稳定性：相等元素的相对顺序是否保持
适应性：对部分有序数据的处理效率

二、比较类排序算法详解

1. 冒泡排序（Bubble Sort）

原理：通过相邻元素比较交换，将最大元素逐步”冒泡”至数组末尾。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        if not swapped: break  # 提前终止优化

特性：

时间复杂度：O(n²)（最好情况O(n)）
空间复杂度：O(1)
稳定排序
适用于小规模数据或基本有序数据

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]

特性：

时间复杂度：O(n²)
空间复杂度：O(1)
不稳定排序（相同元素可能交换）
交换次数少（n次交换 vs 冒泡的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)）
空间复杂度：O(1)
稳定排序
对小规模或部分有序数据效率高

4. 希尔排序（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 log n)）
空间复杂度：O(1)
不稳定排序
适用于中等规模数据

5. 归并排序（Merge Sort）

原理：分治思想，递归分解后合并有序子数组。

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L, R = arr[:mid], arr[mid:]
        merge_sort(L)
        merge_sort(R)
        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
        arr[k:] = L[i:] if i < len(L) else R[j:]

特性：

时间复杂度：O(n log n)
空间复杂度：O(n)
稳定排序
适合链表排序和外部排序

6. 快速排序（Quick Sort）

原理：分治思想，选择基准元素分区后递归排序。

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²)
空间复杂度：O(log n)（递归栈）
不稳定排序
实际应用中效率最高（通过三数取中优化基准）

7. 堆排序（Heap Sort）

原理：构建最大堆后反复取出堆顶元素。

def heapify(arr, n, i):
    largest = i
    l, r = 2*i+1, 2*i+2
    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        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)
不稳定排序
适合实时系统（无最坏情况退化）

三、非比较类排序算法

8. 计数排序（Counting Sort）

原理：统计元素出现次数，按计数重建有序数组。

def counting_sort(arr):
    max_val = max(arr)
    count = [0]*(max_val+1)
    for num in arr:
        count[num] += 1
    idx = 0
    for i in range(len(count)):
        while count[i] > 0:
            arr[idx] = i
            idx += 1
            count[i] -= 1

特性：

时间复杂度：O(n+k)（k为数值范围）
空间复杂度：O(n+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:
        idx = (num-min_val)//bucket_size
        buckets[idx].append(num)
    arr.clear()
    for bucket in buckets:
        insertion_sort(bucket)  # 桶内使用插入排序
        arr.extend(bucket)

特性：

时间复杂度：平均O(n+k)
空间复杂度：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):
        idx = (arr[i]//exp)%10
        count[idx] += 1
    for i in range(1,10):
        count[i] += count[i-1]
    for i in range(n-1,-1,-1):
        idx = (arr[i]//exp)%10
        output[count[idx]-1] = arr[i]
        count[idx] -= 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为最大位数）
空间复杂度：O(n+k)
稳定排序
适合整数或定长字符串

四、算法选型与优化建议

数据规模：
- n < 50：插入排序或选择排序
- 50 < n < 1000：快速排序或堆排序
- n > 1000：归并排序或外部排序
数据特征：
- 基本有序：插入排序（O(n)）
- 重复元素多：三向切分快速排序
- 内存受限：堆排序（O(1)空间）
稳定性要求：
- 需要稳定：归并排序、插入排序
- 不需要稳定：快速排序、堆排序
数值范围：
- 整数且范围小：计数排序
- 均匀分布浮点数：桶排序
- 定长数字：基数排序

五、工程实践注意事项

递归深度控制：快速排序需设置递归深度阈值，超过后转为堆排序
小规模数据优化：当子数组规模小于阈值（如16）时切换为插入排序
并行化设计：归并排序的合并阶段可并行处理
内存访问优化：缓存友好的排序（如块排序）
稳定性处理：在需要稳定的场景中，避免使用选择排序等不稳定算法

通过系统掌握这些排序算法的特性与适用场景，开发者可以在面试中展现扎实的算法基础，在实际工程中根据具体需求选择最优方案，并通过细节优化显著提升系统性能。

发表评论

开发者关注产品榜

最热文章

关于作者

被阅读数
被赞数
被收藏数

开发者热搜

十大经典排序算法深度解析与实践指南

一、排序算法分类与核心指标

二、比较类排序算法详解

1. 冒泡排序（Bubble Sort）

2. 选择排序（Selection Sort）

3. 插入排序（Insertion Sort）

4. 希尔排序（Shell Sort）

5. 归并排序（Merge Sort）

6. 快速排序（Quick Sort）

7. 堆排序（Heap Sort）

三、非比较类排序算法

8. 计数排序（Counting Sort）

9. 桶排序（Bucket Sort）

10. 基数排序（Radix Sort）

四、算法选型与优化建议

五、工程实践注意事项

相关文章推荐

文心一言接入指南：通过百度智能云千帆大模型平台API调用

从 MLOps 到 LMOps 的关键技术嬗变

Sugar BI教你怎么做数据可视化 - 拓扑图，让节点连接信息一目了然

更轻量的百度百舸，CCE Stack 智算版发布

打造合规数据闭环，加速自动驾驶技术研发

LMOps 工具链与千帆大模型平台

发表评论

开发者关注产品榜

百度千帆·大模型服务及Agent开发平台

百度千帆·数据智能平台

秒哒-生成式应用开发平台

百度智能云客悦智能客服平台

最热文章

关于作者