JavaScript 快速排序算法详解与实现

作者：纸飞机

时间：2026-10-22

本文详细解析了 JavaScript 中快速排序的实现原理，包括选取基准值、分区操作及递归处理。文章列出了平均 O(nlogn)、最差 O(n*n) 的时间复杂度及 O(logn) 的空间复杂度，并指出其不稳定性。通过具体代码示例展示了如何利用 splice 和 concat 方法完成排序，适合希望深入理解排序算法的开发者参考。

文章目录

JavaScript 快速排序算法详解与实现

本文分享了 JavaScript 中快速排序的具体实现代码，供读者参考学习。

前置概念说明

时间复杂度用于衡量算法执行所需的时间消耗；空间复杂度指程序运行过程中占用的内存大小。稳定性方面，若两个元素值相等（a=b），排序前 a 在 b 之前，排序后若 a 仍在 b 之前，则称为稳定排序；反之，若排序后位置可能交换，则称为不稳定排序。

JavaScript 快速排序实现

核心原理

快速排序的基本思路是从数组中选取一个基准值（pivot），将数组其余元素与该基准值进行比较：小于基准值的元素放入一个新数组，大于或等于基准值的元素放入另一个新数组。随后对这两个新数组递归执行相同操作，直到子数组中仅剩一个元素或为空，此时排序完成。

性能指标与稳定性分析

平均时间复杂度为 O(nlogn)
最好情况下的时间复杂度为 O(nlogn)
最差情况下的时间复杂度为 O(n*n)
空间复杂度为 O(logn)
该算法属于不稳定排序

快速排序的代码实现


var examplearr=[8,94,15,88,55,76,21,39];
function fastsort(arr){
  if(arr.length<2){
    return arr;
  }
  var left=[];
  var right=[];
  var pivotIndex=Math.floor(arr.length/2);
  var pivot=arr.splice(pivotIndex,1)[0];
  for(i=0;i<arr.length;i++){
    if(arr[i]<pivot){
      left.push(arr[i]);
    }else{
      right.push(arr[i])
    }
  }
  return fastsort(left).concat([pivot],fastsort(right));
}
console.log(fastsort(examplearr));