快速排序原理与JS实现详解

在IT行业这个发展更新速度很快的行业，只有不停止的学习，才不会被行业所淘汰。如果你是文章学习者，那么本文《快速排序原理及JS实现方法》就很适合你！本篇内容主要包括##content_title##，希望对大家的知识积累有所帮助，助力实战开发！

快速排序的工作原理是基于“分而治之”策略，通过选择基准、分区和递归排序三个步骤实现高效排序：首先从数组中选择一个基准元素，然后将数组划分为两部分，左边为小于基准的元素，右边为大于或等于基准的元素，此时基准位于最终有序位置；接着对左右两个子数组递归执行相同操作，直到子数组长度小于等于1，整个数组即有序。该算法平均时间复杂度为O(n log n)，最坏情况下为O(n²)，空间复杂度平均为O(log n)；常见优化包括随机或三数取中法选择基准、小规模数据切换插入排序、三路分区处理重复元素以及尾递归或迭代实现以降低栈深度，从而提升整体性能和稳定性。

快速排序，说白了，就是一种非常高效的排序算法。它的核心思想是“分而治之”：你先从数组里挑一个元素，叫它“基准”（pivot），然后把数组里所有比基准小的元素都挪到基准的左边，比基准大的挪到右边。这样一来，基准就到了它最终该待的位置。接下来，你只要对基准左右两边的子数组重复这个过程，直到所有元素都归位，整个数组也就排好序了。它快就快在，每一步都能把问题规模缩小一大截。

/**
 * 快速排序的JavaScript实现
 *
 * @param {Array} arr - 需要排序的数组
 * @returns {Array} 排序后的数组
 */
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]
*/

快速排序的工作原理是怎样的？

快速排序的“分而治之”策略，在我看来，是它最迷人的地方。它不像某些排序算法那样一步一个脚印地比较和交换，而是有点像一场递归的“分治战争”。一开始，你面对的是一个大乱斗的数组，你的任务是把它整理好。

这个过程通常分为三步：

1. 选择基准（Pivot Selection）： 这是第一步，也是很关键的一步。你需要从数组中挑一个元素作为“基准”。基准的选择方式有很多种，比如选第一个、最后一个、中间的，甚至随机选一个。不同的选择策略会对算法的性能产生影响，尤其是在处理特定输入（比如已经部分有序的数组）时。我个人在实现时，如果不是特别追求极致性能或处理特定数据，通常会选择最后一个元素，因为它比较直观。

2. 分区（Partitioning）： 选定基准后，下一步就是把数组分成两部分。所有比基准小的元素都放到基准的左边，所有比基准大的元素都放到基准的右边。这个过程完成后，基准元素就“归位”了，它现在所在的位置就是它在最终排序数组中的位置。这一步是快速排序的灵魂所在，它通过一系列的元素交换来完成，确保基准两侧的元素满足大小关系。想象一下，你把一堆大小不一的石头，按照某个标准（基准）分成两堆，小的放一边，大的放另一边，基准石子就放在中间。

3. 递归排序（Recursive Sort）： 完成分区后，基准左右两边的子数组还是无序的。但好消息是，它们现在是独立的、更小的排序问题了。所以，快速排序会对自己左右两边的子数组重复执行上述的“选择基准”和“分区”操作，直到子数组的长度变得非常小（比如只剩一个元素或为空），这时它们自然就是有序的。这种递归调用，一层层地把问题分解，再一层层地合并结果，最终就得到了一个完全有序的数组。

快速排序的性能表现如何？

谈到性能，快速排序绝对是排序算法中的明星选手，但它也有自己的“脾气”。它的性能表现，用大O表示法来说，平均情况和最好情况都是 O(n log n)。这意味着，当处理的数据量 n 增大时，它的运行时间增长得相对缓慢，非常高效。

