JavaScript 实现快速排序算法详解

快速排序（Quicksort）是一种高效的分治（Divide and Conquer）排序算法，由东尼·霍尔（Tony Hoare）在1960年提出。由于其平均情况下具有 O(n \log n) 的时间复杂度，并且在实际应用中性能优异，快速排序在编程面试和实际开发中被广泛使用。本篇文章将详细介绍快速排序的原理、在JavaScript中的多种实现方法、时间复杂度分析以及优化策略。

快速排序的基本原理

快速排序通过以下步骤对数组进行排序：

1. 选择基准元素（Pivot）： 从数组中选取一个元素作为基准。常见的选择方法包括选择第一个元素、最后一个元素、中间元素或随机选择。
2. 分区（Partitioning）： 重新排列数组，使得所有比基准小的元素放在基准的左侧，所有比基准大的元素放在基准的右侧。基准元素的位置确定后，它在排序后的数组中的位置就是最终位置。
3. 递归排序： 递归地对基准左侧和右侧的子数组进行快速排序，直到子数组的长度为零或一，排序完成。

快速排序的效率主要依赖于基准的选择，最优情况下，快速排序的时间复杂度为 O(n \log n)，而最坏情况下（例如每次选择的基准都是最大或最小元素，如已排序的数组），时间复杂度为 O(n^2)。

JavaScript 中快速排序的实现方法

在JavaScript中，实现快速排序的方法有多种，以下介绍其中的几种常见实现方式，包括递归实现（非原地排序）、原地排序以及三路快速排序。

方法一：递归实现（非原地排序）

这种方法通过递归地对数组进行分区和排序，不在原数组上进行操作，而是使用额外的数组来存储分区结果，适合用于函数式编程风格。

代码实现：

