当前位置：首页 > news >正文

排序算法大全：从冒泡到快排，LeetCode排序题高效解法

news 2026/7/18 12:23:55

排序算法大全：从冒泡到快排，LeetCode排序题高效解法

【免费下载链接】leetcodepython 数据结构与算法 leetcode 算法题与书籍刷算法全靠套路与总结！Crack LeetCode, not only how, but also why.项目地址: https://gitcode.com/gh_mirrors/leetcode82/leetcode

排序算法是数据结构与算法的基础，也是LeetCode等编程面试中的高频考点。本文将系统介绍常见排序算法的核心原理、适用场景及在LeetCode中的实战应用，帮助你快速掌握从基础到高级的排序技巧，轻松应对各类算法题。

一、排序算法全景图：类型与复杂度对比

排序算法主要分为比较类排序和非比较类排序两大类。比较类排序通过比较元素间的大小来决定顺序，而非比较类排序则利用数学特性直接确定元素位置。以下是常见排序算法的时间复杂度对比：

图：冒泡排序、选择排序和插入排序的性能对比曲线

1.1 比较类排序

冒泡排序：O(n²)时间复杂度，简单直观，适合小规模数据
选择排序：O(n²)时间复杂度，不稳定排序，交换次数少
插入排序：O(n²)时间复杂度，对部分有序数据效率高
快速排序：O(nlogn)平均时间复杂度，分治思想，实际应用最广泛
归并排序：O(nlogn)时间复杂度，稳定排序，适合大数据量和链表
堆排序：O(nlogn)时间复杂度，原地排序，适合TopK问题

1.2 非比较类排序

计数排序：O(n+k)时间复杂度，适合范围不大的整数排序
基数排序：O(d*(n+k))时间复杂度，适合字符串和整数排序
桶排序：O(n)平均时间复杂度，依赖数据分布，适合均匀分布场景

二、基础排序算法：原理与实现

2.1 冒泡排序：最简单的交换排序

冒泡排序通过重复交换相邻元素实现排序，就像水中气泡逐渐上浮。核心代码位于data_structure/sorts/bubble_sort.py：

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] return arr

适用场景：几乎只用于教学，实际工程中很少使用。LeetCode第912题「排序数组」的暴力解法可作为理解基础。

2.2 插入排序：扑克牌式排序

插入排序模拟抓牌时整理手牌的过程，将元素逐个插入到已排序序列的正确位置。实现代码见data_structure/sorts/insertion_sort.py：

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 return arr

实战技巧：在LeetCode第147题「对链表进行插入排序」中，插入排序展现了对链表结构的良好适应性。

三、高级排序算法：性能优化与实战

3.1 快速排序：分治思想的典范

快速排序采用"分而治之"策略，通过选择基准元素将数组分区。项目中的实现位于data_structure/sorts/quick_sort.py：

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)

LeetCode应用：第215题「数组中的第K个最大元素」可通过快排思想的快速选择算法高效解决，平均时间复杂度O(n)。