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

排序算法大全：从冒泡到快排，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)。

3.2 归并排序：稳定排序的代表

归并排序将数组分成两半分别排序，再合并结果。其稳定特性使其适合对象排序，实现见data_structure/sorts/merge_sort.py。

典型应用：LeetCode第23题「合并K个升序链表」是归并排序思想在链表中的经典应用，通过分治合并提高效率。

3.3 堆排序：优先队列的基础

堆排序利用堆的特性进行排序，适合解决TopK问题。项目实现位于data_structure/sorts/heap_sort.py。

实战案例：LeetCode第347题「前K个高频元素」可通过堆排序实现，时间复杂度O(nlogk)。

四、非比较排序：特殊场景的高效解决方案

4.1 计数排序：整数排序的利器

计数排序通过统计元素出现次数来排序，适合范围有限的整数。实现代码见data_structure/sorts/counting_sort.py。

应用场景：LeetCode第164题「最大间距」要求线性时间复杂度，可结合计数排序或桶排序实现。

4.2 桶排序：分布式排序策略

桶排序将数据分到多个桶中，每个桶单独排序。项目中的实现位于data_structure/sorts/bucket_sort.py。

五、算法选择指南：场景与性能对比

选择合适的排序算法需要考虑数据规模、分布特性和稳定性要求：

图：算法知识体系思维导图，包含排序算法在数据结构中的位置

5.1 小规模数据（n<100）

• 优先选择插入排序或冒泡排序，实现简单
• LeetCode第217题「存在重复元素」可直接使用插入排序检测

5.2 中等规模数据（100≤n≤10000）

• 快速排序通常表现最佳
• LeetCode第56题「合并区间」可先用快排预处理区间

5.3 大规模数据（n>10000）

• 归并排序或堆排序更稳定
• 外部排序场景下归并排序是首选

5.4 特殊数据类型

• 字符串排序：基数排序
• 整数排序：计数排序
• 链表排序：归并排序

六、LeetCode排序题解题套路

6.1 排序+双指针

套路解析：先排序，再用双指针优化查找过程
典型例题：LeetCode第15题「三数之和」
解决方案：排序后固定一个元素，双指针查找另外两个元素

6.2 排序+贪心

套路解析：排序后利用贪心策略选择最优解
典型例题：LeetCode第452题「用最少数量的箭引爆气球」
解决方案：按区间右端点排序，贪心选择最早结束的区间

6.3 自定义排序规则

套路解析：根据题目要求定义比较函数
典型例题：LeetCode第179题「最大数」
解决方案：自定义字符串比较规则，排序后拼接

七、学习资源与进阶路径

7.1 推荐学习资料

• 算法理论：book/算法/算法之美.png
• 数据结构基础：book/数据结构/数据结构-极客时间.jpg

7.2 实战训练路径

1. 基础排序：完成LeetCode第912题「排序数组」的5种解法
2. 应用练习：解决第56、148、215等排序应用题
3. 优化挑战：尝试第493题「翻转对」等Hard难度题目

通过系统学习和刻意练习，排序算法将成为你解决复杂问题的有力工具。记住，理解算法原理比死记代码更重要，多思考不同算法的适用场景和优化方向，才能在面试中游刃有余。

祝你的算法学习之旅顺利！🚀

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