• 时间复杂度：

  • 平均情况：O(n log n)。 为什么是 n log n 呢？每次分区操作，我们都会遍历一次当前子数组的所有元素（O(n)），然后把问题规模大致减半。这种“分而治之”的模式，很自然地就导向了 log n 的层级。所以，总的来说就是 n 乘以 log n。在实际应用中，快速排序的常数因子通常很小，这让它在大多数情况下表现得比其他 O(n log n) 的算法（如归并排序）更快。
  • 最好情况：O(n log n)。 当每次分区都能把数组完美地一分为二时（比如基准总是选中了中位数），就达到了最好情况。
  • 最坏情况：O(n²)。 这是快速排序的“阿喀琉斯之踵”。如果每次都选到了一个极端值作为基准（比如数组已经完全有序，或者完全逆序，而你总是选第一个或最后一个），那么每次分区都只会把一个元素放到正确位置，而另一个子数组的长度只减少了1。这样一来，你就相当于做了 n 次 O(n) 的操作，总时间复杂度就退化成了 O(n²)，跟冒泡排序差不多了。这种情况下，它的效率会变得非常低。

• 空间复杂度：

  • 平均情况：O(log n)。 这主要是因为递归调用栈的开销。每次递归都会在调用栈上压入一个帧，而分治的深度是 log n。
  • 最坏情况：O(n)。 如果不幸遇到了最坏时间复杂度的情况（比如每次分区都只分出一个元素），那么递归深度就会达到 n，导致调用栈的开销也达到 O(n)。

虽然最坏情况 O(n²) 听起来有点吓人，但在实际应用中，通过一些优化技巧（比如随机选择基准、三数取中等），以及现代编程语言运行时对递归的优化，快速排序很少会退化到最坏情况。它依然是许多标准库中默认的排序算法，或者作为其他高级排序算法（如混合排序）的组成部分。

快速排序有哪些常见的优化技巧？

快速排序虽然很快，但它并非没有提升空间。针对它的一些“弱点”，比如最坏情况的性能，或者递归深度，社区里发展出了一些非常实用的优化策略。

1. 优化基准选择（Pivot Selection）：

   • 随机选择基准： 这是最常用也最有效的优化之一。不是固定选择第一个或最后一个元素，而是从当前子数组中随机挑选一个元素作为基准。这样大大降低了遇到最坏情况的概率，因为随机性使得任何特定输入序列都很难持续导致最坏行为。
   • 三数取中法（Median-of-Three）： 这种方法通常是选择子数组的第一个、中间和最后一个元素，然后取这三个数的中位数作为基准。这样做的好处是，选到极端值的概率比随机选择更低，从而减少了遇到最坏情况的可能性，同时也不会引入太大的额外计算开销。我个人很喜欢这种方法，因为它兼顾了性能和稳定性。

2. 处理小规模子数组：

   • 当递归到子数组的长度非常小（比如小于10或20个元素，这个阈值需要根据实际测试来确定）时，快速排序的效率其实并不高，因为递归调用的开销相对于排序本身的工作量来说变得显著。
   • 一个常见的优化是，当子数组长度小于某个阈值时，不再递归调用快速排序，而是切换到其他更适合小规模数据的排序算法，比如插入排序（Insertion Sort）。插入排序在处理小规模、接近有序的数据时表现非常出色，并且它的常数因子很小。这种混合排序策略，能有效提升整体性能。

3. 尾递归优化（Tail Recursion Optimization）：

   • 在一些支持尾递归优化的语言（比如某些函数式语言）中，如果快速排序的递归调用是尾调用，编译器或解释器可以将其优化为迭代，从而避免了过深的递归栈。虽然JavaScript引擎在某些情况下可能会对尾调用进行优化，但并不能完全依赖它来避免所有递归深度问题。
   • 如果需要完全避免递归栈溢出，可以考虑将快速排序改写为迭代版本，通过手动维护一个栈来模拟递归过程。这会增加代码的复杂性，但在对内存和栈深度有严格要求的场景下非常有用。

4. 优化分区过程（Partitioning）：

   • 处理相等元素： 原始的快速排序在处理大量重复元素时，效率会下降。如果所有元素都相等，它仍然会退化到 O(n²) 的情况。一种优化是，在分区时，将与基准相等的元素单独放在基准的中间，形成三路分区（Dutch National Flag Problem）。这样，下一次递归就只需要处理比基准小和比基准大的两个子数组，而跳过了相等的元素，从而显著提高了处理重复元素时的效率。

这些优化并非孤立存在，很多时候它们会结合使用，共同提升快速排序在各种场景下的表现。

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~