JS手写3种快速排序算法，小白到大神都爱不释手！

本文深入解析了JavaScript实现数组快速排序的三种经典方案，助你彻底掌握这一高效算法！快速排序作为一种基于“分而治之”策略的排序算法，通过选取基准值将数组划分为左右两部分，递归排序子数组。文章详细介绍了Lomuto分区、Hoare分区以及随机化快速排序三种实现方式。Lomuto方案简单直观，但易导致分区不平衡；Hoare方案效率更高，尤其适合已部分排序的数据；随机化方案则通过随机选取基准值，有效避免最坏情况，提升平均性能。此外，文章还分析了三种方案的优缺点及适用场景，并探讨了快速排序的空间复杂度，助你根据实际需求选择最优方案，提升代码效率。

快速排序是一种基于“分而治之”策略的高效排序算法，其核心是选定一个基准值，将数组分为两部分，使得左边元素小于基准值，右边元素大于基准值，然后递归地对左右子数组排序。文章介绍了三种JavaScript实现方案：1. Lomuto分区方案选择最后一个元素为基准，通过指针i划分边界，优点简单直观但易导致分区不平衡；2. Hoare分区方案使用双指针从两端向中间扫描并交换元素，效率更高，尤其适用于已部分排序的数据；3. 随机化快速排序在每次分区时随机选择基准值，避免最坏情况，提升平均性能。三者中，Lomuto适合教学理解，Hoare更高效但代码复杂，随机化方案通常最优。此外，快速排序空间复杂度理想为O(log n)，最坏情况下退化为O(n)，随机化可有效改善此问题。

快速排序，简单来说，就是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

解决方案

快速排序的核心在于“分而治之”，选定一个基准值，将数组分成两部分，小于基准值的放左边，大于基准值的放右边，然后递归地对左右两部分进行排序。下面分享三种常见的JavaScript快速排序实现方案。

副标题1： 经典快速排序（Lomuto 分区方案）

Lomuto 分区方案是快速排序最经典也是最容易理解的实现方式。它选择数组的最后一个元素作为基准值，并使用一个指针 i 来跟踪小于基准值的元素的边界。

function quickSortLomuto(arr, low, high) {
  if (low < high) {
    let partitionIndex = partitionLomuto(arr, low, high);

    quickSortLomuto(arr, low, partitionIndex - 1);
    quickSortLomuto(arr, partitionIndex + 1, high);
  }
  return arr;
}

function partitionLomuto(arr, low, high) {
  let pivot = arr[high];
  let i = (low - 1); // Index of smaller element

  for (let j = low; j <= high - 1; j++) {
    // If current element is smaller than or equal to pivot
    if (arr[j] <= pivot) {
      i++;    // increment index of smaller element
      swap(arr, i, j);
    }
  }
  swap(arr, i + 1, high);
  return (i + 1);
}

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 示例
let arr = [10, 7, 8, 9, 1, 5];
let n = arr.length;
quickSortLomuto(arr, 0, n - 1);
console.log("排序后的数组: " + arr);

这种方案的优点是简单直观，易于理解。缺点是在某些情况下，例如当数组已经部分排序时，性能会下降，因为每次都选择最后一个元素作为基准值，可能导致分区不平衡。

副标题2： Hoare 分区方案

Hoare 分区方案与 Lomuto 方案不同，它使用两个指针，一个从左向右移动，一个从右向左移动，直到它们相遇。这种方案通常比 Lomuto 方案更有效率，尤其是在处理已经部分排序的数组时。

function quickSortHoare(arr, low, high) {
  if (low < high) {
    let partitionIndex = partitionHoare(arr, low, high);

    quickSortHoare(arr, low, partitionIndex);
    quickSortHoare(arr, partitionIndex + 1, high);
  }
  return arr;
}

function partitionHoare(arr, low, high) {
  let pivot = arr[low]; // 选择第一个元素作为基准
  let i = low - 1;
  let j = high + 1;

  while (true) {
    do {
      i++;
    } while (arr[i] < pivot);

    do {
      j--;
    } while (arr[j] > pivot);

    if (i >= j) {
      return j;
    }

    swap(arr, i, j);
  }
}

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 示例
let arr = [10, 7, 8, 9, 1, 5];
let n = arr.length;
quickSortHoare(arr, 0, n - 1);
console.log("排序后的数组: " + arr);

Hoare 分区方案的关键在于 i 和 j 指针的移动和交换，最终返回 j 作为分区点。需要注意的是，quickSortHoare 递归调用时，右侧子数组的范围是 partitionIndex + 1, high，与 Lomuto 方案略有不同。

副标题3： 随机化快速排序

为了避免快速排序在特定输入下退化成 O(n^2) 的时间复杂度，可以采用随机化快速排序。随机化快速排序的核心是在每次分区时，随机选择一个元素作为基准值。

function quickSortRandomized(arr, low, high) {
  if (low < high) {
    let partitionIndex = randomizedPartition(arr, low, high);

    quickSortRandomized(arr, low, partitionIndex - 1);
    quickSortRandomized(arr, partitionIndex + 1, high);
  }
  return arr;
}

function randomizedPartition(arr, low, high) {
    let randomIndex = Math.floor(Math.random() * (high - low + 1)) + low;
    swap(arr, randomIndex, high); // 将随机选择的元素与最后一个元素交换
    return partitionLomuto(arr, low, high); // 使用 Lomuto 分区方案
}

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 示例
let arr = [10, 7, 8, 9, 1, 5];
let n = arr.length;
quickSortRandomized(arr, 0, n - 1);
console.log("排序后的数组: " + arr);

随机化快速排序通过随机选择基准值，可以有效地避免最坏情况的发生，从而提高算法的平均性能。这里选择随机元素与最后一个元素交换，然后使用 Lomuto 分区方案，当然也可以结合 Hoare 分区方案。

副标题4：三种方案的性能比较和选择建议

三种快速排序方案各有优缺点。

• Lomuto 分区方案： 简单易懂，但对于已经部分排序的数组，性能较差。
• Hoare 分区方案： 通常比 Lomuto 方案更有效率，尤其是在处理已经部分排序的数组时。但代码相对复杂一些。
• 随机化快速排序： 通过随机选择基准值，可以有效地避免最坏情况的发生，提高算法的平均性能。

选择哪种方案取决于具体的应用场景。如果对性能要求不高，且数组随机性较好，可以选择 Lomuto 方案。如果需要处理可能已经部分排序的数组，或者对性能有较高要求，可以选择 Hoare 方案或随机化快速排序。 随机化快速排序通常是最佳选择，因为它可以在各种情况下提供良好的平均性能。

副标题5： 快速排序的空间复杂度

快速排序是一种原地排序算法，这意味着它只需要少量的额外空间。在理想情况下（每次分区都将数组分成大致相等的两部分），快速排序的空间复杂度为 O(log n)，这是因为递归调用栈的深度为 log n。 然而，在最坏情况下（每次分区都将数组分成一个空数组和一个包含 n-1 个元素的数组），快速排序的空间复杂度会退化为 O(n)。

通过随机化选择基准值，可以降低最坏情况发生的概率，从而使快速排序的空间复杂度在大多数情况下保持在 O(log n) 级别。

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