排序算法全解，为什么快排的时间波动特别大？
目录
排序算法全解，为什么快排的时间波动特别大？
一、总览与对比分析
二、快速排序
1、核心思想
2、算法特点
3、示例
三、归并排序
1、核心思想
2、算法特点
3、示例
四、堆排序
1、核心思想
2、算法特点
3、示例
五、排序方法对比与其他排序
六、总结
作者：watermelo37
CSDN全栈领域优质创作者、万粉博主、华为云云享专家、阿里云专家博主、腾讯云“创作之星”特邀作者、支付宝合作作者，全平台博客昵称watermelo37。
一个假装是giser的coder，做不只专注于业务逻辑的前端工程师，Java、Docker、Python、LLM均有涉猎。
---------------------------------------------------------------------
温柔地对待温柔的人，包容的三观就是最大的温柔。
---------------------------------------------------------------------
排序算法全解，为什么快排的时间波动特别大？
一、总览与对比分析
在本文中，我们将对各种排序算法进行总体比较，重点从以下几个维度展开：
-
时间复杂度（平均、最坏、最好）
-
空间复杂度
-
稳定性
-
是否原地排序
-
是否适合大数据
-
实际应用场景
二、快速排序
1、核心思想
使用分治法。
每次选择一个基准元素，将数组分成两个部分：小于基准值的放左边，大于的放右边，然后递归处理两边，直到完全结束。
2、算法特点
不稳定排序，原地排序。大多数通用排序任务中表现优异。
-
时间复杂度：平均O(n log n) ；最坏情况：O(n^2)
-
空间复杂度：O(log n)，递归栈空间
稳定排序：
当两个元素的值相等时，排序之后它们的相对顺序不会改变。
当你排序的是多字段对象，而且希望保留“主键不变”的排序顺序时，稳定性很关键。比如先按“姓名”排，再按“成绩”稳定排序，这样姓名相同的学生仍保持之前的顺序。
原地排序：
排序过程中只使用常数级别的额外空间（O(1)），排序操作直接在原数组上进行，不依赖额外的数据结构。
3、示例
// 简洁，但并非原地快排function quickSort(arr) { if (arr.length x x > pivot); return [...quickSort(left), pivot, ...quickSort(right)];}// 原地快排function quickSort(arr, low = 0, high = arr.length - 1) { if (low < high) { // 获取分区索引：pivot 已放在正确位置 const pivotIndex = partition(arr, low, high); // 递归排序 pivot 左右两部分 quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); } return arr; // 为了链式调用方便，可选}// 分区函数function partition(arr, low, high) { const pivot = arr[high]; // 选最后一个元素为 pivot let i = low; // i 表示小于等于 pivot 区域的边界 for (let j = low; j < high; j++) { // 如果当前元素 <= pivot，就把它放到左边区域 if (arr[j] <= pivot) { [arr[i], arr[j]] = [arr[j], arr[i]]; // 交换 i++; // 边界右移 } } // 最后把 pivot（arr[high]）放到它该在的位置 [arr[i], arr[high]] = [arr[high], arr[i]]; return i; // 返回 pivot 的最终位置}三、归并排序
1、核心思想
先分解后合并，分解成唯一个体了自然就是有序的，实际是一种基于递归的排序策略。
分解：将数组分成两半递归排序；合并：将两个有序数组合并成一个。
2、算法特点
稳定排序，不原地排序。适用于大数据量、稳定性要求强的场景，如外部排序、大型电商列表等。
-
时间复杂度：O(n log n)
-
空间复杂度：O(n)
3、示例
function mergeSort(arr) { if (arr.length <= 1) return arr; const mid = Math.floor(arr.length / 2); const left = mergeSort(arr.slice(0, mid)); const right = mergeSort(arr.slice(mid)); let result = [], i = 0, j = 0; while (i < left.length && j < right.length) { result.push(left[i] <= right[j] ? left[i++] : right[j++]); } return [...result, ...left.slice(i), ...right.slice(j)];}四、堆排序
1、核心思想
利用最大堆结构，每次把堆顶（最大值）放到数组末尾，重新调整堆。
2、算法特点
不稳定排序，原地排序。适用于无需稳定性要求、空间敏感场景。
-
时间复杂度：O(n log n)
-
空间复杂度：O(1)
3、示例
function heapSort(arr) { const n = arr.length; // 构建大顶堆，从最后一个非叶子节点开始 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) { heapify(arr, n, i); } // 依次取出堆顶元素，放到数组末尾 for (let i = n - 1; i > 0; i--) { [arr[0], arr[i]] = [arr[i], arr[0]]; // 交换堆顶与当前尾部 heapify(arr, i, 0); // 重新对堆顶元素调整堆 } return arr;}// 维护大顶堆的堆化过程function heapify(arr, heapSize, rootIndex) { let largest = rootIndex; const left = 2 * rootIndex + 1; const right = 2 * rootIndex + 2; // 找出三个节点中最大的那个 if (left arr[largest]) largest = left; if (right arr[largest]) largest = right; // 如果最大值不是根节点，交换并递归堆化 if (largest !== rootIndex) { [arr[rootIndex], arr[largest]] = [arr[largest], arr[rootIndex]]; heapify(arr, heapSize, largest); }}// 示例const arr = [4, 10, 3, 5, 1];console.log(heapSort(arr)); // 输出: [1, 3, 4, 5, 10]五、排序方法对比与其他排序
有一点需要注意，归并排序和堆排序的耗时都非常稳定，不管原始数据是整齐还是混乱，因为他们的执行流程不依赖于数据的初始顺序。但是快速排序耗时波动大，快排的性能高度依赖于“划分是否平衡”，而这个又与基准值的选择以及原始数据分布密切相关。
相对来说，堆排序不如归并排序和快排常用，虽然堆排序的时间复杂度稳定，但在实际运行中堆的 heapify 操作涉及大量的父子节点交换，不如快排那样直接交换元素高效，且堆是树形结构，访问内存不是连续的，会导致 CPU 缓存命中率低，最后还不是稳定排序，虽然快速排序也不是稳定排序，但那是快排快啊。
常见通用排序方法里面，只有快速排序、归并排序和堆排序的时间复杂度最优，像冒泡排序、插入排序、选择排序、希尔排序时间复杂度都要逊色一些。
但有些排序方法，在特殊场景下的时间复杂度优于O(n log n)，这里不详细介绍。
六、总结
简单做一个“技术选型”的场景推荐：
-
若数据量大，推荐 归并 或 堆排序
-
对性能极致要求时，快排更合适（但注意最坏 O(n²)）
-
对空间敏感：选择堆排序
-
数据几乎有序：插入排序
-
数字范围小或分布均匀：计数/桶排序
-
大批量整数：基数排序
只有锻炼思维才能可持续地解决问题，只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助，麻烦您点个赞支持一下，还可以收藏起来以备不时之需，有疑问和错误欢迎在评论区指出~
其他热门文章，请关注：
极致的灵活度满足工程美学：用Vue Flow绘制一个完美流程图
你真的会使用Vue3的onMounted钩子函数吗？Vue3中onMounted的用法详解
Web Worker：让前端飞起来的隐形引擎
DeepSeek：全栈开发者视角下的AI革命者
通过array.filter()实现数组的数据筛选、数据清洗和链式调用
测评：这B班上的值不值？在不同城市过上同等生活水平到底需要多少钱？
通过Array.sort() 实现多字段排序、排序稳定性、随机排序洗牌算法、优化排序性能
TreeSize：免费的磁盘清理与管理神器，解决C盘爆满的燃眉之急
通过MongoDB Atlas 实现语义搜索与 RAG——迈向AI的搜索机制
深入理解 JavaScript 中的 Array.find() 方法：原理、性能优势与实用案例详解
前端实战：基于Vue3与免费满血版DeepSeek实现无限滚动+懒加载+瀑布流模块及优化策略
el-table实现动态数据的实时排序，一篇文章讲清楚elementui的表格排序功能
JavaScript双问号操作符（??）详解，解决使用 || 时因类型转换带来的问题
【前端实战】如何让用户回到上次阅读的位置？
内存泄漏——海量数据背后隐藏的项目生产环境崩溃风险！如何避免内存泄漏
MutationObserver详解+案例——深入理解 JavaScript 中的 MutationObserver
JavaScript中通过array.map(）实现数据转换、创建派生数组、异步数据流处理、DOM操作等
高效工作流：用Mermaid绘制你的专属流程图；如何在Vue3中导入mermaid绘制流程图
