排序算法全解，为什么快排的时间波动特别大？

作者：watermelo37

ZEEKLOG全栈领域优质创作者、万粉博主、华为云云享专家、阿里云专家博主、腾讯云“创作之星”特邀作者、支付宝合作作者，全平台博客昵称watermelo37。

一个假装是giser的coder，做不只专注于业务逻辑的前端工程师，Java、Docker、Python、LLM均有涉猎。

---------------------------------------------------------------------

温柔地对待温柔的人，包容的三观就是最大的温柔。

---------------------------------------------------------------------

排序算法全解，为什么快排的时间波动特别大？

一、总览与对比分析

在本文中，我们将对各种排序算法进行总体比较，重点从以下几个维度展开：

时间复杂度（平均、最坏、最好）
空间复杂度
稳定性
是否原地排序
是否适合大数据
实际应用场景

算法	最好时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	原地排序	适用场景
快速排序	O(n log n)	O(n log n)	O(n^2)	O(log n)	否	是	大多数通用场景
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	是	否	大数据、稳定需求
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	否	是	内存受限、无稳定性需求
插入排序	O(n)	O(n^2)	O(n^2)	O(1)	是	是	数据基本有序、小数组
桶排序	O(n+k)	O(n+k)	O(n^2)	O(n+k)	是	否	数据分布均匀
基数排序	O(nk)	O(nk)	O(nk)	O(n+k)	是	否	整数或字符串排序
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	是	是	教学演示

二、快速排序

1、核心思想

使用分治法。

每次选择一个基准元素，将数组分成两个部分：小于基准值的放左边，大于的放右边，然后递归处理两边，直到完全结束。

2、算法特点

不稳定排序，原地排序。大多数通用排序任务中表现优异。

时间复杂度：平均O(n log n) ；最坏情况：O(n^2)
空间复杂度：O(log n)，递归栈空间

稳定排序：

        当两个元素的值相等时，排序之后它们的相对顺序不会改变。

        当你排序的是多字段对象，而且希望保留“主键不变”的排序顺序时，稳定性很关键。比如先按“姓名”排，再按“成绩”稳定排序，这样姓名相同的学生仍保持之前的顺序。

原地排序：

        排序过程中只使用常数级别的额外空间（O(1)），排序操作直接在原数组上进行，不依赖额外的数据结构。

3、示例

// 简洁，但并非原地快排 function quickSort(arr) { if (arr.length <= 1) return arr; const pivot = arr[0]; const left = arr.slice(1).filter(x => x <= pivot); const right = arr.slice(1).filter(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 < heapSize && arr[left] > arr[largest]) largest = left; if (right < heapSize && arr[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 + k)	整数且范围小（如 0~100）
桶排序	O(n + k)	分布均匀的浮点数
基数排序	O(n · d)	多位数或字符串，d 为位数