function quickSort(arr) {
        // 基线条件：如果数组长度小于或等于1，则无需排序
        if (arr.length <= 1) {
            return arr;
        }
        
        // 选择基准值（这里选择中间元素）
        const pivotIndex = Math.floor(arr.length / 2);
        const pivot = arr[pivotIndex];
        
        // 初始化左右数组
        const left = [];
        const right = [];
        
        // 遍历数组，将元素根据基准值分到左右数组中
        for (let i = 0; i < arr.length; i++) {
            if (i === pivotIndex) continue; // 跳过基准值
            if (arr[i] < pivot) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        
        // 递归排序并合并结果
        return [...quickSort(left), pivot, ...quickSort(right)];
    }

使用示例：

const array = [64, 34, 25, 12, 22, 11, 90];
    console.log("排序前：", array);
    const sortedArray = quickSort(array);
    console.log("排序后：", sortedArray);
// 输出：
// 排序前： [64, 34, 25, 12, 22, 11, 90]
// 排序后： [11, 12, 22, 25, 34, 64, 90]

代码解析：

1. 基线条件： 如果数组长度小于或等于1，则直接返回该数组，因为无需排序。
2. 选择基准元素： 选取数组的中间元素作为基准值，以减少最坏情况发生的概率。
3. 分割数组： 初始化两个空数组 left 和 right，遍历原数组，将小于基准值的元素放入 left，大于或等于基准值的元素放入 right。
4. 递归排序和合并： 递归调用 quickSort 对 left 和 right 数组进行排序，然后合并排序后的左数组、基准值和右数组，形成最终的有序数组。

此实现方式逻辑清晰，适合理解快速排序的基本原理，但在处理非常大的数组或递归深度较大的情况下，可能导致栈溢出或性能问题。

方法二：原地排序（In-Place QuickSort）

为了减少空间复杂度，可以采用原地排序的方法，直接在原数组上进行操作，避免创建额外的数组。

代码实现：

function quickSortInPlace(arr, low = 0, high = arr.length - 1) {
        if (low < high) {
            // 划分数组，得到基准值的位置
            const pivotIndex = partition(arr, low, high);
            
            // 递归对左右区间排序
            quickSortInPlace(arr, low, pivotIndex - 1);
            quickSortInPlace(arr, pivotIndex + 1, high);
        }
        return arr;
    }

    function partition(arr, low, high) {
        // 使用数组最后一个元素作为基准值
        const pivot = arr[high];
        let i = low - 1; // i 是左区间的尾部指针

        // 遍历 low 到 high-1 区间，将小于基准的元素放在左区间
        for (let j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                [arr[i], arr[j]] = [arr[j], arr[i]]; // 交换元素
            }
        }

        // 把基准元素放到正确位置
        [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
        return i + 1; // 返回基准值的位置
    }

使用示例：

const array = [64, 34, 25, 12, 22, 11, 90];
    console.log("排序前：", array);
    quickSortInPlace(array);
    console.log("排序后：", array);
// 输出：
// 排序前： [64, 34, 25, 12, 22, 11, 90]
// 排序后： [11, 12, 22, 25, 34, 64, 90]

代码解析：

1. quickSortInPlace 函数： 接收数组、左边界和右边界。若左边界小于右边界，则调用 partition 函数进行分区，得到基准元素的索引 pivotIndex，然后递归地对左边和右边的子数组进行快速排序。
2. partition 函数： 选择数组的最后一个元素作为基准值。通过遍历数组，将比基准值小的元素移动到左边，最终将基准元素放置到正确的位置，并返回其索引。

原地排序的优缺点：

• 优点： 降低了空间复杂度，仅需常数额外空间，空间复杂度为 O(log n)（递归调用栈的深度）。
• 缺点： 实现较为复杂，需要额外处理数组交换和指针操作。

方法三：三路快速排序

针对含有大量重复元素的数组，三路快速排序可以提升效率，将数组分为小于基准、等于基准和大于基准的三个部分。

代码实现：

function quickSort3Way(arr, low = 0, high = arr.length - 1) {
        if (low >= high) {
            return;
        }

        const pivot = arr[low];
        let lt = low;       // arr[low...lt-1] < pivot
        let gt = high;      // arr[gt+1...high] > pivot
        let i = low + 1;    // arr[lt...i-1] == pivot

        while (i <= gt) {
            if (arr[i] < pivot) {
                [arr[lt], arr[i]] = [arr[i], arr[lt]];
                lt++;
                i++;
            } else if (arr[i] > pivot) {
                [arr[i], arr[gt]] = [arr[gt], arr[i]];
                gt--;
            } else {
                i++;
            }
        }

        quickSort3Way(arr, low, lt - 1);
        quickSort3Way(arr, gt + 1, high);

        return arr;
    }

使用示例：

const array = [3, 6, 8, 3, 3, 10, 1, 2, 1];
    console.log("排序前：", array);
    quickSort3Way(array);
    console.log("排序后：", array);
// 输出：
// 排序前： [3, 6, 8, 3, 3, 10, 1, 2, 1]
// 排序后： [1, 1, 2, 3, 3, 3, 6, 8, 10]

代码解析：

1. quickSort3Way 函数： 采用三路分区的方法，将数组划分为小于、等于和大于基准的三部分。
2. 变量说明：
   • lt：指向小于基准的区域末尾。
   • gt：指向大于基准的区域起始。
   • i：当前遍历的位置。
3. 分区过程： 遍历数组，根据元素与基准的比较结果调整 lt、gt 和 i 的位置，实现三路分区。

三路快速排序的优缺点：

• 优点： 针对大量重复元素时，减少了比较次数，提高了排序效率。
• 缺点： 实现相对复杂，但在处理特定数据集时性能表现更佳。

时间复杂度分析

快速排序的时间复杂度取决于基准值的选择及数组的分布情况：

• 最优情况： 基准能够将数组均匀分割，时间复杂度为 O(n \log n)。
• 最坏情况： 每次选择的基准是当前数组的最大或最小值，导致时间复杂度为 O(n²)。
• 平均情况： 对于随机数据，平均时间复杂度为 O(n \log n)。

优化策略

为了提升快速排序的性能，尤其是在处理特定数据集时，可以采用以下优化策略：

1. 基准选择优化： 选择一个好的基准可以有效避免最坏情况。常用的方法包括随机选择基准元素或选择“三数取中”（即取数组的第一个、最后一个和中间元素的中位数）。
2. 三路快速排序： 对于含有大量重复元素的数组，使用三路快速排序可以减少比较次数，提高效率。
3. 尾递归优化： 通过优化递归顺序，减少递归深度，避免栈溢出。
4. 切换到其他排序算法： 当子数组的大小小于某个阈值时，可以切换到插入排序等其他排序算法，以减少递归调用带来的开销。

原地排序 vs. 非原地排序

• 非原地排序（使用额外数组）：
  • 优点：逻辑清晰，代码更容易理解和实现。
  • 缺点：需要额外的空间存储分区，空间复杂度较高（O(n)）。
• 原地排序（就地操作）：
  • 优点：降低了空间复杂度（O(log n)）。
  • 缺点：代码更复杂，需要额外处理数组交换和指针操作。

空间复杂度

• 非原地版本： 额外的数组导致空间复杂度为 O(n)。
• 原地版本： 仅需常数额外空间，空间复杂度为 O(log n)（递归调用栈的深度）。

参考文档

1. 快速排序的 JavaScript 实现 - 阮一峰
2. 用 JavaScript 实现快速排序 - 掘金
3. Js实现快速排序（代码+讲解） - CSDN博客
4. js算法-快速排序(Quicksort) - 深入前端 - SegmentFault 思否

结论

快速排序是一种高效且广泛应用的排序算法，在JavaScript中有多种实现方式。通过理解其原理和不同的实现方法，您可以根据具体需求选择最适合的快速排序算法。非原地排序方法适合于简单实现和理解，而原地排序方法在处理大规模数据时更为高效。针对特定数据集，诸如三路快速排序等优化策略可以进一步提升性能。同时，合理选择基准元素和优化递归深度也是提升快速排序性能的关键。了解这些实现细节和优化策略，有助于在大型数据集或特定场景下有效地应用快速排序，提高应用程序的整体性能。

如果您对快速排序的具体实现有更多疑问或需要进一步的优化建议，欢迎参考上述提供的在线资源，获取详细的代码示例和深入的讲解。