快速排序 Quick Sort

Guide

• 原理
• 实现
• 时空复杂度
• 优化
• 使用场景
• 参考文献

原理

核心思想：分治

1. 选择基准（Pivot）：任取一个数组元素，一般是首、中、尾。

2. 分区（Partition）：遍历数组，将比基准小的元素移动到基准的左侧，比基准大的元素移动到基准的右侧。

3. 递归（Recursion）：对这两部分分别进行快速排序，直到数组完全有序。

实现

更简单的理解方式：创建 < = > 三个额外数组，这样做还可以让算法稳定。

// 三路稳定快排
function quickSort(nums) {
    if (nums.length <= 1) {
        return nums;
    }

    const pivot = nums[nums.length - 1]; // 选取数组尾元素为基准
    let [smaller, equal, larger] = [[], [], []];

    for (let num of nums) {
        if (num < pivot) {
            smaller.push(num);
        } else if (num === pivot) {
            equal.push(num);
        } else {
            larger.push(num);
        }
    }

    return [...quickSort(smaller), ...equal, ...quickSort(larger)];
}

const arr = [2, 9, 2, 1, 10, 0, 5, 7, 6, 3];
console.log(quickSort(arr)); // [0, 1, 2, 2, 3, 5, 6, 7, 9, 10]

时空复杂度

• 时间复杂度：

  • 最好情况：O(nlogn), 在理想情况下，每次分区都能将数组对半分。

  • 最坏情况：O(n^2), 若每次选择的基准都为最大或最小值，则会导致分区极不平衡。

  • 平均情况：O(nlogn)

• 空间复杂度：

  • 原地排序：O(log n), 主要消耗在递归调用的系统栈上。

  • 非原地排序：O(n), 使用额外数组来存储小于/等于/大于基准的元素。

优化

1. 基准选择优化：避免最坏情况。

   • 随机选择一个元素作为基准。

   • 三数取中法：取数组首、中、尾三个位置的元素里的中值作为基准。

2. 分区优化：减少遍历、比较的次数。

   • 双指针法：使用两个指针分别从数组两端向中间扫描，原地交换位置，减少遍历次数。

   • 三路快排：将数组分为小于、等于、大于基准的三部分，减少不必要的交换操作。上文实现即基于此优化。

3. 尾递归（Tail Recursion）优化：将递归改写为迭代，或者在递归中先处理较小的子数组，减少递归深度，避免栈溢出。

   尾递归是指在一个函数的最后一步直接返回递归调用的结果，且不再进行任何额外的计算或操作。 这样，编译器或解释器可以对尾递归进行优化，将递归调用转换为迭代，从而避免增加调用栈的深度，提高性能。

   上文实现并不是尾递归，因为在递归调用后，还需要对三个数组进行拼接，这属于额外操作，因此递归调用并不在函数的最后一步。

   涉及前端开发的 TCO 相关：

   • ECMAScript 2015（ES6）规范：在 ECMAScript 2015 标准中，引入了对尾调用优化（Tail Call Optimization, TCO）的支持 （尾递归是尾调用的特殊形式，即在函数末尾调用自己）。

     • 严格模式下的尾调用优化：标准规定，只有在严格模式 'use strict';下，尾调用优化才可能被应用。

     • 要求：尾调用必须是函数的最后一步，不能有额外的操作，调用参数也不应涉及副作用。

   • 标准支持并非强制：需要注意的是，ECMAScript 规范并未强制要求 JavaScript 引擎必须实现尾调用优化，这取决于具体的引擎实现。

     • 关于 V8（Chrome 和 Node.js），自 v11.2 版本起支持 TCO。

     • 关于 SpiderMonkey（Firefox），不支持 TCO。

     • 关于 JavaScriptCore（Safari），支持 TCO。

4. 混合排序优化：对于小数组，使用插入排序。

   • 插入排序的时间复杂度为 O(n^2)，但插入排序在小数组上的性能可能优于快速排序。

   • 可以设置一个「阈值」¹，当数组长度小于该阈值时，使用插入排序。

使用场景

规模较大的数组排序，且对时间复杂度要求较高的场景。

参考文献

• 快速排序算法

• ECMAScript 2015 Language Specification

• V8 官方博客：WebAssembly tail calls