快速排序的工作原理是基于“分而治之”策略，通过选择基准、分区和递归排序三个步骤实现高效排序：首先从数组中选择一个基准元素，然后将数组划分为两部分，左边为小于基准的元素，右边为大于或等于基准的元素，此时基准位于最终有序位置；接着对左右两个子数组递归执行相同操作，直到子数组长度小于等于1，整个数组即有序。该算法平均时间复杂度为o(n log n)，最坏情况下为o(n²)，空间复杂度平均为o(log n)；常见优化包括随机或三数取中法选择基准、小规模数据切换插入排序、三路分区处理重复元素以及尾递归或迭代实现以降低栈深度，从而提升整体性能和稳定性。
快速排序，说白了，就是一种非常高效的排序算法。它的核心思想是“分而治之”：你先从数组里挑一个元素，叫它“基准”（pivot），然后把数组里所有比基准小的元素都挪到基准的左边，比基准大的挪到右边。这样一来，基准就到了它最终该待的位置。接下来，你只要对基准左右两边的子数组重复这个过程，直到所有元素都归位，整个数组也就排好序了。它快就快在，每一步都能把问题规模缩小一大截。
/**
* 快速排序的JavaScript实现
*
* @param {Array<number>} arr - 需要排序的数组
* @returns {Array<number>} 排序后的数组
*/
function quickSort(arr) {
// 递归的终止条件：如果数组为空或只有一个元素，它已经是排序好的
if (arr.length <= 1) {
return arr;
}
// 选择一个基准元素。这里我习惯选择数组的最后一个元素作为基准，
// 但其实选择中间的、第一个的，甚至是随机的都可以，各有优缺点。
const pivot = arr[arr.length - 1];
// 移除基准元素，因为我们后续要把它插入到正确的位置
const remainingArr = arr.slice(0, arr.length - 1);
// 两个空数组，用来存放比基准小的和比基准大的元素
const left = [];
const right = [];
// 遍历剩余的数组，将元素分配到左右两边
for (let i = 0; i < remainingArr.length; i++) {
if (remainingArr[i] < pivot) {
left.push(remainingArr[i]);
} else {
// 这里包含了等于基准的元素，通常放在右边，也可以单独处理
right.push(remainingArr[i]);
}
}
// 递归地对左右两边的子数组进行排序，然后将它们、基准、以及右边排序后的结果拼接起来
// 这种实现方式虽然直观，但在内存消耗上可能不如原地交换的实现。
return [...quickSort(left), pivot, ...quickSort(right)];
}
// 示例用法：
// const unsortedArray = [3, 6, 8, 10, 1, 2, 1];
// const sortedArray = quickSort(unsortedArray);
// console.log(sortedArray); // 输出: [1, 1, 2, 3, 6, 8, 10]
// 注意：上述实现是“非原地”的，因为它创建了新的数组。
// 实际生产环境中，为了性能和内存效率，更常见的是“原地”交换元素的实现，
// 那会涉及更多的指针操作和数组元素的直接交换。
// 例如：
/*
function quickSortInPlace(arr, low, high) {
if (low < high) {
let pi = partition(arr, low, high);
quickSortInPlace(arr, low, pi - 1);
quickSortInPlace(arr, pi + 1, high);
}
}
function partition(arr, low, high) {
let pivot = arr[high];
let i = (low - 1); // Index of smaller element
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]]; // Swap
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Swap pivot
return i + 1;
}
// 调用示例：
// const unsortedArrayInPlace = [3, 6, 8, 10, 1, 2, 1];
// quickSortInPlace(unsortedArrayInPlace, 0, unsortedArrayInPlace.length - 1);
// console.log(unsortedArrayInPlace); // 输出: [1, 1, 2, 3, 6, 8, 10]
*/快速排序的“分而治之”策略，在我看来，是它最迷人的地方。它不像某些排序算法那样一步一个脚印地比较和交换，而是有点像一场递归的“分治战争”。一开始，你面对的是一个大乱斗的数组，你的任务是把它整理好。
这个过程通常分为三步：
选择基准（Pivot Selection）： 这是第一步，也是很关键的一步。你需要从数组中挑一个元素作为“基准”。基准的选择方式有很多种，比如选第一个、最后一个、中间的，甚至随机选一个。不同的选择策略会对算法的性能产生影响，尤其是在处理特定输入（比如已经部分有序的数组）时。我个人在实现时，如果不是特别追求极致性能或处理特定数据，通常会选择最后一个元素，因为它比较直观。
分区（Partitioning）： 选定基准后，下一步就是把数组分成两部分。所有比基准小的元素都放到基准的左边，所有比基准大的元素都放到基准的右边。这个过程完成后，基准元素就“归位”了，它现在所在的位置就是它在最终排序数组中的位置。这一步是快速排序的灵魂所在，它通过一系列的元素交换来完成，确保基准两侧的元素满足大小关系。想象一下，你把一堆大小不一的石头，按照某个标准（基准）分成两堆，小的放一边，大的放另一边，基准石子就放在中间。
递归排序（Recursive Sort）： 完成分区后，基准左右两边的子数组还是无序的。但好消息是，它们现在是独立的、更小的排序问题了。所以，快速排序会对自己左右两边的子数组重复执行上述的“选择基准”和“分区”操作，直到子数组的长度变得非常小（比如只剩一个元素或为空），这时它们自然就是有序的。这种递归调用，一层层地把问题分解，再一层层地合并结果，最终就得到了一个完全有序的数组。
谈到性能，快速排序绝对是排序算法中的明星选手，但它也有自己的“脾气”。它的性能表现，用大O表示法来说，平均情况和最好情况都是 O(n log n)。这意味着，当处理的数据量 n 增大时，它的运行时间增长得相对缓慢，非常高效。
时间复杂度：
空间复杂度：
虽然最坏情况 O(n²) 听起来有点吓人，但在实际应用中，通过一些优化技巧（比如随机选择基准、三数取中等），以及现代编程语言运行时对递归的优化，快速排序很少会退化到最坏情况。它依然是许多标准库中默认的排序算法，或者作为其他高级排序算法（如混合排序）的组成部分。
快速排序虽然很快，但它并非没有提升空间。针对它的一些“弱点”，比如最坏情况的性能，或者递归深度，社区里发展出了一些非常实用的优化策略。
优化基准选择（Pivot Selection）：
处理小规模子数组：
尾递归优化（Tail Recursion Optimization）：
优化分区过程（Partitioning）：
这些优化并非孤立存在，很多时候它们会结合使用，共同提升快速排序在各种场景下的表现。
以上就是快速排序是什么？快速排序的JS实现的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
583
收藏
